7.5: Ejercicios adicionales- Primalidad y Factoraje

En el criptosistema RSA es importante poder encontrar fácilmente grandes números primos. Además, este criptosistema no es seguro si podemos factorizar un número compuesto que es producto de dos primos grandes. Las soluciones a ambos problemas son bastante fáciles. Para saber si un número\(n\) es primo o para factorizar\(n\text{,}\) podemos usar la división de prueba. Simplemente dividimos\(n\) por\(d = 2, 3, \ldots, \sqrt{n}\text{.}\) O bien se obtendrá una factorización, o\(n\) es primo si no se\(d\) divide\(n\text{.}\) El problema es que tal cálculo consume mucho tiempo prohibitivamente si\(n\) es muy grande.

1

Un mejor algoritmo para factorizar enteros positivos impares es el algoritmo de factorización de Fermat.

1. Let\(n= ab\) Ser un número compuesto impar. \(n\)Demostrar que se puede escribir como la diferencia de dos cuadrados perfectos:

   \[ n = x^2 - y^2 = (x - y)(x + y)\text{.} \nonumber \]

   En consecuencia, un entero impar positivo se puede factorizar exactamente cuando podemos encontrar enteros\(x\) y\(y\) tal que\(n = x^2 - y^2\text{.}\)

2. Escribir un programa para implementar el siguiente algoritmo de factorización basado en la observación en la parte (a). El techo de expresión (sqrt (n)) significa el entero más pequeño mayor o igual que la raíz cuadrada de\(n\text{.}\) Escribir otro programa para hacer factorización usando división de prueba y comparar la velocidad de los dos algoritmos. ¿Qué algoritmo es más rápido y por qué?

x := ceiling(sqrt(n))
y := 1

1 : while x^2 - y^2 > n do
    y := y + 1

if x^2 - y^2 < n then
    x := x + 1
    y := 1
    goto 1
else if x^2 - y^2 = 0 then
    a := x - y
    b := x + y
    write n = a * b

2. Pruebas de Primalidad

Recordemos el pequeño teorema de Fermat del Capítulo 6. Let\(p\) be prime con\(\gcd(a, p) = 1\text{.}\) Then\(a^{p-1} \equiv 1 \pmod{p}\text{.}\) We can use Little Theorema de Fermat como prueba de cribado para primes. Por ejemplo,\(15\) no puede ser primo ya que

\[ 2^{15-1} \equiv 2^{14} \equiv 4 \pmod{15}\text{.} \nonumber \]

Sin embargo,\(17\) es un potencial primo ya que

\[ 2^{17-1} \equiv 2^{16} \equiv 1 \pmod{17}\text{.} \nonumber \]

Decimos que un número compuesto impar\(n\) es un pseudoprimo si

\[ 2^{n-1} \equiv 1 \pmod{n}\text{.} \nonumber \]

¿Cuáles de los siguientes números son primos y cuáles son los pseudoprimos?

1. \(\displaystyle 342\)
2. \(\displaystyle 811\)
3. 601
4. \(\displaystyle 561\)
5. \(\displaystyle 771\)
6. \(\displaystyle 631\)

3

Let\(n\) Ser un número compuesto impar y\(b\) ser un entero positivo tal que\(\gcd(b, n) = 1\text{.}\) Si\(b^{n-1} \equiv 1 \pmod{n}\text{,}\) entonces\(n\) es una base pseudoprima\(b\text{.}\) Mostrar que\(341\) es una base pseudoprima\(2\) pero no una base pseudoprima\(3\text{.}\)

4

Escriba un programa para determinar todos los primos menos que\(2000\) usando la división de prueba. Escribe un segundo programa que determinará todos los números menores\(2000\) que los que son primos o pseudoprimos. Compara la velocidad de los dos programas. ¿Cuántos pseudoprimos hay a continuación?\(2000\text{?}\)

Existen números compuestos que son pseudoprimos para todas las bases a las que son relativamente primos. Estos números se llaman números de Carmichael. El primer número de Carmichael es\(561 = 3 \cdot 11 \cdot 17\text{.}\) En 1992, Alford, Granville y Pomerance demostraron que hay un número infinito de números de Carmichael [4]. Sin embargo, los números de Carmichael son muy raros. Solo hay 2163 números de Carmichael menos que\(25 \times 10^9\text{.}\) Para pruebas de primalidad más sofisticadas, ver [1], [6], o [7].