Prime Number
Un número primo es un número natural mayor que 1 divisible solo entre 1 y sí mismo; es el bloque constituyente de la teoría de números, y todo entero se factoriza de forma única en primos.
Propósito
Servir de bloques constituyentes de los enteros, base de la teoría de números y la criptografía (RSA).
Mecanismo
Un número natural mayor que 1 cuyos únicos divisores son 1 y sí mismo. Teorema fundamental de la aritmética: todo entero se factoriza de forma única en primos. Tests de primalidad: división por tentativa, Miller-Rabin (probabilístico), AKS (determinista pero lento). Hay infinitos primos (demostración de Euclides).
Casos de uso
- Generación de claves RSA
- Parámetros Diffie-Hellman
- Capacidades primas de tablas hash
- Investigación en teoría de números
Ejemplos
- entrada
The first 10 primesOutput2,3,5,7,11,13,17,19,23,292 is the only even prime
Errores comunes
- Using small primes for RSA moduli
- Use large primes (≥1024 bits)
Términos relacionados
Modular Arithmetic
La aritmética modular toma restos tras operaciones enteras, manteniendo los resultados en [0, n); es el fundamento de la teoría de números y la criptografía. GLOSARIO
BigInteger
BigInteger es un tipo de entero de precisión arbitraria, no limitado por un tamaño de palabra fijo, usado para cálculos más allá del rango de los enteros nativos (como criptografía y combinatoria). GLOSARIO
GCD
El MCD (máximo común divisor) es el mayor entero positivo que divide a dos o más enteros, calculado eficientemente con el algoritmo de Euclides. GLOSARIO