Page 77 - 16 Fermat

puede preguntarse si un número dado cumple la propiedad del
pequeño teorema de Fermat; sin embargo, nótese que esto es el
recíproco del teorema y, por tanto, no hay ninguna garantía de que
el número sea primo. De hecho, se sabe que los llamados números
de Carmichael no cumplen el recíproco del teorema. Aun así,
dicha prueba es tan sencilla y rápida que se usa en la implementa-
ción del algoritmo RSA para descartar rápidamente números com-
puestos. Porque, en realidad, la prueba de primalidad basada en
el pequeño teorema es una prueba de si el número es compuesto.
Por si fuera poco, el pequeño teorema de Fermat se utiliza tam-
bién para demostrar que el algoritmo RSA es con-ecto.
Otras pruebas de primalidad se dividen entre probabilísticas y
deterministas. Entre las primeras está la prueba de Miller-Rabin,

LA FACTORIZACIÓN DE FERMAT

Fermat inventó un método de factorización que, en ciertos casos, es más
eficiente que la división por tentativa, a partir de la observación de que un
2
2
número impar no cuadrado se puede escribir como N=x - y , donde
X =n1+n2 Y Y=n1-n2_
2 2
Se puede demostrar fácilmente que N=n n • Si N es primo, n =N y n =l. En
1 2 1 2
caso contrario, n y n son divisores propios de N. Dado que n y n son impa-
1 2 1 2
res por ser N impar, x e y son enteros. De aquí que resolver la ecuación ante-
rior para x e y enteros implique la existencia de una factorización de N. Para
resolver esta ecuación se procede por tanteo, empezando con un entero m
que cumpla cierta propiedad y, si no es la solución, continuar con otro núme-
ro m' que se obtiene a partir de m, y continuar así hasta que se obtenga un
divisor propio o se llegue al propio número N. La factorización de Fermat
puede llegar a ser muy eficiente en ciertos casos, porque los números m tienen
que ser cuadrados, y muchas veces es muy fácil determinar si un número es
cuadrado solo por inspección. En efecto, los cuadrados perfectos solo pueden
terminar en O, 1, 4, 5, 9, 16, 36, 56, 76 y 96, lo cual excluye el 90% de las ter-
minaciones. La belleza del método es que no requiere conocer todos los
primos hasta un cierto número, y que, si N es compuesto y tiene un factor
cercano a ✓N, esta factorización lo identifica con rapidez.

LA MODERNA TEORÍA DE NÚMEROS 77