test de primalidad

LA GACETA

567

´
LA COLUMNA DE MATEMATICA
COMPUTACIONAL
Secci´on a cargo de
Tom´
as Recio

El objetivo de esta columna es presentar de manera sucinta, en
cada uno de los n´
umeros de La Gaceta, alguna cuesti´
on matem´
atica
en la que los c´
alculos, en un sentido muy amplio, tengan un papel
destacado. Para cumplir este objetivo el editor de la columna (sin
otros m´eritos que su inter´es y sinotros recursos que su mejor voluntad) quisiera contar con la colaboraci´
on de los lectores, a los que
anima a remitirle (a la direcci´
on que se indica al pie de p´
agina1 ) los
trabajos y sugerencias que consideren oportunos.
´
EN ESTE NUMERO.
..

Para este n´
umero de La Gaceta hemos solicitado la colaboraci´on del Catedr´
atico de Algebra de la Universidad de Valladolid, D. Juan Tena Ayuso.
Setrata de una introducci´
on excelente a un tema de actualidad e inter´es
(econ´omico y matem´atico): la b´
usqueda de n´
umeros primos muy grandes, y
su posible utilizaci´
on en determinados algoritmos criptogr´
aficos.
El profesor Tena ha hecho un esfuerzo notable para describir de modo
particularmente sencillo el complejo y dif´ıcil mundo de los tests de primalidad.
Espero que el resultado seadel agrado de los lectores.

Tests de Primalidad
por
Juan Tena Ayuso

INTRODUCCION
Los n´
umeros primos han interesado a los matem´aticos desde hace, al menos,
2000 a˜
nos (los Elementos de Euclides se ocupan de ellos, demostrando en particular la existencia de infinitos primos). Tal inter´es parece justificado ya que,
en virtud del Teorema Fundamental de la Aritm´etica, todo n´
umero natural se
1Tom´
as Recio. Departamento de Matem´
aticas. Facultad de Ciencias.
Universidad de Cantabria. 39071 Santander. recio@matesco.unican.es

568

´
LA COLUMNA DE MATEMATICA
COMPUTACIONAL

expresa, de forma u
´nica, como producto de primos. Este teorema ser´ıa formulado expl´ıcitamente por Gauss (Disquisitiones Arithmeticae, 1801) pero era
bien conocido por los matem´aticos anteriores.
Por otra parte,el tema es lo bastante complejo para que el citado inter´es por los n´
umeros primos haya podido mantenerse hasta la actualidad. En
particular, las reglas que rigen la distribuci´
on de los primos en el conjunto
N de los n´
umeros naturales, plantearon desde el principio un desaf´ıo, ya que
tal distribuci´
on no parece seguir pautas razonables : por ejemplo, existen primos consecutivos que sediferencian en dos unidades, los denominados primos
gemelos (aunque se ignora si, como se cree, existen infinitas tales parejas),
mientras que existen primos consecutivos cuya diferencia es tan grande como
se quiera. El problema de determinar si un n´
umero natural dado es primo o
no es el objetivo de los tests de primalidad.
El estudio de los n´
umeros primos ocupa un lugar destacado en la historiade las Matem´
aticas y muchos de los grandes matem´aticos han ligado su
nombre a ellos. La lista ser´ıa interminable, citemos solo algunos: Euclides, Fermat, Euler, Legendre, Gauss, Dedekind, Dirichlet, Hilbert, Hadamard, de la
Vall´ee-Poussin, etc. Todos ellos y otros muchos han ido a˜
nadiendo piezas al
puzzle de los n´
umeros primos, ver [Ribemboim, 1988], [Bressoud, 1989]. Por
ejemplo, comohemos dicho, Euclides mostr´o la infinitud de los primos (libro
IX, proposici´
on 20) y Hadamard y de la Vall´ee-Poussin demostraron el teorema de los n´
umeros primos sobre la densidad de estos dentro de los naturales:
si π(x) denota el n´
umero de primos no superiores al real positivo x, se tiene
que π(x) ∼ x/ ln(x). El impulso subyacente a los estudios citados era el puro
desaf´ıo intelectual deintentar explicar las propiedades de los primos y hasta hace pocos a˜
nos casi todos los matem´aticos subscribir´ıan la afirmaci´
on de
Hardy (aplicada al contexto, m´as amplio, de la Teor´ıa de N´
umeros):
...there is one science at any rate, and that their own, whose very remoteness
from ordinary human activities should keep it gentle and clean. [G.H. Hardy
A Mathematician’s Apology, 1940]

Al...