[skip-to-content]
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\gcd}{\operatorname{mcd}} \renewcommand{\lcm}{\operatorname{mcm}} \renewcommand{\deg}{\operatorname{gr}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Sección7.4Ejercicios Adicionales: Primalidad y Factorización

En el criptosistema RSA es importante ser capaz de encontrar números primos grandes con facilidad. Asimismo, este criptosistema deja de ser seguro si somos capaces de factorizar un número entero que sea el producto de dos números primos grandes. Las soluciones teóricas de ambos problemas son bastante simples. Para saber si un número \(n\) es primo o para factorizar \(n\text{,}\) podemos usar intentos de división. Simplemente dividimos \(n\) entre \(d = 2, 3, \ldots, \sqrt{n}\text{.}\) Ya sea obtendremos una factorización, o \(n\) es primo si ningún \(d\) divide a \(n\text{.}\) El problema es que tales cálculos toman muchísimo tiempo si \(n\) es muy grande.

1

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

  1. Sea \(n= ab\) un número impar compuesto. Demuestre que \(n\) puede ser escrito como la diferencia de dos cuadrados perfectos:

    \begin{equation*} n = x^2 - y^2 = (x - y)(x + y). \end{equation*}

    Por lo tanto, un entero positivo impar se puede factorizar si y solo si podemos encontrar enteros \(x\) e \(y\) tales que \(n = x^2 - y^2\text{.}\)

  2. Escriba un programa para implementar el siguiente algoritmo de factorización basado en la observación en la parte (a). La expresión ceiling(sqrt(n)) se refiere al menor entero que es mayor o igual a la raíz cuadrada de \(n\text{.}\) Escriba otro programa que use intentos de división y compare la velocidad de los dos algoritmos. ¿Cuál de ellos 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
[listing]7.6algoritmo en pseudo-código
2Verificación de Primalidad

Recuerde el Pequeño Teorema de Fermat del Capítulo 6. Sea \(p\) un primo con \(\gcd(a, p) = 1\text{.}\) Entonces \(a^{p-1} \equiv 1 \pmod{p}\text{.}\) Podemos usar el Pequeño Teorema de Fermat como un examen para primos. Por ejemplo, 15 no puede ser primo pues

\begin{equation*} 2^{15-1} \equiv 2^{14} \equiv 4 \pmod{15}. \end{equation*}

Pero, 17 es potencialmente un primo pues

\begin{equation*} 2^{17-1} \equiv 2^{16} \equiv 1 \pmod{17}. \end{equation*}

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

\begin{equation*} 2^{n-1} \equiv 1 \pmod{n}. \end{equation*}

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

  1. 342

  2. 811

  3. 601

  4. 561

  5. 771

  6. 631

3

Sea \(n\) un número impar compuesto y \(b\) un entero positivo tal que \(\gcd(b, n) = 1\text{.}\) Si \(b^{n-1} \equiv 1 \pmod{n}\text{,}\) entonces \(n\) es un pseudoprimo en base \(b\text{.}\) Muestre que 341 es un pseudoprimo en base 2 pero no es un pseudoprimo en base 3.

4

Escriba un programa para determinar todos los primos menores a 2000 usando intentos de división. Escriba un segundo programa que determine todos los números menores a 2000 que sean primos o pseudoprimos. Compare la velocidad de ambos programas. ¿Cuántos pseudoprimos hay menores a 2000?

Existen números compuestos que son pseudoprimos para todas la bases con que son relativamente primos. Estos números se llaman números de Carmichael. El primer número de Carmichael es el \(561 = 3 \cdot 11 \cdot 17\text{.}\) En 1992, Alford, Granville, y Pomerance demostraron que hay infinitos números de Carmichael [4]. Pero, los números de Carmichael son muy escasos. Existen solo \(2163\) números de Carmichael menores a \(25 \times 10^9\text{.}\) Para tests de primalidad más sofisticados, vea [1], [6], o [7].