Page 78 - 16 Fermat

que se basa también en el pequeño teorema de Fermat, o la de
Solovay-Strassen, fundamentada en un teorema de Euler que gene-
raliza el pequeño teorema. Esta última nunca declara que un nú-
mero es primo sin serlo, pero es menos exitosa con números
compuestos. En efecto, hay pruebas que son más eficaces mos-
trando que un número es compuesto y otras más aptas para probar
que es primo.
Una extensión determinista de la prueba de Miller-Rabin se
basa en un resultado no probado: la hipótesis extendida de Rie-
mann. Su eficacia, evidentemente, depende de que dicha hipótesis
sea cierta. Sin embargo, en 2002 se anunció por primera vez una
prueba, llamada AKS, que es general (funciona para cualquier nú-
mero), determinista, incondicional (no depende de resultados no
probados) y eficiente (con una complejidad computacional poli-
nomial). El algoritmo AKS está también basado en una generaliza-
ción del pequeño teorema de Fermat.
Es importante distinguir las pruebas de primalidad de los
algoritmos de factorización. Mientras que todo algoritmo de fac-
torización es implícitamente una prueba de primalidad, las prue-
bas de primalidad no implican necesariamente factorizar. Por
ejemplo, la criba de Eratóstenes no factoriza el número (aunque
una generalización trivial puede hacerlo) y la prueba basada di-
rectamente en el pequeño teorema de Fermat ni siquiera encuen-
tra ninguno de sus factores, mientras que la división por tentativa
sí lo hace. De aquí que, aunque se haya encontrado un algoritmo
eficiente como prueba de primalidad, el problema de la factori-
zación siga siendo lo suficientemente complicado como para que
el algoritmo RSA permanezca vigente. La prueba AKS no facto-
riza el número: las transacciones en Internet continúan siendo
seguras.
Existen muchos otros resultados que dependen del pequeño
teorema. Uno de los más conocidos es algo que todos hemos ob-
servado: la expansión decimal de un número racional se repite
periódicamente si en dicho racional, expresado como fracción
irreducible, el denominador es un primo p distinto de 2 y de 5 (que
son los factores primos de 10). De hecho, se repite con un período
de repetición de, o bien p-1 o bien un divisor de p-1. Es por ello

78 LA MODERNA TEORÍA DE NÚMEROS