introduccion a los numero´ s pseudoprimos
TRANSCRIPT
Introduccion a los numeros pseudoprimos
Trabajo de Tesispresentado al
Departamento de Matematicas
por
Valerie Gauthier Umana
Asesor: Carlos Montenegro
Para optar al tıtulo deMatematica
MatematicasUniversidad de Los Andes
Julio 2006
Introduccion a los numeros pseudoprimos
Aprobado por:
Carlos Montenegro, Asesor
Xavier Caicedo
Fecha de Aprobacion
0234
Tabla de Contenido
Lista de Tablas IV
Lista de Figuras V
Introduccion VI
I. Preliminares 1
II. Los numeros pseudoprimos 5
2.1. Los numeros pseudoprimos . . . . . . . . . . . . . . . . . . . . . . . 5
2.2. Los pseudoprimos fuertes y de Euler . . . . . . . . . . . . . . . . . 13
2.3. La relacion entre los psp, los epsp, los spsp y los numeros deCarmichael. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4. La densidad de los numeros de Carmichael . . . . . . . . . . . . . . 19
III. Los numeros pseudoprimos de Lucas 27
3.1. Los pseudoprimos de Lucas . . . . . . . . . . . . . . . . . . . . . . 27
3.2. La densidad de los pseudoprimos de Lucas . . . . . . . . . . . . . . 38
IV. Aplicaciones 45
Referencias 50
iii
0234
Lista de Tablas
1. Lista de los pseudoprimos que no son libres de cuadrados, en base 2,menores que 25× 109 . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2. Cantidad de pseudoprimos en las bases 2, 3, 5 y 7 inferiores a unlımite dado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3. La evolucio de C(x) en el tiempo . . . . . . . . . . . . . . . . . . . . 19
4. Dos aproximaciones de C(x) . . . . . . . . . . . . . . . . . . . . . . . 22
5. Los valores de P2(x), E2(x), S2(x) y C(x), segun el valor de x . . . . 23
6. Comportamiento de C(x) y P2(x) con relacion a π(x) . . . . . . . . . 23
7. Los numeros fuertemente pseudoprimos simultaneamente en las bases2, 3 y 5 menores a 25× 109 . . . . . . . . . . . . . . . . . . . . . . . 25
8. Dos aproximaciones de L(x), R(x) y S(x), segun el metodo A o B . . 42
iv
0234
Lista de Figuras
1. La relacion entre los psp, los epsp, los spsp y los numeros de Carmichael 18
2. La relacion entre los lpsp, los lepsp y los lspsp, segun el metodo uti-lizado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
v
0234
Introduccion
El desarrollo de los computadores revoluciono varias ramas de las matematicas,
entre ellas una de las mas antiguas: la teorıa de numeros.
Una de las grandes preocupaciones de los matematicos interesados en esta rama,
es saber cuando un numero es o no primo. Grandes matematicos se esforzaron por
encontrar numeros primos muy grandes, por dar formulas para generarlos, y por
hallar algoritmos que nos permitieran saber si un numero es o no primo.
Este interes se vio incrementado, incluso fuera del ambito de las matematicas, cuando
se descubrio que los numeros primos grandes se podıan utilizar para cifrar mensajes
enviados por canales inseguros, tales como las lıneas telefonicas o las transmisiones
de radio.
Existen varias propiedades de enteros, que se cumplen cuando estos son numeros
primos, por ejemplo el pequeno teorema de Fermat (que veremos mas adelante). Ası,
cuando sabemos que un numero dado no cumple tal propiedad, podemos afirmar
que es un numero compuesto; sin embargo, si la cumple, no podemos afirmar que
sea un numero primo. Estos ultimos son llamados pseudoprimos y veremos en el
capıtulo 2 que son bastante escasos.
Hay varios algoritmos que nos permiten saber si un numero n dado es primo,
uno de ellos (el mas intuitivo de todos) es dividir a n por todos los numeros primos
menores a√
n, sin embargo, si el numero es muy grande (por ejemplo de 50 cifras),
este proceso seria muy largo, incluso imposible de realizar.
Existe otro tipo de algoritmos que tienen este mismo fin, pero cuyas dos respuestas
vi
0234
posibles son: n es compuesto, si alguno de los pasos falla. De lo contrario, “es muy
probable que n sea primo”. La probabilidad de la respuesta es bastante alta (segun
el algoritmo), de hecho hay muchos para los cuales no se ha podido encontrar un
contraejemplo (existen varias recompensas para quienes lo encuentre, o demuestren
que no existe).
Aunque la respuesta no sea del todo segura, la rapidez del metodo y su muy pequena
probabilidad de error los hacen bastante utiles.
En el Capıtulo 2 daremos una introduccion a los numeros pseudoprimos; estudi-
aremos sus principales propiedades y veremos algunos de los algoritmos (como el de
Maple) para determinar si un numero es primo.
En el Capıtulo 3 haremos un trabajo analogo al hecho en el 2, pero con los pseudop-
rimos de Lucas, criterio que nos permitira mejorar el algoritmo dado anteriormente.
Y finalmente, en el Capıtulo 4, veremos a grandes rasgos como funciona el proce-
so de cifrar los mensajes, una de las aplicaciones mas frecuentes de los pseudoprimos.
Mi aporte fue buscar la bibliografıa, sintetizar y redactar un documento que
permita introducir y motivar al lector a los numeros pseudoprimos, haciendo un
estado del arte de estos numeros, y dando su principal aplicacion. Para esto tuve
que estudiar las demostraciones y en la mayorıa de los casos completar partes que
los autores daban por hecho. En otros casos donde no encontre las demostraciones
las hice en su totalidad.
vii
0234
Capıtulo I
Preliminares
A continuacion enumeramos resultados basicos que utilizaremos mas adelante.
Las referencias para este capıtulo son : [18], [2], [10], [4], [11], [7], [3].
El Teorema Fundamental de la Aritmetica afirma, que todo entero positivo se
puede representar como producto de factores primos de una forma unica, salvo el
orden. A continuacion vamos a asumir, cuando escribimos n = pα11 ...pαk
k que los pi
son diferentes entre ellos, para todo i = 1, ...k y αi > 0.
Definicion 1.0.1 (La funcion de Euler φ(n) ). La funcion de Euler φ(n), asocia a
cada entero n la cantidad de enteros positivos relativamente primos a n, menores o
iguales que el.
Definicion 1.0.2 (mınimo comun multiplo (mcm)). El mınimo comun multiplo
(mcm) de dos o mas numeros naturales, es el menor numero natural que es multiplo
de todos ellos.
Definicion 1.0.3 (Libre de cuadrados). Un numero se dice libre de cuadrados, si
su descomposicion en numeros primos no contiene factores repetidos.
Teorema 1.0.1 (El pequeno teorema de Fermat). Sea p un primo. Si p no divide
a a entonces ap−1 ≡ 1(mod p). Para todo entero a, ap ≡ a(mod p).
Teorema 1.0.2 (Generalizacion de Euler del teorema de Fermat). Si (a,n)=1, en-
tonces aφ(n) ≡ 1(mod n)
Teorema 1.0.3 (El teorema chino del residuo). Sean m1, m2, ...,mr r enteros pos-
itivos, relativamente primos entre ellos, y a1, a2, ..., ar, r enteros. La congruencia:
1
0234
x ≡ a1(mod m1), x ≡ a2(mod m2),...,x ≡ ar(mod mr), admite por lo menos una
solucion comun. Y si x0 es una de estas soluciones, x1 va a ser otra solucion si y
solo si es de la forma x1 = x0 + km, con m = m1m2...mr.
Definicion 1.0.4 (El coeficiente binomial). Sea n un real, y k un entero no negativo,(nk
)es el coeficiente binomial y esta dado por la siguiente formula:(
n
k
)=
n(n− 1)(n− 2)...(n− k + 1)
k!
Si n y k son enteros, y si 0 ≤ k ≤ n entonces(
nk
)= n!
k!(n−k)!.
Teorema 1.0.4 (El teorema del binomio). Para todo entero n ≥ 1, y todo par de
reales x e y,
(x + y)n =n∑
k=0
(n
k
)xkyn−k
Definicion 1.0.5 (Orden de a modulo m). Sea m un entero positivo, y a un entero
tal que (a, m) = 1. Sea h el menor entero positivo tal que ah ≡ 1(mod m). Decimos
que el orden de a modulo m es h, o que a pertenece al exponente de h modulo m y
lo notamos om(a) = h.
Lema 1.0.1. Si a tiene orden h modulo m, entonces los enteros positivo k, tal que
ak ≡ 1(mod m), son precisamente aquellos, tales que h|k.
Definicion 1.0.6 (Una raız primitiva). Si existe un real g, tal que el orden de a
modulo m es φ(m), entonces g es llamada raiz primitiva modulo m.
Teorema 1.0.5. Existe una raız primitiva modulo m si y solo si m=1, 2, 4, pα, o
2pα, cuando p es un primo impar.
Definicion 1.0.7 (residuo cuadratico). Sea p un primo y a un entero tal que (a, p) =
1: a es un residuo cuadratico (mod p); si existe un entero x que sea solucion de
x2 ≡ a(mod p), y a es un residuo no cuadratico (mod p) si no existe un entero x
que sea solucion de x2 ≡ a(mod p).
Notamos (ap) al sımbolo de Legendre que se define de la siguiente manera:
2
0234
Definicion 1.0.8 (Sımbolo de Legendre).
(ap) = 1 si a es un residuo cuadratico (mod p).
(ap) = 0 si p divide a a.
(ap) = −1 si a es un residuo no cuadratico (mod p).
Teorema 1.0.6. Sea p un primo impar, (ap) ≡ a
p−12 (mod p)
El sımbolo de Jacobi ( an) es una generalizacion del de Legendre y se define de la
siguiente manera:
Definicion 1.0.9 (Sımbolo de Jacobi). Sea n =∏k
i=1 peii un numero impar. El
sımbolo de Jacobi de n es: (a
n
)=
k∏i=1
(a
p
)ei
(1)
Vale la pena resaltar que que ( an) ∈ {−1 , 0, 1}.
Definicion 1.0.10. Llamamos π(x), la cantidad de numeros primos menores o
iguales a x.
Para simplificar las ecuaciones vamos a utilizar la siguiente notacion introducida
en [11]:
Notacion 1.0.1. Sea lnrx la funcion que resulta de componer r veces el logaritmo
natural de x: lnx.
Teorema 1.0.7. Sea f(x) un polinomio con coeficientes enteros, y para todo entero
positivo m, sea N(m) la cantidad de soluciones de la congruencia f(x) ≡ 0(mod m).
Si m = m1m2, con (m1, m2) = 1, entonces N(m) = N(m1)N(m2). Si m = pα11 ...pαk
k ,
entonces N(m) = N(pα11 )...N(pαk
k ).
Teorema 1.0.8 (Lema de Hensel). Sea f(x) un polinomio con coeficientes enteros.
Si f(a) ≡ 0(mod pj) y f ′(a) no es congruente con 0 modulo p, entonces existe un
unico t(mod p) tal que f(a + tpj) ≡ 0(mod pj+1).
3
0234
Teorema 1.0.9. Sea p un primo, y (a, p) = 1, entonces la congruencia xn ≡a(mod p) tiene (n, p − 1) soluciones o ninguna, segun si a
p−1(n,p−1) ≡ 0(mod p) o
no.
Definicion 1.0.11 (Numero aureo). Tambien conocido como razon aurea y es la
solucion positiva de la ecuacion x2 − x− 1 = 0.
Teorema 1.0.10. Para todo entero positivo n:∑
d|n φ(d) = n.
Definicion 1.0.12 (O(g(n))). Sea f(n) una funcion, decir que f(n) = O(g(n))
significa que existen constantes positivas c y k, tales que 0 ≤ f(n) ≤ cg(n) para todo
n ≥ k. Los valores de c y de k estan determinados por la funcion f y no dependen
de n.
Definicion 1.0.13 (Algoritmos de tiempo polinomial). Se dice que un algoritmo
es de tiempo polinomial, si el numero de pasos necesarios para finalizarlo es O(nk),
donde k es un entero no negativo, y n es la entrada del algoritmo.
Definicion 1.0.14 (Los primos de Sophie Germain). se dice que un numero primo
p es un primo de Sophie Germain si 2p + 1 tambien es un numero primo.
Definicion 1.0.15 (La hipotesis de Riemann). La funcion zeta de Riemann ζ(s)
esta definida para todos los numeros complejos s 6= 1 y posee ciertos ceros triviales
para s = −2, s = −4, s = −6, ... La conjetura de Riemann hace referencia a los
ceros no triviales afirmando que :
La parte real de todo cero no trivial de la funcion zeta de Riemann es 12.
Por lo tanto los ceros no triviales deberıan encontrarse en la lınea crıtica 12
+ i t,
donde t es un numero real e i es la unidad imaginaria.
La hipotesis de Riemann, formulada por primera vez por Bernhard Riemann
en 1859, es una conjetura sobre la distribucion de los ceros de la funcion zeta de
Riemann ζ(s) y constituye uno de los problemas abiertos mas importantes de las
matematicas contemporaneas. El Instituto Clay de Matematicas ofrece dentro del
marco de su programa de problemas del milenio 1 millon de dolares como premio
por una prueba de la conjetura. La mayor parte de los matematicos consideran que
la conjetura es cierta.
4
0234
Capıtulo II
Los numeros pseudoprimos
2.1. Los numeros pseudoprimos
Los antiguos chinos descubrieron que si un entero n no divide a 2n − 2 entonces
es un numero compuesto. Sin embargo si n lo divide, no podemos afirmar que sea
primo. Es el caso de n = 341 = 11 × 31 que divide a 2341 − 2. A los numeros com-
puestos que cumplen esta propiedad los llamamos numeros pseudoprimos en base
2, lo cual notamos psp(2). Sin embargo, este tipo de numeros son bastante escasos,
de hecho hay aproximadamente 450 millones de numeros primos y solamente 15000
numeros psp(2) menores a 1010 (ver la tabla 6).
El 18 de Octubre de 1640, Fermat le escribio una carta a su amigo Frenicle, en
donde afirmaba que esta propiedad no era exclusiva del numero 2, sino que en general
si n es primo entonces divide a an − a. Al ser n primo, cuando a no es multiplo de
p, esto es equivalente a decir que : an−1 ≡ 1(mod n). Podemos, entonces, definir los
numeros pseudoprimos en cualquier base a (numero entero) de la siguiente manera:
Definicion 2.1.1 (Numeros pseudoprimos). [11] Un numero compuesto e impar n,
es pseudoprimo en base a (lo cual notamos psp(a)) si
an−1 ≡ 1(mod n) (2)
Nota: Antes de 1980, los numeros pseudoprimos eran los numeros que cumplıan
la ecuacion (2); en ese ano, Pomerance, Selfridge, and Wagstaff [11] restringieron su
uso a los numeros compuestos e impares.
5
0234
Ejemplos: 91 = 7× 13 es psp(3) y 105 = 3× 5× 7 es psp(13).
La cantidad de numeros psp(a) es bastante pequena con respecto a la cantidad
de primos (ver la tabla (6)), por lo tanto, si un numero cumple (2) es muy probable
que sea primo. De hecho, a los numeros que cumplan esta propiedad, se les llama
“probablemente primos en una base a”.
Ahora, si este numero cumple la condicion (2) a la vez para a = 2 y a = 3, es
aun mas probable que sea primo. Esta idea motiva la definicion de los numeros de
Carmichael:
Definicion 2.1.2 (Numeros de Carmichael). [11] Un numero n compuesto e impar
es de Carmichael si n es psp(a) para todo a < n, tal que (a, n) = 1.
El numero de Carmichael mas pequeno es 561 = 3×11×17, el cual fue descubierto
por Robert Daniel Carmichael en 1910. Otros ejemplos: 1105 = 5× 13× 17, 1729 =
7× 13× 19, 2465 = 5× 17× 29. Con el objeto de buscar definiciones alternas de los
numeros de Carmichael que nos permitan familiarizarnos con ellos, introducimos la
siguiente definicion:
Definicion 2.1.3 (El indicador de Carmichael λ(n)). [8] Llamamos indicador de
Carmichael a la funcion que a todo entero n ≥ 1 asocia λ(n): el menor entero h tal
que ah ≡ 1(mod n) para todo a tal que (a,n)=1.
Propiedad 2.1.1. Sea n = 2αpα11 ...pαk
k , donde los pi son primos impares diferentes
entre si y α, αi son enteros positivos. Entonces λ(n) se calcula de la siguiente forma:
λ(1) = 1.
λ(2α) = φ(2α) = 2α−1, si α = 1, 2.
λ(2α) = 12φ(2α) = 2α−2, si α ≥ 3.
λ(pαii ) = φ(pαi
i ) = pαi−1i (pi − 1), para pi un primo impar.
λ(n) = mcm(λ(2α), λ(pα11 )..., λ(pαk
k )).
6
0234
Demostracion: Si n ∈ {1, 2, 4, pαii }, con pi un primo impar, segun el teorema
1.0.2 (p.1) aφ(n) ≡ 1(mod n), para todo a tal que (a, n) = 1. Y λ(n) es el menor entero
h tal que ah ≡ 1(mod n), para todo a tal que (a, n) = 1, por lo tanto λ(n) ≤ φ(n).
Segun el teorema 1.0.5 (p.2) para estos valores de n existe b, una raiz primitiva
modulo n. Es decir, que para algun b tal que (b, n) = 1, el mınimo h tal que ah ≡1(mod n) es φ(n). Por lo tanto λ(n) = φ(n).
Ahora, si n = 2α, con α ≥ 3, sea H = 2α−2. Veamos primero por induccion en α que
aH ≡ 1(mod 2α).
Caso base: α = 3; veamos que a2 ≡ 1(mod 23), para todo a impar. Tenemos cuatro
posibilidades: a puede ser congruente a 1, 3, 5, o 7 modulo 8. En estos cuatros casos,
a2 ≡ 1(mod 8), y 2 es el mınimo tal que esto pasa. Ası que λ(n) = 2α−2, si α = 3.
Paso inductivo: La hipotesis de induccion (HI) es la siguiente: a2α−2 ≡ 1(mod 2α).
Mostremos que si HI es valida, a2α−1 ≡ 1(mod 2α+1). Pero a2α−1 ≡ 1(mod 2α+1) si
y solo si a2α−1 − 1 ≡ 0(mod 2α+1) si y solo si 2α+1|(a2α−2 − 1)(a2α−2+ 1). Y la HI
es verdad si y solo si a2α−2 − 1 ≡ 0(mod 2α), es decir, si y solo si 2α|(a2α−2 − 1).
Ademas, como a es impar, 2|(a2α−2+ 1). Por lo tanto, (2)(2α)|(a2α−2 − 1)(a2α−2
+ 1),
y ası aH ≡ 1(mod 2α).
Ahora, veamos que λ(n) = H para todo α: Sea K el mınimo h tal que ah ≡ 1(mod n)
para todo a con (a, n) = 1. Por el lema 1.0.1 (p.2) tenemos que K|(H = 2α−2), es
decir que que K es de la forma 2R, para algun entero R ≤ (α − 2). Veamos que
para todo α ≥ 3 existe un a tal que (a, n) = 1 y a2α−3 6≡ 1(mod n); de ser ası,
λ(n) = 2α−2. Notemos que si α = 3, 31 6≡ 1(mod 8).
Demostramos por induccion que existe a tal que (a, n) = 1, a ≡ 1(mod 4) y a2α−3 6≡1(mod n) para α > 3:
Caso base: Si α = 4, tomando a = 5, vemos que 5 ≡ 1(mod 4), y que a2α−3= a2 =
25 ≡ 9 6≡ 1(mod 24).
Paso inductivo: Ahora, si α ≥ 4 supongamos que existe un a tal que a ≡ 1(mod 4)
y a2α−3 6≡ 1(mod 2α) (HI), y veamos que a2α−2 6≡ 1(mod 2α+1), es decir que 2α+1 -(a2α−2 − 1) = (a2α−3 − 1)(a2α−3
+ 1). Segun la HI, 2α - (a2α−3 − 1), por lo tanto
para que 2α+1|(a2α−3 − 1)(a2α−3+ 1), se necesita que 4|(a2α−3
+ 1), es decir que
a2α−3 ≡ −1(mod 4), pero esto no es verdad ya que a ≡ 1(mod 4). Por lo tanto si
7
0234
α ≥ 3, λ(2α) = 2α−2.
Ahora si n = 2λpλ11 ...pλk
k , donde los pi son primos impares diferentes entre ellos, sea
H = mcm(λ(2α), λ(pα11 )..., λ(pαk
k )), veamos que λ(n) = H.
Primero veamos que aH ≡ 1(mod n): Sean a1 = aλ(2α) y ai+1 = aλ(pαii ), para i =
1, ..., k. Sea x ≡ a1(mod 2α) y x ≡ ai+1(mod pαii ), para todo i = 1, ..., k, un sistema
de congruencias. Por la definicion de λ(2α) y de λ(pαii ), sabemos que 1 es solucion
de este sistema, ası que, segun el teorema chino del residuo, si x1 es otra raız de
este sistema, tenemos que x1 ≡ 1(mod n). Por la definicion de H, existen enteros
A y Ai tales que H = A(λ(2α)) y H = Ai(λ(pαii )) para i = 1, ..., k, por lo tanto
aH ≡ (aλ(2α))A ≡ 1(mod 2α), y aH ≡ (aλ(pαii ))Ai ≡ 1(mod pαi
i ) para todo i = 2, ..., k.
Entonces aH tambien es una solucion al sistema, y por lo tanto aH ≡ 1(mod n).
Ahora veamos que, λ(n) = H. Como aH ≡ 1(mod n), sabemos que λ(n)|H. Como
aλ(n) ≡ 1(mod n), tenemos que aK ≡ 1(mod 2α), es decir, que λ(2α)|λ(n), y para
todo i = 1, ..., k, aλ(n) ≡ 1(mod pα1i ), ası que H|λ(n) y por lo tanto H = λ(n).
�
El siguiente teorema nos permite dar otra definicion de los numeros de Carmichael:
Teorema 2.1.1. [19] Un numero compuesto e impar n es un numero de Carmichael
si y solo si λ(n) divide a (n− 1).
Demostracion: Si n es un numero de Carmichael, tenemos que an−1 ≡ 1(mod n),
para todo a tal que (a, n) = 1. Como, por definicion, λ(n) es el menor entero h tal
que xh ≡ 1(mod n) para todo x tal que (x, n) = 1 tenemos entonces que λ(n) divide
a (n− 1).
Ahora, si λ(n) divide a (n − 1), existe un entero t tal que (n − 1) = tλ(n). Ten-
emos, entonces, que an−1 = at.λ(n) = (aλ(n))t ≡ 1t = 1(mod n) para todo a tal que
(a, n) = 1, es decir, n es un numero de Carmichael.
�
En 1899 Korselt (respondiendo al “probleme chinois”de L’intermediaire des Mathemati-
ciens, periodico frances equivalente en esa epoca al actual “ The American Mathe-
matical Monthly ”) afirmo que:
8
0234
Teorema 2.1.2 (Criterio de Korselt). [14] an−1 ≡ 1(mod n) para todo a tal que
(a, n) = 1 si y solo si
(i) n es libre de cuadrados y
(ii) p− 1 divide a n− 1 para todo primo p que divide a n.
Demostracion: Supongamos que i y ii se cumplen y veamos que n es un numero
de Carmichael:
Por (i), n = p1p2...pt donde los pi son diferentes entre ellos. Por (ii), (p−1) divide a
(n−1) para i = 1, ..., t, es decir, existen enteros ki tales que (n−1) = ki(pi−1). Por
el Pequeno Teorema de Fermat tenemos que api−1 ≡ 1(mod pi) para todo a tal que
(a, n) = 1. Por lo tanto tenemos que, an−1 ≡ (api−1)ki ≡ (1)ki ≡ 1 ≡ api−1(mod pi).
Entonces, 1 ≡ api−1(mod pi) y an−1 ≡ api−1(mod pi) para todo i = 1, ..., t. Por el
teorema chino del residuo, an−1 ≡ 1(mod n) para todo a tal que (a, n) = 1. Y, por
lo tanto, n es un numero de Carmichael.
Ahora, si n es un numero de Carmichael, es decir, si λ(n) divide a (n− 1), veamos
que se cumplen (i) y (ii).
Primero veamos (i): Si λ(n) divide a (n − 1), entonces n y λ(n) no tienen factores
en comun. Como n es un numero compuesto e impar, entonces lo podemos escribir
de la forma: n = pα11 ...pαt
t , donde los pi son primos impares diferentes entre ellos, y
los αi son enteros positivos.
Si pi, αi > 1 para algun i, como λ(pαii ) = pαi−1
i (pi−1) y λ(n) = mcm(λ(pλ11 )...λ(pλt
t )),
entonces pi divide a λ(n). Llegamos a una contradiccion, y podemos concluir que si
n es un numero de Carmichael, es libre de cuadrados.
Ahora, veamos (ii): Por (i), n = p1p2...pt donde los pi son diferentes entre si. Tenemos
entonces: λ(n) = mcm((p1 − 1), ..., (pt − 1)), y por lo tanto (pi − 1) divide a λ(n)
para todo i = 1, ..., t. Pero como por hipotesis λ(n) divide a (n−1), entonces (pi−1)
divide a (n− 1) para todo i = 1, ..., t.
�
Se podrıa pensar que al ser libres de cuadrados los numeros de Carmichael,
9
0234
sera bastante difıcil encontrar pseudoprimos que no sean libres de cuadrados.
Propiedad 2.1.2. [11] Sea n un psp(a) y p un primo tal que pr divide a n, entonces,
ap−1 ≡ 1(mod pr).
Demostracion: Como pr divide a n, existe un entero t tal que n = prt.
Como n es un psp(a), an−1 ≡ 1(mod n) y por lo tanto an ≡ a(mod pr). Entonces:
ap−1 ≡ (an)p−1 = aprt(p−1) = (aφ(pr))tp ≡ 1(mod pr), donde φ es la funcion de Euler.
�
Para a fijo, las soluciones de ap−1 ≡ 1(mod p2) son escasas, de hecho, si tomamos
a = 2 y p < (3)(109) solamente hay 2 soluciones de 2p−1 ≡ 1(mod p2): p = 1093
y p = 3511 [11]. Esta propiedad nos dice, entonces, que en efecto la mayorıa de
los pseudoprimos son libres de cuadrados; de hecho, hasta el momento no se han
encontrado soluciones a 2p−1 ≡ 1(mod p3) [11]. En la Tabla 1, tomada de [11], se
muestran algunos de los pseudoprimos que no son libres de cuadrados y se indica si
son pseudoprimos fuertes o no (esta definicion la veremos mas adelante).
Numero Factorisacion spsp(2)1194649 10932 Si12327121 35112 Si3914864773 (29)(113)(10932) Si5654273717 (10932)(4733) Si6523978189 (43)(127)(10932) No22178658685 (5)(47)(79)(10932) No
Tabla 1: Lista de los pseudoprimos que no son libres de cuadrados, en base 2,menores que 25× 109
Si n = p1p2...pk donde los pi son diferentes entre ellos tenemos que: λ(n) =
mcm((p1 − 1), ..., (pk − 1)). El criterio de Korselt se puede, entonces, escribir de la
siguiente manera:
Criterio 2.1.1. [8] n = p1p2...pk es un numero de Carmichael si y solo si los pi son
diferentes y L = mcm(p1 − 1, p2 − 1, ..., pk − 1) divide a n− 1.
10
0234
Por ejemplo para verificar que 561 es un numero de Carmichael, tenemos que
mirar si L = 80 = mcm(2, 10, 16) divide a 560.
Veamos, a continuacion, algunas de las propiedades mas caracterısticas de los numeros
de Carmichael.
Teorema 2.1.3. [19] Un numero de Carmichael no puede ser el producto de dos
primos.
Demostracion: Sea n = pq un numero de Carmichael y tomemos sin perder
generalidad p > q: Segun el criterio de Korselet (p − 1) divide a (n − 1); es decir,pq−1p−1
es un entero. Pero pq−1p−1
= q + q−1p−1
, y como p > q, q−1p−1
no es un entero. Por lo
tanto, llegamos a una contradiccion.
�
Definicion 2.1.4 (Los numeros de Bernoulli). [2] Los numeros de Bernoulli Bn son
una sucesion de numeros racionales que cumplen:
x
ex − 1=
∞∑n=0
Bnxn
n!(3)
El siguiente teorema, es un corolario del teorema de Von Staudt-Clausen [2] y
solo se aplica para enteros n pares ya que si n es impar Bn = 0.
Teorema 2.1.4. [2] Sea denom(Bn) el denominador de Bn. Si n es par
denom(Bn) =∏
(p−1)|(n)
p
.
Propiedad 2.1.3. [11] Sea n un entero compuesto e impar. Entonces n es un
numero de Carmichael si y solo si divide al denominador del numero de Bernoulli
Bn−1.
11
0234
Demostracion: Supongamos que n es un numero de Carmichael, por lo tanto
n = p1p2...pk con los pi diferentes entre ellos, y para todo i = 1, ..., k, (pi − 1)
divide a (n − 1). Como n es impar, segun el teorema 2.1.4 (p. 11) denom(Bn−1) =∏(p−1)|(n−1) p = p1p2....pk−1pkq1...qt, con qj primo para j = 1, ..., t. Por lo tanto n
divide a denom(Bn−1).
Ahora, supongamos que n divide a denom(Bn−1). Si existe un primo p tal que
p2 divide a n entonces p2 divide a denom(Bn−1), lo cual no puede pasar ya que
denom(Bn−1) es libre de cuadrados por el teorema 2.1.4 (p. 11). Ahora, si n =
p1p2...pk con los pi diferentes entre ellos, como n divide a denom(Bn−1), entonces
denom(Bn−1) =∏
(p−1)|(n−1) p = p1p2....pk−1pkq1...qt, con qj primo para j = 1, ..., t,
asi que por el teorema 2.1.4 (p. 11): para todo i = 1, ..., k, (pi − 1) divide a (n− 1).
Por el criterio de Korselt n es un numero de Carmichael.
�
Es interesante saber cuando un numero es probablemente primo en una cierta
base a; sin embargo, es aun mas util saber si lo es en varias bases ya que esto
aumentarıa la probabilidad de ser primo, lo cual motiva el siguiente teorema.
Teorema 2.1.5. [9] Sea n = pα11 ...pαk
k un entero positivo. El numero de bases
a (mod n) para las cuales n es psp(a) es: Πi(n− 1, pi − 1).
Demostracion: El numero de bases a para las cuales n es psp(a) es el numero
de soluciones (mod n) de la congruencia:
f(x) = xn−1 − 1 ≡ 0(mod n) (4)
Primero consideremos las siguientes ecuaciones:
f(x) ≡ 0(mod pαii ) (5)
f(x) ≡ 0(mod pi) (6)
Segun el teorema 1.0.9 (p. 4), la congruencia (6) tiene si = (n − 1, pi − 1)
soluciones. Veamos si p divide a f ′(x) = (n− 1)xn−2: como p es primo, para dividir
a f ′(x) tiene que dividir a alguno de sus dos factores. Pero p no divide a (n − 1)
12
0234
ya que p divide a n, y tampoco divide a xn−2 ya que de ser ası: xn−2 ≡ 0(mod p)
y, por lo tanto, xn−1 ≡ 0(mod p), lo cual es falso ya que xn−1 ≡ 1(mod p). Como
f ′(x) no es congruente con 0(mod p), segun el lema de Hensel (p. 3), cada raız de
(6), corresponde a una raız de (5), por lo tanto (5) tiene tambien si soluciones . Y
segun el teorema 1.0.7 (p. 3), (4) tiene Πsisoluciones distintas.
�
Definicion 2.1.5. Llamamos Pa(x) a la cantidad de numeros psp(a) menores o
iguales a x.
En la tabla 2 (p.14) se puede ver que Pa(x) y Pb(x) tienen la misma razon de
crecimiento para cualquier par de bases a y b, cuando x tiende a infinito.
Hasta el momento, nadie ha mostrado que hay infinitos numeros simultaneamente
pseudoprimos en dos bases dadas, excepto el caso trivial en que las dos bases son
potencias de un mismo numero. Los datos de esta tabla apoyan la siguiente conje-
tura: para todo conjunto finito de bases, existen infinitos psp(a) simultanemanente
para cada a del conjunto. Segun los resultados de Pomerance, Selfridge y Wagstaff
se puede ver que entre mas grande sea el numero de bases para las cuales es pseudo-
primo un n dado, es mayor la probabilidad de que sea un numero de Carmichael.
Por ejemplo, mientras que solo el 10 % de lo psp(2) menores a 25× 109 son numeros
de Carmichael, el 89 % de los numeros que son pseudoprimos en las bases 2, 3, 5 y
7 son numeros de Carmichael.
Con el objeto de seguir aumentando la probabilidad de primalidad, vamos a
definir a continuacion los pseudoprimos de Euler, que notaremos epsp(a), y los
pseudoprimos fuertes, que notaremos spsp(a).
2.2. Los pseudoprimos fuertes y de Euler
El criterio de Euler es un resultado similar al pequeno teorema de Fermat, desde
el punto de vista que si un numero no cumple ciertas propiedades podemos afirmar
que es compuesto; sin embargo, si las cumple, no podemos asegurar que sea un
numero primo.
13
0234
Bases Primer ejemplo limites103 105 107 109 25× 109
2 341=11.31 3 78 750 5597 218533 91=7.13 5 76 749 - -5 217=7.31 3 66 726 - -7 25=5.5 5 69 651 - -
2,3 1105=5.13.17 0 23 187 1272 47092,5 561=3.11.17 1 16 159 1086 38972,7 561=3.11.17 1 11 125 970 35733,5 1541=23.67 0 14 137 - -3,7 703=19.37 1 13 141 - -5,7 561=3.11.17 1 9 112 - -
2,3,5 1729=7.13.19 0 11 95 685 25222,5,7 1105=5.13.17 0 7 90 688 24992,5,7 561=3.11.17 1 4 73 576 20463,5,7 29341=13.37.61 0 4 69 - -
2, 3,5,7 29341=13.37.61 0 3 63 501 1770
Tabla 2: Cantidad de pseudoprimos en las bases 2, 3, 5 y 7 inferiores a un lımitedado
14
0234
Criterio 2.2.1 (Criterio de Euler). [10] Si n es un primo impar y a un entero tal
que (a,n)=1, entonces
a(n−1)
2 ≡ (a
n)(mod n). (7)
Sabemos entonces que si n no cumple con la ecuacion (7), es un numero com-
puesto; sin embargo, si la cumple, no podemos afirmar que sea primo. Esto motiva
la siguiente definicion:
Definicion 2.2.1 (pseudoprimos de Euler). Un numero compuesto e impar es
epsp(a) si (a, n) = 1 y an−1
2 ≡ ( an)(mod n).
Por ejemplo, 1905, que de hecho es el mınimo epsp(2).
Ahora, sea p un primo impar y a tal que (a, p) = 1, entonces ap−1 ≡ 1(mod p) segun
el Pequeno Teorema de Fermat. En particular, si p = 2m + 1 tenemos:
a2m − 1 = (am − 1)(am + 1) ≡ 0(mod p).
Al ser p primo, debe dividir algunos de los 2 factores, sin embargo no puede dividir
a ambos, ya que de ser ası, dividirıa su diferencia (am + 1)− (am − 1) = 2, y al ser
p impar no divide a 2. Por lo tanto, am ≡ ±1(mod p).
Ahora, si en vez de tomar p como 2m + 1, tomamos la descomposicion 2Sd + 1 de p
y consideramos ap−1− 1 = (ad− 1)(ad +1)(a2d +1)...(a2(S−1)d +1), nos preguntamos
entonces que pasa si p divide exactamente a alguno de estos factores. Esto motiva
la siguiente definicion:
Definicion 2.2.2 (pseudoprimos fuertes). Sea n un numero compuesto e impar y
sea d un numero impar tal que (n− 1) = d2S entonces n es un spsp(a) si:
i) ad ≡ 1(mod n) o
ii) ad2R ≡ −1(mod n) para algun R en 0 ≤ R ≤ S.
Veamos algunos ejemplos: 2047 = 23 × 89, 121 = 112 y 781 = 11 × 71, son
pseudoprimos fuertes en base 2, 3 y 5, respectivamente.
El menor spsp en las bases 2, 3 y 5 es 2315031751 = 151× 751× 28351, el cual es
15
0234
un numero de Carmichael que es fuertemente pseudoprimo en las bases 2, 3, 5 y 7.
Sin embargo, estos numeros fuertemente pseudoprimos en varias bases son bastante
escasos; de hecho, en [11] vemos que este es el unico numero con estas propiedades
menor a 25× 109.
Definicion 2.2.3 (Los numeros de Mersenne). Un numero de Mersenne es un
numero de la forma Mn = 2n − 1 con n un entero.
Los numeros de Mersenne (llamados ası en honor al monje frances Marin Mersenne,
contemporaneo de Fermat, con el cual mantuvo una larga correspondencia) han ocu-
pado un puesto importante en el estudio de los numeros primos. Se han hecho varias
hipotesis del estilo: si n es un numero primo, Mn tambien lo es, lo cual es falso ya
que M11 = 2047 = (23)(89). Sin embargo, su reciproca es valida [12]. Otra conje-
tura posible es que Mn es un primo siempre y cuando n sea a su vez un numero
de Mersenne, lo cual tambien es falso ya que M13 es compuesto, por lo tanto MM13
tambien lo es.
Pierre de Fermat buscaba numeros que le ayudaran a comprobar la primalidad de
los numeros de Mersenne, en su busqueda vio que el pequeno teorema de Fermat era
util para encontrar los numeros primos (como lo vimos anteriormente) y sugirio que
los numeros de Fermat (que definiremos a continuacion) debıan ser primos, lo cual
demostro hasta n = 4; sin embargo, no pudo demostrarlo para n = 5, mas tarde
Euler mostro que F5 era divisible por 641.
Definicion 2.2.4 (Los numeros de Fermat). Un numero de Fermat es un numero
de la forma Fn = 22n+ 1 con n entero.
Es interesante ver, que estos numeros son pseudoprimos fuertes:
Propiedad 2.2.1. [11] Todo numero compuesto de Mersenne o de Fermat es un
spsp(2).
La demostracion de estas propiedades estan en [11]. Vimos que es falso decir que
si n es un numero primo Mn tambien lo es; sin embargo, a continuacion veremos
que si n es un psp(2), entonces Mn tambien lo es.
16
0234
Corolario 2.2.1. Si n es un psp(2), entonces 2n − 1 es un spsp(2).
Demostracion: Este resultado sale directamente de la propiedad anterior. Sin
embargo, daremos una prueba directa: sea N = 2n − 1, veamos que si n es un
psp(2), entonces N es un un numero compuesto. N es impar por definicion. Como
n es compuesto existen enteros b y c tales que n = bc. Como 2b ≡ 1(mod 2b − 1),
tenemos que 2n = 2bc ≡ 1(mod 2b − 1); es decir, 2b − 1 divide a N, y como b > 1 es
compuesto.
Ahora, veamos que N cumple la condicion (i) de la definicion 2.2.2 (p.15) (es decir
que si d es un numero impar tal que (N − 1) = d2S entonces 2d ≡ 1(mod N)).
Como n es un psp(2) entonces 2n−1 ≡ 1(mod n), por lo tanto existe algun entero t
tal que 2n−1 − 1 = nt; t es necesariamente impar ya que tanto n como 2n−1 − 1 son
impares. Multiplicando ambos lados por 2, encontramos que: N−1 = (2n−1)−1 =
2nt; es decir, que d = nt. Falta ver entonces que, en efecto, 2d ≡ 1(mod N), pero
2n ≡ 1(mod 2n−1) y entonces 2d = 2nt ≡ 1(mod 2n−1). En efecto N es un spsp(2).
�
2.3. La relacion entre los psp, los epsp, los spsp y losnumeros de Carmichael.
La figura 1 nos permite ver graficamente la relacion entre los psp, los epsp, los
spsp y los numeros de Carmichael. Al mismo tiempo nos muestra el menor numero
que pertenece a cada conjunto. Por ejemplo, 561 es el menor numero que cumple
con ser numero de Carmichael y pseudoprimo de Euler a la vez. 2821 es el menor
numero de Carmichael que no es ni pseudoprimo de Euler ni fuerte.
Teorema 2.3.1. spsp(a) ⊆ epsp(a) ⊆ psp(a).
Vamos a mostrar la segunda inclusion, la primera se puede consultar en [11].
Primero veamos que epsp(a) ⊆ psp(a): si n es un epsp(a) tenemos que an−1
2 ≡( a
n)(mod n), es decir an−1 = a
n−12 × a
n−12 ≡ ( a
n) × ( a
n) ≡ 1(mod n) ya que, como
(a, n) = 1,entonces ( an)(mod n) = ±1.
17
0234
Es interesante saber cuando un numero cumple los requisitos para ser fuerte-
mente pseudoprimo y a la vez numero de Carmichael, ya que va a tener una mayor
probabilidad de ser primo.
Veamos algunos teoremas tomados de [8] que muestran la relacion entre estos numeros.
Teorema 2.3.2. Si n ≡ 3(mod 4) y n es un epsp(a), entonces n es un spsp(a).
Demostracion: Si n ≡ 3(mod 4), tenemos que existe un d impar tal que: n−1 =
d21 . Como n es un epsp(a), sabemos que ad ≡ ( an)(mod n) con ( a
n) igual a 1 o -1
ya que (a, n) = 1.
Si ( an) = 1 , se cumple la primera condicion de la definicion 2.2.2 (p.15).
De lo contrario, ( an) = −1 y si tomamos a R = 0, se cumple la segunda condicion
de la definicion 2.2.2 (p.15). Ası que n es un spsp(a).
�
�
�
�
�
�
�
�
�341
1905
2047
561
15841spsp(2)
epsp(2)
psp(2)
2821
Carmichael
Figura 1: La relacion entre los psp, los epsp, los spsp y los numeros de Carmichael
Teorema 2.3.3. Si n es un epsp(a) y ( an) = −1, entonces n es un spsp(a).
18
0234
Demostracion: Como n es impar, existe un d tal que n− 1 = d2S, por lo tanto
ad2S−1= a
n−12 ≡ ( a
n) = −1(mod n). Se cumple, ası, la segunda condicion de la
definicion 2.2.2 (p.15) y n es un spsp(a).
�
2.4. La densidad de los numeros de Carmichael
En la primera parte de este capıtulo vimos que encontrar ejemplos de numeros
de Carmichael fue un problema abierto durante mucho tiempo, lo cual sugiere que
estos numeros son bastante raros.
Definicion 2.4.1. Llamamos C(x) a la cantidad de numeros de Carmichael menores
o iguales a x.
En la Tabla 3, tomada de [14] se muestra la evolucion de los calculos de C(x) en
el tiempo.
x C(x) Ano Descubridor(es)103 1 1910 Carmichael104 7 1912 Carmichael105 16106 43107 105108 255 1938 Poulet109 646 1975 Swift1010 15472,5× 1010 2163 1980 pomerance, selfridge,Wagstaff1011 36051012 8241 1990 Jaeschke1013 192791014 447061015 105212 1992 Pinch
Tabla 3: La evolucio de C(x) en el tiempo
Una vez se supo que existıan tales numeros, la pregunta fue si eran infinitos, y
buscar metodos que los generaran. La ultima definicion de los numeros de Carmichael
19
0234
que vimos (Criterio 2.1.1 (p. 10)), sirve para verificar si algun numero es, o no, de
Carmichael; por ejemplo, para ver si 1105, 1729, 2465, 2821, 41041, 825265 lo son,
falta ver que L = 48 divide a 1104, L = 36 divide a 1728, L = 112 divide a 2464,
L = 60 divide a 2820, L = 120 divide a 41040 y finalmente que L = 144 divide a
825264. Segun estos ejemplos, uno pensarıa que L debe ser mucho menor que (n−1),
sin embargo para un n arbitrario, esto no es obligatorio.
Para construir los numeros de Carmichael, la idea que se tenıa era tratar de
forzar que L fuera mucho menor que (n− 1), tomando los primos pi de manera que
los pi − 1 tuvieran muchos factores en comun.
En 1956, Erdos cambio la forma de aproximarse al problema y en vez de escoger
primos que minimizaran L, escogio un L tal que existieran muchos primos pi que no
dividieran a L, pero cada pi − 1 si lo dividiera.
Una vez obteniendo el conjunto de los pi que cumplen estas condiciones, se selec-
ciona un subconjunto tal que n = p1p2...pk ≡ 1(mod L), y entonces por el Criterio
2.1.1 (p. 10), n es un numero de Carmichael.
Veamos a continuacion el ejemplo de construccion de un numero de Carmichael,
dado por Granville en [14]. Si L = 120, los primos pi que no dividen a L y tales que
pi− 1 si lo hace son: 7,11,13,31,41 y 61. Revisando todas las combinaciones de estos
primos cuyo producto sea congruente con 1 modulo L, encontramos:
41041 = 7× 11× 13× 41 ≡ 1(mod 120), 172081 = 7× 13× 31× 61 ≡ 1(mod 120) y
852841 = 7× 11× 31× 41× 61 ≡ 1(mod 120), por lo tanto 41041, 172081 y 852841
son numeros de Carmichael.
Si al realizar esta construccion para un L determinado se encuentran r primos
diferentes, va a haber 2r − 1 productos posibles entre ellos. Si asumimos que 1L
de
estos productos es congruente con 1 modulo L, vamos a tener aproximadamente 2r
L
numeros de Carmichael nuevos. Erdos hizo un razonamiento parecido para un L
bastante grande, e hizo la siguiente hipotesis: C(x) > x1−ε, para cualquier ε > 0 fijo
y x lo suficientemente grande.
20
0234
Sin embargo esta hipotesis no fue acogida por todo el mundo, de hecho Dan
Shanks, en su libro “Solved and unsolved problems in number theory”, reto a los
seguidores de Erdos a encontrar un x tal que C(x) > x12 .
En 1992, Alford, Granville y Pomerance [6] demostraron que C(x) > x27 , si x es lo
suficientemente grande, y dieron argumentos suficientes para convencer, incluso al
propio Shanks. Se puede responder al desafio de Shanks extrapolando C(x)ln(x)
, y por lo
tanto x debe ser aproximadamente 1060; sin embargo, no es factible escribir todos
los numeros de Carmichael hasta este punto.
Nos interesa, pues, hacer un estudio de la densidad de C(x), ya que si limx→∞C(x)π(x)
=
0 entonces un numero muy grande que cumpla las condiciones para ser de Carmichael,
es muy probable que sea primo.
En 1956, Paul Erdos [13] demostro que
C(x) < x exp(−c lnxln3x
ln2x) (8)
donde c es una constante positiva, y x es lo suficientemente grande.
En [11] se demuestra que para cada ε > 0 existe un entero x0(ε) tal que para
todo x > x0(ε)
C(x) < F (x) = x exp(−(1− ε)lnxln3x
ln2x). (9)
Y los autores retoman el argumento heurıstico de Erdos, que asegura que si ε > 0 y
para todo x > x0(ε), entonces:
C(x) > x exp(−(2 + ε)lnxln3x
ln2x). (10)
Estas dos ecuaciones sugieren, ası, que existe una funcion, que llamamos k(x), tal
que
C(x) = x exp(−k(x)lnxln3x
ln2x). (11)
21
0234
Trataron, tambien, de aproximar C(x) a una funcion del tipo Kxu, y encontraron
que G(x) = 0,15x0,4 cuadra bastante bien para los valores de C(x) conocidos.
En la tabla 4, vemos una comparacion de C(x) con F (x) y G(x) (dadas anterior-
mente), que nos permite concluir que estas aproximaciones son bastante buenas.
x C(x) F (x) G(x) C(x)F (x)
C(x)G(x)
k(x)
104 7 6 6 1,21 1,17 2,1955105 16 13 15 1,20 1,07 2,0763106 43 32 38 1,33 1,14 1,9795107 105 81 95 1,30 1,11 1,9339108 255 208 238 1,23 1,07 1,9049(5)(108) 469 408 453 1,15 1,04 1,8920109 646 547 597 1,18 1,08 1,87995× 109 1184 1090 1137 1,09 1,04 1,87221010 1547 1470 1500 1,05 1,03 1,86871,5× 1010 1782 1753 1764 1,017 1,010 1,86862× 1010 1983 1986 1979 0,998 1,002 1,86782,5× 1010 2163 2189 2164 0,9882 0,9995 1,8668
Tabla 4: Dos aproximaciones de C(x)
Definicion 2.4.2. Llamamos Ea(x) y Sa(x) a la cantidad de numeros epsp(a) y
spsp(a), respectivamente, menores o iguales a x.
Segun el Teorema 2.3.1 (p. 17), spsp(a) ⊆ epsp(a) ⊆ psp(a), y por lo tanto ten-
emos que Sa(x) ≤ Ea(x) ≤ Pa(x) y C(x) ≤ P2(x), ya que para ser un numero de
Carmichael n tambien debe ser pseudoprimo en base 2.
En la tabla 5 [11] podemos ver los valores de P2(x), E2(x), S2(x) y C(x), segun
el valor de x. E2(x) − S2(x) corresponde a los numeros que son pseudoprimos de
Euler pero que no son pseudoprimos fuertes.
En la tabla 6 (basada en los datos encontrados en [15]) vemos como se comportan
C(x) y P2(x) con respecto a π(x).
Vemos entonces que en efecto limx→ınfP2(x)π(x)
= 0 y limx→ınfC(x)π(x)
= 0, por lo tanto
un numero que cumpla las condiciones para ser un numero de Carmichael es muy
probable que sea primo, lo cual motiva la siguiente definicion.
22
0234
x P2(x) E2(x) E2(x)− S2(x) S2(x) C(x)103 3 1 1 0 1104 22 12 7 5 7105 78 36 20 16 16106 245 114 68 46 43107 750 375 213 162 105108 2057 1071 583 488 255109 5597 2939 1657 1282 6461010 14884 7706 4415 3291 154725× 109 21853 11347 6505 4842 2163
Tabla 5: Los valores de P2(x), E2(x), S2(x) y C(x), segun el valor de x
x P2(x) C(x) π(x) P2(x)π(x)
C(x)π(x)
103 3 1 168 (1,79)(10−2) (5,95)(10−3)104 22 7 1229 (1,79)(10−2) (5,70)(10−3)105 78 16 9592 (8,13)(10−3) (1,67)(10−3)106 245 43 78498 (3,12)(10−3) (5,48)(10−4)107 750 105 664579 (1,12)(10−3) (1,58)(10−4)108 2057 255 5761455 (3,57)(10−4) (4,43)(10−5)109 5597 646 50847534 (1,1)(10−4) (1,27)(10−5)1010 14884 1547 455052511 (3,27)(10−5) (3,40)(10−6)1011 38975 3605 4118054813 (9,46)(10−6) (8,75)(10−7)1012 101629 8241 37607912018 (2,70)(10−6) (2,19)(10−7)1013 264239 19279 346065536839 (7,64)(10−7) (5,57)(10−8)
Tabla 6: Comportamiento de C(x) y P2(x) con relacion a π(x)
23
0234
Definicion 2.4.3. A los numeros que cumplan (2) (p. 5) (compuestos o no) los
llamamos probablemente primos en base a, lo cual notamos prp(a).
A los numeros compuestos o no que cumplan las demas condiciones para ser epsp(a)
o spsp(a) los llamamos, respectivamente, probablemente primos de Euler y probable-
mente primos fuertes en base a, lo cual notamos eprp(a) y sprp(a).
Para saber si un numero n dado es primo, se divide por todos los numeros primos
menores a√
n, sin embargo, si el numero es muy grande, este proceso es muy largo
de realizar. Utilizando lo visto en este capıtulo, podrıamos disenar un algoritmo mas
eficiente para determinar si un numero es primo.
Sea n un numero dado, primero veamos si algun numero primo menor a 1000 (por
ejemplo) lo divide, de ser ası ya sabemos que n es un numero compuesto, de lo con-
trario no podemos afirmar nada. Luego veamos si para algunas bases ai fijas (por
ejemplo 2, 3 y 5) n es un prp(ai); si no lo es afirmamos que es un numero compuesto.
De lo contrario, miramos si para algunas bases (bi) aleatorias n es un prp(bi). De
ser ası; podrıamos afirmar con una buena probabilidad (segun las tablas dadas an-
teriormente), que n es un numero primo. Es mas, podrıamos mejorar este algoritmo
exigiendo que sean probablemente primos fuertes (este algoritmo es conocido como
el “test de Rabin-Miller”).
Otro algoritmo presentado en [11] es el siguiente: primero verificar si n es prp(a)
para a=2, 3 y 5. De ser ası, verificar si el numeros aparece en la siguiente tabla;
si aparece es compuesto, si no, es primo. Este algoritmo nos permite concluir, con
total certeza para los numeros menores a 25× 109; para los que sean mayores, solo
se puede decir que hay una alta probabilidad de que sea primo.
En la tabla 7 vemos los numeros que son pseudoprimos, simultaneamente, en las
bases 2, 3 y 5 menores a 25× 109, y vemos si son pseudoprimos en las bases 7, 11 y
13, y si son numero de Carmichael (Car).
(k + 1)(4k + 1), cuando 4k + 1 = (m + 1)(5m + 1) (12)
24
0234
numero psp(7) psp(11) psp(13) Car factorisacion FormaA 25 326001 No No No No 2251.11251 (k + 1)(5k + 1)B 161 304001 No spsp No No 7333.21997 (k + 1)(3k + 1)C 960 946321 No No No No 11717.82013 (k + 1)(7k + 1)D 1157 839381 No No No No 24061.48121 (k + 1)(2k + 1)E 3215 031751 spsp psp psp Si 151.751.28351 (12)F 3697 278427 No No No No 30403.121609 (k + 1)(4k + 1)G 5764 643587 No No spsp No 37963.151849 (k + 1)(4k + 1)H 6770 832367 No No No No 41143.164569 (k + 1)(4k + 1)I 14386 156093 psp psp psp Si 397.4357.8317 (13)J 15579 919981 psp spsp No No 88261.176521 (k + 1)(2k + 1)K 18459 366157 No No No No 67933.271729 (k + 1)(4k + 1)L 19887 974881 psp No No No 81421.244261 (k + 1)(3k + 1)M 21276 028621 No psp spsp No 103141.206281 (k + 1)(2k + 1)
Tabla 7: Los numeros fuertemente pseudoprimos simultaneamente en las bases 2, 3y 5 menores a 25× 109
En el caso E: k = 28350, y m = 150.
(k + 1)(208k + 1), cuando 208k + 1 = (m + 1)(11m + 1) (13)
En el caso I: k = 8316, y m = 396.
De la tabla anterior, podemos resaltar que los numeros menores a 25×109 que son
pseudoprimos simultaneamente en las bases 2, 3 y 5 son de la forma (k + 1)(rk + 1)
donde r es un numero pequeno y k +1 un primo. Esto sugiere que de ser compuesto
el numero n podrıa factorizarse de esta forma.
El algoritmo usado por Maple V.2 para saber si un numero n dado es o no primo,
explicado por Arnault [8], se basa en lo visto en este capıtulo y es el siguiente:
Paso 1: primero verifica que n no tenga divisores primos menores que 1000.
Paso 2: Verifica si n es sprp en las bases 2, 3, 5, 7, 11 (si uno lo pide explıcitamente,
puede hacer esta verificacion en mas bases).
Paso 3: verifica que n no sea de la forma:
(k + 1)(r k2
+ 1) con 3 ≤ k ≤ 9 o
(k + 1)(rk + 1) con 5 ≤ k ≤ 20
25
0234
El problema de estos algoritmos es que al ser n pseudoprimo en mas de un
cierto numero de bases, es muy probable que sea un numero de Carmichael y, por lo
tanto, al aumentar el numero de bases, no aumentarıa la probabilidad de ser primo.
Serıa interesante tener otro criterio independiente al dado anteriormente, que nos
permitiera ver si un numero es, o no, primo para poder combinarlos y tener una
mejor probabilidad.
26
0234
Capıtulo III
Los numeros pseudoprimos de Lucas
En el capıtulo anterior tomamos propiedades que cumplen los numeros primos,
tales como el pequeno teorema de Fermat, y vimos que pasaba cuando algunos
numeros compuestos las cumplıan, definiendo ası los numeros probablemente pri-
mos. Analogamente, en este capıtulo definimos los pseudoprimos de Lucas, veremos
algunas de sus propiedades y, finalmente, estudiaremos su densidad.
3.1. Los pseudoprimos de Lucas
Edouard Lucas desarrollo un metodo para estudiar la primalidad de los numeros
de Mersenne (definidos anteriormente), el cual le permitio probar en 1876 que 2127−1
es un numero primo (de hecho fue el mayor primo conocido hasta mediados del siglo
XX, y es el mayor que ha sido encontrado sin la ayuda de un computador). Este
metodo fue retomado por Derrik Henry Lehmer en 1930 y es el siguiente [4]:
Sean s2 = 4, s3 = 14, s4 = 194, ..., donde sn = s2n−1 − 2. Dado un numero de
Mersenne Mp = 2p − 1 con p > 2 primo, Mp es primo si y solo si sp es divisible por
Mp.
Lucas tambien se intereso en la sucesion definida por Leonardo de Pisa (Fibonac-
ci), a la cual denomino la “sucesion de Fibonacci” y que definiremos a continuacion:
Definicion 3.1.1 (Sucesion de Fibonacci). Es la sucesion definida por: F (0) = 0,
F (1) = 1 y F (n) = F (n− 1) + F (n− 2) si n ≥ 2.
Esta sucesion tiene bastantes propiedades muy interesantes tales como [4]:
27
0234
limn→ınfF (n+1)
F (n)= φ, donde φ es el numero aureo.
Cualquier numero natural se puede escribir mediante la suma de un numero
limitado de terminos de la sucesion de Fibonacci, cada uno de ellos distinto a
los demas. Por ejemplo, 17=13+3+1, 65=55+8+2.
Tan solo un termino de cada tres es par, uno de cada cuatro es multiplo de 3,
uno de cada cinco es multiplo de 5, etc. Esto se puede generalizar, de forma
que la sucesion de Fibonacci es periodica en las congruencias modulo m, para
cualquier m.
Si F(p) es un numero primo, p tambien es primo, con una unica excepcion:
F(4)=3.
La suma infinita de los terminos de la sucesion F (n)10n es exactamente 10
89.
Lucas se intereso en este tipo de sucesiones y de hecho a cierta sucesion que
utiliza la misma recursion que la de Fibonacci pero con valores iniciales diferentes,
se le llamo los numeros de Lucas en su honor.
Definicion 3.1.2 (Numeros de Lucas L(n)). Es la sucesion definida por: L(0) = 2,
L(1) = 1 y L(n) = L(n− 1) + L(n− 2) si n ≥ 2.
Los numeros de Lucas tienen tambien propiedades muy interesantes y bastante
parecidas a las de la sucesion de Fibonacci, tales como [1]:
limn→ınfF (n+1)
F (n)= φ, donde φ es el numero aureo.
Si L(p) es un numero primo, p tambien es primo, el recıproco es falso.
L(n) = F (n− 1) + F (n + 1) para todo entero n.
5F (n) = L(n− 1) + L(n + 1) para todo entero n.
F (2n) = L(n)F (n) para todo entero n.
Lucas encontro una formula para hallar F (n), sin tener que calcular los terminos
anteriores:√
5F (n) = (1+√
52
)n − (1−√
52
)n, lo cual facilito el estudio de esta serie. A
continuacion veremos una demostracion de esta ecuacion:
28
0234
Teorema 3.1.1. [16] Suponga que an satisface la recursion de segundo orden an =
c1an−1 + c2an−2, donde c1 y c2 son constantes y c2 6= 0. Sean r1 y r2 las dos raıces
de r2 − c1r − c2 = 0, y asumamos r1 6= r2. Entonces an = Arn1 + Brn
2 para alguna
constante A y B. Y recıprocamente, an = Arn1 + Brn
2 satisface la recursion definida
anteriormente.
Como F (n) = F (n−1)+F (n−2), entonces c1 = 1 y c2 = 1. Las raıces de r2−r−1 = 0 son: r1 = 1+
√5
2y r2 = 1−
√5
2. Por lo tanto F (n) = A(1+
√5
2)n +B(1−
√5
2)n. Como
0 = F (0) = A + B, tenemos que A = −B , y como 1 = F (1) = A(1+√
52
) + B(1−√
52
),
tenemos que 1 = A(1+√
52
) − A(1−√
52
) =√
5A. Por lo tanto A = 1√5
y B = − 1√5
y
probamos entonces que en efecto√
5F (n) = (1+√
52
)n − (1−√
52
)n.
La cantidad de propiedades interesantes de estos numeros nos motivan a gener-
alizar estas sucesiones, las cuales reciben el nombre de sucesiones de Lucas:
Definicion 3.1.3 (Las sucesiones de Lucas). [9] Sean D,P y Q enteros, tales que
D = P 2 − 4Q 6= 0 y P > 0. Sean U0 = 0 y U1 = 1 y V0 = 2 y V1 = P , definimos
recursivamente las series de Lucas para k ≥ 2:
Uk = PUk−1 −QUk−2 y Vk = PVk−1 −QVk−2.
Estas dos sucesiones tienen la misma recursion, y lo unico que cambia son las
condiciones iniciales. La de Uk son las mismas que en la serie de Fibonacci y las de Vk
son las mismas que para los numeros de Lucas. Vale al pena notar que, tambien, se
pueden calcular los valores de Uk, con k un entero negativo, de la siguiente manera:
Uk = PUk+1−Uk+2
Q, ası por ejemplo U−1 = PU0−U1
Q= −1
Q. Se puede hacer lo mismo
para Vk. A continuacion veremos algunas propiedades de estas sucesiones.
Propiedad 3.1.1. [9] Sean α y β las dos raıces de x2 − Px + Q = 0. Para k ≥ 0
tenemos que Uk = αk−βk
α−βy Vk = αk + βk.
Demostracion: Primero veamos que para k ≥ 0 tenemos que Uk = αk−βk
α−β. Segun
el teorema 3.1.1 (p.29), Uk = A(α)k + B(β)k. Encontremos A y B: 0 = U0 = A + B,
entonces A = −B, y como 1 = U1 = Aα + Bβ = A(α − β) entonces A = 1α−β
y
29
0234
B = − 1α−β
. Por lo tanto, tenemos Uk = αk−βk
α−β.
Ahora veamos que Vk = αk +βk. Segun el teorema 3.1.1 (p.29), Vk = A(α)k +B(β)k.
Encontremos A y B: 2 = U0 = A + B, entonces B = 2 − A, y como P = U1 =
Aα + Bβ = Aα + (2− A)β = A(α− β) + 2β, entonces A = P−2βα−β
. Pero α = P+√
D2
,
β = P−√
D2
, α − β =√
D y P − 2β =√
D, por lo tanto A = 1 y B = 2 − 1 = 1.
Entonces Vk = αk + βk.
�
Propiedad 3.1.2. Para todo par de enteros, a y b tenemos:
Ua+b = UaVb + QaUb−a.
Demostracion: Ua+b = αa+b−βa+b
α−βentonces Ua+b = (αa−βa)(αb+βb)
α−β+ (αaβa)(αb−a−βb−a)
α−β
es decir Ua+b = UaVb+αaβaUb−a y como αβ = Q, tenemos que Ua+b = UaVb+QaUb−a.
�
Propiedad 3.1.3. Para todo par de enteros, a y b tenemos:
1. U2a = UaVa
2. DU2a = V2a − 2Qa
3. V 2a −DU2
a = 4Qa
4. 2Va+b = VaVb + DUaUb.
Demostracion: Podemos ver que α− β =√
D y αβ = Q.
1. UaVa = (αa−βa
α−β)(αa + βa) = α2a−β2a
α−β= U2a.
2. DU2a = D(αa−βa
α−β)2 = (αa − βa)2 = α2a + β2a − 2(αβ)a = V2a − 2Qa.
3. V 2a −DU2
a = (αa + βa)2 −D(αa−βa
α−β)2 = (αa + βa)2 − (αa − βa)2 = 4Qa.
4. VaVb + DUaUb = (αa + βa)(αb + βb) + (αa − βa)(αb − βb) = 2Va+b.
�
30
0234
Propiedad 3.1.4. Para todo par de enteros a y b tenemos:
2Ua+b = UaVb + UbVa (14)
2QbUa−b = UaVb − UbVa (15)
Demostracion:
UaVb + UbVa = (αa−βa
α−β)(αb + βb) + (αb−βb
α−β)(αa + βa) = (2αa+b−2βa+b
α−β) = 2Ua+b
UaVb−UbVa = (αa−βa
α−β)(αb+βb)−(αb−βb
α−β)(αa+βa) = 2(αaβb−αbβa
α−β) = 2(αa−bαbβb−αbβa−bβb
α−β) =
2αbβb(αa−b−βa−b
α−β) = 2QbUa−b
�
Para facilitar la escritura de la formulas, vamos a utilizar la siguiente definicion:
Definicion 3.1.4. [9] Para todo entero n, ε(n) = (Dn), donde (D
n) es el sımbolo de
Jacobi, y δ(n) = n− ε(n)
Nota: δ(n) solo puede tomar los valores n− 1, n o n+1, ya que ε(n) es -1, 0 o 1.
El teorema que veremos a continuacion es el equivalente, en este capıtulo, al pequeno
teorema de Fermat en el capıtulo anterior.
Teorema 3.1.2. [9] Si p es un numero primo tal que (p, Q) = 1, entonces
Uδ(p) ≡ 0(mod p). (16)
Demostracion: La siguiente demostracion esta basada en el teorema (4.12 p.202
de [18]). Sabemos que Un = αn−βn√
D, αn = (P+
√D
2)n, y βn = (P−
√D
2)n.
Usando la expresion binomial obtenemos 2n√
DUn = (P +√
D)n − (P −√
D)n =∑nk=0
(nk
)P n−k(D
k2 − (−1)kD
k2 ) = 2
∑nk=0,kimpar
(nk
)P n−kD
k2 . Por lo tanto Un =
21−n∑n
k=0,kimpar
(nk
)P n−kD
k−12 . Los posibles valores de δ(p) son p-1, p y p+1 de-
pendiendo de (Dp).
Si δ(p) = p: entonces (Dp) ≡ 0(mod p). Pero
(pk
)= p!
k!(p−k)!≡ 0(mod p) si 1 ≤ k ≤ p−1
ası que Uδ(p) = Up = 21−p∑p
k=0,kimpar
(pk
)P p−kD
k−12 ≡ D
p−12 ≡ 0(mod p).
Si δ(p) = p + 1: entonces (Dp) ≡ −1(mod p). Nuevamente
(p+1k
)= (p+1)!
k!(p+1−k)!≡
31
0234
0(mod p) si 2 ≤ k ≤ p−1 ası que Uδ(p) = Up+1 = 21−(p+1)∑p+1
k=1,kimpar
(p+1k
)P p+1−kD
k−12 ≡
2−p((p + 1)P p + (p + 1)PDp−12 ≡ 2−1P (1 + D
p−12 ) ≡ 2−1P (1 + (D
p)) ≡ 0(mod p)).
Si δ(p) = p−1: entonces (Dp) ≡ 1(mod p). Ahora, por definicion Up+1 = PUp−QUp−1
ası que QUp−1 = PUp − Up+1 ≡ P (DP
)− 2−1P (1 + (DP
)) ≡ P − 2−1P (2) ≡ 0(mod p),
pero como (p, Q) = 1 entonces Uδ(p) = Up−1 ≡ 0(mod p).
�
Nos preguntamos que pasa si n cumple la condicion (16) pero no es primo, esto
motiva la siguiente definicion:
Definicion 3.1.5 (Numeros pseudoprimos de Lucas). [9] Un numero compuesto n
es pseudoprimo de Lucas con parametros P y Q (los cual notamos lpsp(P,Q) o a
veces lpsp(P,Q,D)) si Uδ(n) ≡ 0(mod n).
Por ejemplo 341 es un lpsp(7,2).
Teorema 3.1.3. [9] Sea p un numero primo tal que (p, Q) = 1, entonces las sigu-
ientes congruencias son validas:
Vδ(p) ≡ 2Q1−ε(p)
2 (mod p) si(p, D) = 1 (17)
Up ≡ ε(p)(mod p) (18)
Vp ≡ V1 = P (mod p). (19)
Ası como en el capıtulo 2 estudiamos la cantidad de bases a para las cuales un
numero n dado era psp(a), vamos a calcular a continuacion, para un D dado, la
cantidad de parejas (P, Q) tales que n es un lpsp(P, Q).
Teorema 3.1.4. [9] Sea D un entero. Sea n = Πpαii , un numero entero positivo e
impar tal que (n,D) = 1. El numero de valores distintos de P, modulo n, para los
cuales existe un Q tal que P 2 − 4Q ≡ D(mod n) y n es un lpsp(P,Q) es :
Πi((δ(n), δ(pi))− 1).
32
0234
Para la demostracion de este teorema, necesitamos los siguientes resultados pre-
liminares:
Definicion 3.1.6 (Rango de aparicion de p). [9] Sea p un primo impar tal que
(p, Q) = 1. Entonces w(p) = w(p; P, Q) denota el menor entero k tal que p divide a
Uk, al cual llamamos el rango de aparicion de p en la serie de Lucas Uk(P, Q).
Nota: El rango existe para todo primo p, ya que segun el teorema 3.1.2 (p.31)
Uδ(p) ≡ 0(mod p), ası que w(p) ≤ δ(p).
Propiedad 3.1.5. Sea p, un primo impar tal que (p, Q) = 1, entonces
p|Uk si y solo si w(p)|k.
Demostracion: esta demostracion esta basada en [17]. Sea K = {k | (p|Uk)},por definicion w(p) es el menor elemento de K. Como (p, Q) = 1 segun (14) y (15)
(p.31), si p|Ur y p|Us entonces p|Ur+s y p|Ur−s. Es decir, si r, s ∈ K, entonces r + s
y r − s tambien pertenecen a K.
Sea S = {k | (w(p)|k)}, veamos que S ⊆ K: ∀s ∈ S existe un entero A tal que
s = Aw(p) = w(p) + w(p) + ... + w(p). Como w(p) ∈ K entonces s ∈ K, y por lo
tanto S ⊆ K.
Ahora, supongamos que S 6= K, es decir, que existe un q ∈ K tal que q /∈ S. Como
q /∈ S, existen enteros A y B tales que q = Aw(p) + B, con B < w(p). Como
Aw(p) ∈ S entonces Aw(p) ∈ K y por lo tanto q − Aw(p) = B ∈ K; lo cual es una
contradiccion, ya que de ser ası w(p) no serıa el menor elemento de K, por lo tanto
S = K.
�
Propiedad 3.1.6. [9] Sea n un entero, y p un primo impar tal que (p, Q) = 1 y p|nentonces: w(p)|δ(n) si y solo si w(p)|(δ(n), δ(p)).
Demostracion: Por el teorema 3.1.2 (p.31), Uδ(p) ≡ 0(mod p), es decir, p|Uδ(p),
lo cual es equivalente segun la propiedad 3.1.5 a w(p)|δ(p). Ası que si w(p)|δ(n),
entonces w(p)|(δ(n), δ(p)), y si w(p)|(δ(n), δ(p)) tenemos que w(p)|δ(n).
33
0234
�
El siguiente teorema es de H.C.Williams, y lo retoman Baillie y Wagstaff en [9]:
Teorema 3.1.5. Sea p un primo, si d|δ(p) y d > 1 entonces hay φ(d) valores de P
modulo p diferentes entre si, tales que w(p)=d.
Demostracion del teorema 3.1.4 (p.32)(basada en la demostracion dada en
[9]). Supongamos que pα divide a n, con p un primo impar. Primero encontremos
B(p) el numero de valores distintos de P modulo p, para los cuales existe un Q tal
que P 2 − 4Q ≡ D(mod n) y n sea un lpsp(P, Q), es decir Uδ(n) ≡ 0(mod n).
Segun las propiedades 3.1.5 y 3.1.6 (p.33), p|Uδ(n) si y solo si w(p)|δ(n), si y solo
si w(p)|(δ(n), δ(p)). Segun el teorema 3.1.5 (p.34), si d|δ(n) y d > 1 entonces hay
φ(d) valores distintos de P modulo p tales que w(p) = d. Y como U1 = 1, para
ningun P se tiene w(p) = 1, entonces B(p) =∑
d|(δ(n),δ(p)),d>1 φ(d) = (δ(n), δ(p))− 1
segun el teorema 1.0.10 (p.4).
Ahora, como Uk(P, D) = αk−βk
α−β, α = P+
√D
2y β = P−
√D
2, entonces α − β =
√D
y αk − βk = (P+√
D)k−(P−√
D)k
2k .
Si k es par: (P +√
D)k − (P −√
D)k = 2∑ k
2r=0
(k
2r+1
)P k−2r−1Dr
√D, por lo tanto
Uk(P, D) = 12k−1
∑ k2r=0
(k
2r+1
)P k−2r−1Dr.
Sea Tk(x) =∑ k
2r=0
(k
2r+1
)xk−2r−1Dr. Tenemos entonces que Uk(P, D) = 2−(k−1)Tk(P ),
es decir, Uδ(n)(P, D) = 2−(δ(n)−1)Tδ(n)(P ).
Si k es impar: (P +√
D)k − (P −√
D)k = 2∑ k−1
2r=0
(k
2r+1
)P k−2r−1Dr
√D, y Tk(x) =∑ k+1
2r=0
(k
2r+1
)xk−2r−1Dr; aquı tambien tenemos Uk(P, D) = 2−(k−1)Tk(P ).
Por lo tanto B(p), que es el numero de valores distintos de P , modulo p, para los
cuales Uδ(n) ≡ 0(mod p), es el numero de raıces de Tδ(n)(x) modulo p, pues p es
impar y no divide a 2δ(n)−1.
Veamos ahora que B(p) = B(pα). Segun el lema de Hensel (p.3), esto es cierto
si p no divide la derivada de Tδ(n)(x).
Primero encontremos T ′k(x), la derivada de Tk(x) con respecto a x, suponiendo que
34
0234
k es par ya que lo que nos interesa es hallar Uδ(n), y por lo tanto Tδ(n)(P ), donde
δ(n) = n− ε(n) con n impar y ε(n) = ±1.
T ′k(x) =
∑ k2r=0
(k
2r+1
)(k − 2r − 1)xk−2r−1−1Dr, por lo tanto
T ′k(x) =
∑ k−1+12
r=0 k(
k−12r+1
)xk−1−2r−1Dr = kTk−1(x).
Ahora, supongamos que T ′δ(n)(x) = δ(n)Tδ(n)−1(P ) ≡ 0(mod p). Como p es primo
divide a δ(n) o a Tδ(n)−1(P ). Como p|n, entonces p no divide a n + 1 ni a n− 1, es
decir p - δ(n).
Supongamos entonces que p|Tδ(n)−1(P ), y por lo tanto p|Uδ(n)−1(P ). Como n es lpsp,
entonces Uδ(n)(P, Q) ≡ 0(mod p), y por definicion Uδ(n) = PUδ(n)−1 −QUδ(n)−2, por
lo tanto p|(Uδ(n)(P )− Puδ(n)−1(P ); es decir, p|QUδ(n)−2.
Esto implica que p|Q o p|Uδ(n)−2:
Si p|Uδ(n)−2 entonces, por definicion de Uk, p va a dividir a todos los Uk con k < δ(n),
lo cual es falso si k = 1. Por lo tanto si P |Tδ(n)−1(P ) tenemos que p|Q.
Ahora si p|Q y p|P , por la definicion de d, p|D, y esto no puede ser cierto, ya que
(n,D) = 1. Y si p|Q y p - P , p - Uk para todo k ≥ 1, n no es un lpsp y tampoco nos
sirve.
Entonces p no divide a Tδ(n)−1(P ), y por lo tanto T ′δ(n)(x) no es congruente con cero
modulo p, tenemos entonces que B(p) = B(pα) = (δ(n), δ(p))− 1. Segun el teorema
1.0.7 (p.3), Tδ(n)(x) tiene Πi((δ(n), δ(pi))− 1) raıces modulo n.
�
Al igual que para los pseudoprimos definidos anteriormente, podemos dar las
siguientes definiciones.
Definicion 3.1.7 (Numeros pseudoprimos de Euler de Lucas). [9] Un numero com-
puesto n es pseudoprimo de Euler de Lucas con parametros P y Q (los cual notamos
elpsp(P,Q)) si (n, QD) = 1 y
(i) U δ(n)2
≡ 0(mod n) si(Qn) = 1 o
(ii) V δ(n)2
≡ 0(mod n) si(Qn) = −1.
Definicion 3.1.8 (Numeros pseudoprimos fuertes de Lucas). [9] Un numero com-
puesto n es pseudoprimo fuerte de Lucas con parametros P y Q (los cual notamos
slpsp(P,Q)) si (n, D) = 1 y sea d impar tal que δ(n) = d2s, tenemos
35
0234
(i) Ud ≡ 0(mod n) o
(ii) Vd2r ≡ 0(mod n) para algun r con 0 ≤ r < s.
Al igual que en el capıtulo anterior, nos interesa saber como es la relacion entre
estos numeros.
Teorema 3.1.6. [9] slpsp(P, Q) ⊆ elpsp(P, Q) ⊆ lpsp(P, Q).
Vamos a mostrar la segunda inclusion, la primera se puede consultar en [9].
Primero veamos que elpsp(P, Q) ⊆ lpsp(P, Q): segun la propiedad 3.1.2 (p.30), para
todo par de enteros a y b tenemos Ua+b = UaVb + QaUb−a. Tomando a = b = δ(n)2
tenemos Uδ(n) = U δ(n)2
V δ(n)2
+QU0 = U δ(n)2
V δ(n)2
. Si n es un elpsp, cumple la condicion
(i) o (ii) de la definicion 3.1.7. Si cumple la condicion (i), n|U δ(n)2
, y por lo tanto
n|Uδ(n), es decir n es lpsp. Ahora, si cumple la condicion (ii), n|V δ(n)2
, y por lo tanto
n|Uδ(n), es decir n es lpsp.
Teorema 3.1.7. [9] Si n es un elpsp(P,Q) y (Qn) = −1 o δ(n) ≡ 2(mod 4), entonces
n es un slpsp(P,Q).
Demostracion: Supongamos que n es un elpsp(P,Q) y (Qn) = −1. Como δ(n) =
d2s tenemos que δ(n)2
= d2s−1. Por la condicion (ii) de la definicion 3.1.7 (p.35),
Vd2s−1 = V δ(n)2
≡ 0(mod n) y por lo tanto se cumple (ii) de la definicion 3.1.8 (p.35),
y entonces n es un slpsp.
Ahora, si suponemos que n es un elpsp(P,Q) y δ(n) ≡ 2(mod 4),tenemos que d = δ(n)2
.
Al ser un elpsp(P,Q), tenemos que Ud = U δ(n)2
≡ 0(mod n) y por lo tanto se cumple
(i) de la definicion 3.1.8 y ası n es un slpsp, o Vd2s−1 = V δ(n)2
≡ 0(mod n), y por lo
tanto se cumple (ii) de la definicion 3.1.8 y n es un slpsp.
�
Teorema 3.1.8. [9] Supongamos que (n, 2QD) = 1, Un ≡ ε(n)(mod n) y n es un
lpsp(P,Q). Si n es un epsp(Q), tenemos que n es un elpsp(P,Q).
36
0234
Demostracion: Segun la propiedad 3.1.2 (p.30), para todo par de enteros a y
b tenemos Ua+b = UaVb + QaUb−a. Si tomamos a = (n−ε(n))2
y b = (n+ε(n))2
, tenemos
que :
Un = U (n−ε(n))2
V (n+ε(n))2
+ Q(n−ε(n))
2 Uε(n) ≡ ε(n)(mod n) (20)
Como U1 = 1 y U−1 = −1Q
, si ε(n) = 1 entonces Q(n−ε(n))
2 Uε(n) = Q(n−1)
2 ε(n). Y si
ε(n) = −1 entonces Q(n−ε(n))
2 Uε(n) = Q(n+1)
2−1Q
= Q(n−1)
2 ε(n). Por lo tanto, sea cual
sea ε(n), Q(n−ε(n))
2 Uε(n) = Q(n−1)
2 ε(n). Entonces:
U δ(n)2
V (n+ε(n))2
≡ ε(n)(1−Q(n−1)
2 )(mod n). (21)
Utilizando otra vez la propiedad 3.1.2 con a = b = δ(n)2
, tenemos que Uδ(n) =
U δ(n)2
V δ(n)2
+ Qδ(n)
2 U0, pero como U0 = 0, n es un lpsp(P,Q):
Uδ(n) = U δ(n)2
V δ(n)2
≡ 0(mod n). (22)
Ahora, si (Qn) = 1 entonces como n es epsp(Q), Q
(n−1)2 ≡ 1(mod n). Tenemos que
ver si n|U δ(n)2
. (21) queda ası: U δ(n)2
V (n+ε(n))2
≡ 0(mod n).
Sea p un primo impar tal que pe||n y pe - U δ(n)2
, por (22): p|V δ(n)2
, y por (21): p|V (n+ε(n))2
. Como p - Q ya que (n,Q) = 1 tenemos que p|V0 = 2, lo cual es una contradiccion.
Ası que n|U δ(n)2
si (Qn) = 1.
Ahora, si (Qn) = −1 entonces como n es epsp(Q), Q
(n−1)2 ≡ −1(mod n) y (21) queda
ası: U δ(n)2
V (n+ε(n))2
≡ 2ε(n)(mod n). Por lo tanto, n - U δ(n)2
y de (22) obtenemos que
n|V δ(n)2
.
Ası que n es un elsp(P,Q).
�
Definicion 3.1.9 (Los numeros de Lucas-Carmichael). [8] Para un entero fijo D,
llamamos numero de Lucas-Carmichael todo entero positivo y compuesto tal que
(n, 2D) = 1, y que sea lpsp(P,Q) para todo par de enteros (P,Q) tales que D =
P 2 − 4Q, y (Q,D)=1.
El siguiente teorema fue dado por Williams y retomado por Arnualt en [8].
37
0234
Teorema 3.1.9. [8] Para un D fijo, un entero compuesto n es un numero de Lucas-
Carmichael si y solo si es el producto p1...ps de s primos impares distintos, que no
dividen a D y tal que
p− ε(p)|n− ε(n).
Sin embargo hasta el momento no se ha podido saber si existe algun numero que
sea a las vez numero de Carmichael y de Lucas-Carmichael con ε(n) = −1. Williams
demostro que de existir este numero seria de la forma p1...ps con ε(pi) = −1 y s ≥ 5.
La duda que aparece es saber si hay infinitos pseudoprimos de Lucas, y si son
tan escasos como los pseudoprimos definidos anteriormente. Segun [9] las congru-
encias (16)-(19) son bastante raras cuando n es un numero compuesto. Rotkiewics
mostro en 1973 que cuando Q = ±1 y (P, Q) 6= (1, 1), existen infinitos numeros
compuestos que satisfacen (16), (18) y (19) simultaneamente. Yorinaga (1976) es-
tudio la sucecion de Fibonacci y dio la tabla de los numeros menores a 707000 que
satisfacen (18), entre los cuales aparecen cuarto psp(2) (219781, 252601, 399001 y
512461). Lehmer en 1964 demostro que existen infinitos lpsp(1,-1).
En la siguiente seccion vamos a estudiar las densidades de los pseudoprimos de
Lucas.
3.2. La densidad de los pseudoprimos de Lucas
En el capıtulo anterior vimos que la cantidad de pseudoprimos menores a un x
dado es mucho menor que la de primos, y por esto introdujimos los numeros proba-
blemente primos. En esta seccion veremos que sudede lo mismo con los pseudoprimos
de Lucas, y tiene entonces sentido definir los numeros “probablemente primos de Lu-
cas con parametros P y Q”, que son los numeros impares que cumplen la condicion
(16).
Teorema 3.2.1. [9] Dados P y Q, sea L(x) el numero de lpsp(P,Q) menores que x.
Existe una constante c3 tal que para un x lo suficientemente grande:
38
0234
L(x) < x exp(−c3
√(lnx)(ln2x)).
Teorema 3.2.2. [9] Sean P y Q enteros positivos tales que (P, Q) = 1 y P 2 − 4Q
es positivo, pero no un cuadrado. Y sea R(x) el numero de slpsp(P,Q) menores que
x. Ası, existe una constante c(P,Q) tal que R(x) > c(P, Q)ln(x) para todo x lo
suficientemente grande.
En [9] Baillie y Wagstaff nos dicen que los psp(2) menores a 25 × 109 no son
lpsp, y que si escogemos P, Q y D, segun el metodo B (que veremos a continuacion),
los primeros 50 numeros de Carmichael no son lpsp. Seria interesante combinar el
algoritmo dado al final del capıtulo anterior con los pseudoprimos de Lucas para
mejorar la probabilidad de la respuesta.
La pregunta inmediata es como escoger los parametros P y Q. Aun cuando hay
muchas formas de hacerlo, estudiaremos las dos mas conocidas: la primera llamada
(metodo A) propuesta por John Selfridge, y la segunda (metodo B) preferida por
Baillie.
Si D es un cuadrado modulo n, existe un b tal que D ≡ b2(mod n), por lo
tanto (Dn) = 1, P = b + 2, Q = b + 1, α = P+
√D
2≡ P+b
2= b + 1 = Q(mod n),
β = P−√
D2
≡ P−b2
= 1(mod n) y Uδ(n) = Un−1 ≡ αn−1−βn−1
α−β≡ Qn−1−1
Q−1. Esto implica
que Qn−1 ≡ 1(mod n), es decir n es un pseudoprimo en base Q y por lo tanto no
nos interesa. Para evitar este caso, vamos, entonces, a pedir que (Dn) = −1.
Metodo A: Sea D el primer elemento de la sucesion 5, -7, 9, -11, 13,... para el
cual (Dn) = −1. Sea p = 1 y Q = 1−D
4.
Metodo B: Sea D el menor elemento de la sucesion 5, 9, 13..., tal que (Dn) = −1.
Sea P el menor entero impar que sea mayor a D12 y sea Q = p2−D
4.
En el metodo A no interesa D=-3, ya que en ese caso P=Q=1, lo cual genera una
sucesion de Lucas periodica (0 1 1 0 -1 -1 0 -1 -1 0 -1 -1 0...), y para esta todos los
39
0234
n impares que no sean multiplos de 3 son lpsp(1,1). Con el metodo A los primeros
lpsp que encontramos son: 323, 377, 1159, 1829 y 3827, mientras que con el metodo
B son: 323, 377, 1349, 2033 y 2651.
El algoritmo [9] queda entonces ası:
1. Ver que n no es divisible por algun primo menor que un lımite determinado
(por ejemplo 1000).
2. Ver que n es un sprp(2).
3. Ver que n no es el cuadrado de algun numero y que es un lprp, segun el metodo
A o B.
4. ver que n es un slprp para los parametros P y Q.
Si ningun paso falla y n es menor que 1000 (en este caso), se sabe con exactitud
que es un numero primo; de lo contrario, si es mayor que 1000 (y cumple con todos
los pasos) podemos afirmar con una gran probabilidad que es un numero primo. En
[9] afirman que este algoritmo funciona para todos los numeros menores a 25× 109.
La figura 2 muestra como se comportan los lpsp(P,Q) segun el metodo utilizado
para construirlos, y al mismo tiempo muestra el menor elemento de cada categorıa.
Por ejemplo, 2018839 es el menor elpsp segun la forma A, pero segun la forma B es
unicamente lpsp.
La Tabla 8 muestra L(x), R(x) y S(x), la cantidad de lpsp, elpsp y slpsp, re-
spectivamente, menores a un cierto x segun cada uno de los metodos A, B, o los dos
simultaneamente.
Combinando los pseudoprimos, y los pseudoprimos de Lucas obtenemos una
muy buena prueba de primalidad, ya que hasta el momento no se le conoce ningun
contraejemplo. En 1980 Pomerance, Samuel y Wagstaff en [11] ofrecieron U.S.$30 a
la persona que diera un numero que fuera tanto spsp(2) como lpsp por cualquiera
40
0234
�
�
�
�
�
�
�
�
�
�
�
�
lpsp
1829
elpsp
1159
slpsp
5459
75077 2018839
3441239 230159
5777
Metodo A
56279
3827
323164438393569
3599 elpsp
1349 lpsp
Metodo B
slpsp
Figura 2: La relacion entre los lpsp, los lepsp y los lspsp, segun el metodo utilizado
41
0234
de los metodos A o B, o que, por el contrario, demostrara que tales numeros no
existen. En diciembre de 1993 Arnault [8] reafirma que hasta ese momento nadie ha
podido responder a este problema, y que de hecho no se conoce ningun entero que
sea spsp(2) y sea lpsp(1,-1,5) con ( 5n) = −1, lo cual reafirma que el algoritmo de
[9], explicado anteriormente, funciona bastante bien, ya que no se le conoce ningun
contraejemplo.
x 103 104 105 106 107 108
Metodo AL(x) 2 9 57 219 659 1911R(x) 0 3 17 80 269 833S(x) 0 2 12 58 178 505Metodo BL(x) 2 15 70 248 750 2119R(x) 2 7 40 142 441 1265S(x) 2 4 23 84 261 711Metodo A y B simultaneamenteL(x) 2 4 29 87 246 660R(x) 0 1 5 18 57 156S(x) 0 1 5 17 49 125
Tabla 8: Dos aproximaciones de L(x), R(x) y S(x), segun el metodo A o B
Hasta el momento los metodos para verificar la primalidad de un numero tienen
varios problemas: si son deterministas son muy largos (imposibles de realizar), si
son probabilisticos corren el riesgo (aunque muy pequeno) de presentar un numero
compuesto como primo. Los algoritmos que se cree pueden ser de tiempo poli-
nomial, estan basados en conjeturas no demostradas; por ejemplo, el de Miller
es polinomial si la hipotesis extendida de Riemann (o conjetura ERH) 1.0.15 es
cierta. Aunque existe una creencia generalizada en esta conjetura, al faltar una
demostracion matematica, no se puede concluir nada.
Por ello, el reciente descubrimiento de un algoritmo determinista de tiempo poli-
nomial que no se basa en ninguna conjetura no probada debe ser considerado un
hito importante. En agosto de 2002, Agrawal, Kayal y Saxena [5] presentaron un
42
0234
algoritmo deterministico de tiempo polinomial para la determinacion de la primali-
dad de un numero. Este algoritmo (llamado AKS) se puede ejecutar en un tiempo
de complejidad maxima
O((log n)12f(log log n)). (23)
Donde f es una funcion polinomial. El algoritmo se basa en el siguiente teorema, el
cual es una generalizacion del pequeno teorema de Fermat extendido a polinomios:
Teorema 3.2.3. Sean a y p enteros tales que (a,p)=1 y p > 1. Entonces p es primo
si y solo si
(x + a)p ≡ xp + a(mod p). (24)
Demostracion: Si p es primo, p divide a(
pr
)para r = 1, 2, ..., p − 1. Esto
muestra que (x + a)p ≡ (xp + ap)(mod p), y por el pequeno teorema de Fermat
podemos concluir la ecuacion (24).
Ahora, supongamos que p > 1 es un numero compuesto; sea q uno de sus divisores
primos, y sea k tal que qk es la mayor potencia de q que divide a p. Entonces qk no
divide a(
pq
)y es relativamente primo a ap−q, ası que el coeficiente del termino xq en
el termino izquierdo de la ecuacion no es nulo, mientras que en el derecho si lo es.
Tenemos entonces que si p es compuesto, la ecuacion (24) no es valida.
�
Al igual que en los algoritmos dados anteriormente, la idea es para un n dado
escoger un a y verificar si la ecuacion (24) es o no valida. Si no es valida, el numero
es compuesto, de lo contrario es primo. Sin embargo el tiempo de verificacion es
bastante largo, una forma de disminuirlo es la siguiente: calcular los dos lados de la
congruencia modulo un polinomio de la forma xr − 1, para un r pequeno escogido
apropiadamente. En otras palabras el problema se reduce a ver si
(x + a)n ≡ xn + a(mod xr − 1, n). (25)
Todos los primos verifican (25), pero para algunos valores de a y r, algunos com-
puestos tambien la verifican. Si para un r especıfico y para muchos valores de a, la
43
0234
ecuacion se sigue cumpliendo, n debe ser un primo. La cantidad de valores de a y
el valor apropiado de r, estan acotados por un polinomio.
Veamos el algoritmo AKS, el cual tiene como entrada un numero n. Si el numero
es primo la salida del algoritmo es “Primo” y si es compuesto la salida es “com-
puesto”:
1. Si n es de la forma ab donde b > 1, la salida es: Compuesto
2. Encuentre el menor entero r tal que or(n) > log2n.
3. Si 1 < (a, n) < n para algun a ≤ r, la salida es Compuesto.
4. Si n ≤ r, la salida es Primo.
5. Para a = 1 hasta⌊√
φ(r)logn⌋
hacer:
Si ((X + a)n 6= Xn + a(mod Xr − 1, n)), la salida es Compuesto.
Si no a = a + 1.
6. La salida es Primo.
Tambien se muestra en [5] que si los numeros primos de Sophie Germain (1.0.14),
tienen la distribucion esperada, el exponente 12 de la ecuacion (23) puede ser reem-
plazado por un 6 haciendo mucho mas rapido el algoritmo. Es de esperar que en un
futuro el tiempo de ejecucion de este algoritmo mejore, sin embargo los resultados
de los algoritmos probabilısticos actuales (mas rapidos) cubren las necesidades del
momento y muy posiblemente del futuro.
Hasta el momento hemos visto como los pseudoprimos nos permiten hacer prue-
bas de primalidad, y encontrar numeros grandes que tengan una probabilidad bas-
tante buena de ser primos; sin embargo, no sabemos que utilidad puedan tener estos
numeros. A continuacion vamos a ver una de sus aplicaciones.
44
0234
Capıtulo IV
Aplicaciones
Este Capıtulo esta basado en [12] , [18] y [4].
La capacidad de encontrar numeros primos grandes cobro una gran importancia
fuera del ambito de las matematicas, cuando se descubrio que se podıan utilizar
para cifrar mensajes enviados por medios inseguros, tales como radio, telefono, etc.
Llamamos criptografıa a la tecnica de transformacion de datos para hacerlos incom-
prensibles a quien no tenga la clave adecuada. Al arte de desbaratar estas tecnicas se
le llama criptoanalisis y conjuntamente se les conoce como criptologıa. Aun cuando
este ultimo termino no esta recogido todavıa en el Diccionario de la Real Academia
(siendo una traduccion directa de la palabra inglesa Cryptology), es de uso comun
entre los expertos en el tema. Llamamos algoritmo de codificacion al procedimiento
utilizado para volver incomprensible el mensaje que queremos proteger (denominado
texto en claro). Al finalizar este algoritmo, el texto quedara legible unicamente por
las personas deseadas, y lo llamaremos texto cifrado. Este algoritmo se puede ver
como el calculo de una funcion matematica, cuya entrada es el texto en claro y la
salida es el texto cifrado.
Existen tres tipos de sistemas de cifrado: simetricos, asimetricos e hıbridos.
En el sistemas de cifrado simetrico el algoritmo de codificacion es un regla de trans-
formacion del texto, por ejemplo cambiar la letra a por la b, la b por la c... A esta
regla la llamaremos clave de cifrado, y a la usada en el algoritmo de descifrado la
llamaremos clave de descifrado. En este caso, al conocer la clave de cifrado, se puede
45
0234
deducir la de descifrado y, por lo tanto, unicamente las dos personas que se van a
comunicar pueden conocerla. Lo cual representa un problema inicial de divulgacion
de la clave. Esta es la primera causa de inseguridad de este metodo.
En cambio, en los sistemas de cifrado asimetricos estas dos claves son diferentes:
una es publica y se puede entregar a cualquier persona, y la otra es privada y solo el
propietario la conoce. El remitente usa la clave publica del destinatario para cifrar
el mensaje, y una vez cifrado solo la clave privada del destinatario podra descifrarlo.
Estos sistemas, tambien llamados de clave publica, se inventaron con el fin de evitar
el problema del intercambio de claves presentes en los sistemas de cifrado simetricos.
Llamamos funcion de un solo sentido a las funciones faciles de realizar y cuya fun-
cion inversa es extremadamente difıcil. Por ejemplo, multiplicar dos numeros primos
grandes es facil de realizar, mientras que factorizar un compuesto muy grande, por
mas que sepamos que es multiplo de unicamente dos primos, es bastante difıcil. Lla-
mamos funcion-trampa de un sentido a las funciones de un solo sentido tales que
si se posee informacion extra, realizar la inversa de la funcion es facil. Siguiendo
el ejemplo anterior, si conocieramos uno de los dos factores primos, seria muy facil
encontrar el segundo.
Los sistemas asimetricos se basan en funciones-trampa de un solo sentido que aprovechan
propiedades particulares, por ejemplo, de los numeros primos. Siguiendo el mismo
ejemplo, veamos un cifrado de clave publica basado en la factorizacion de numeros
primos: la clave publica contiene un numero compuesto de dos factores primos
grandes, y el algoritmo de cifrado usa ese compuesto para cifrar el mensaje. El
algoritmo para descifrar el mensaje requiere el conocimiento de los factores primos,
de lo contrario serıa extremadamente difıcil. Un ejemplo claro de este tipo de cifrado
es el RSA , que explicaremos mas adelante, y es utilizado actualmente en el mundo
de la banca y de las finanzas.
La mayor ventaja de la criptografıa asimetrica es que se puede cifrar con una
clave y descifrar con la otra, pero este sistema tiene bastantes desventajas:
Para una misma longitud de clave y mensaje se necesita mayor tiempo de
46
0234
proceso que con un sistema simetrico.
Las claves deben ser de mayor tamano que las simetricas.
El mensaje cifrado ocupa mas espacio que el original.
Esto motiva el tercer sistema de cifrado, llamado hıbrido, que consiste en una
mezcla de los dos sistemas: la primera parte del mensaje utiliza un sistema asimetri-
co gracias al cual se mandan la clave de cifrado simetrico, y la segunda parte envıa
el mensaje ya cifrado (mediante el sistema simetrico, con la clave de cifrado enviada).
El algoritmo RSA:
Los mensajes enviados usando el algoritmo RSA se representan mediante numeros
y el funcionamiento se basa en el producto de dos numeros primos grandes (general-
mente de mas de 100 cifras), elegidos al azar, para conformar la clave de descifrado.
La seguridad de este algoritmo radica en que no hay maneras rapidas conocidas de
descomponer un numero grande en sus factores primos, utilizando computadoras
tradicionales. El algoritmo fue descrito en 1977 por Ron Rivest, Adi Shamir y Len
Adleman en MIT; las letras RSA son las iniciales de sus apellidos. Clifford Cocks, un
matematico britanico trabajando para la agencia de inteligencia britanica GCHQ
describio un sistema equivalente en un documento interno en 1973. Debido a la
lentitud de la implementacion en las computadoras de la epoca, se lo considero una
curiosidad. Su descubrimiento, sin embargo, no fue revelado hasta 1997 ya que era
confidencial.
Este algoritmo se basa en el siguiente Lema:
Lema 4.0.1. [18] Sea a un entero, y m un entero positivo tal que (a,m)=1. Si k y
k’ son enteros positivos tales que kk′ ≡ 1(mod φ(m)), entonces akk′ ≡ a(mod m).
Demostracion: Como kk′ ≡ 1(mod φ(m)), existe un entero r > 0 tal que
kk′ = 1 + rφ(m). Segun el Teorema 1.0.2, aφ(m) ≡ 1(mod m) y por lo tanto akk′ ≡a1+rφ(m) ≡ a (aφ(m))r ≡ a(mod m).
47
0234
�
Para generar las claves publicas y privadas necesitamos los siguientes pasos:
1. Escoger dos primos grandes diferentes p1 y p2.
2. Calcular m = p1p2.
3. Calcular φ(m) = (p1 − 1)(p2 − 1).
4. Escoger un entero k grande tal que 0 < k < φ(m) y ver si (k, φ(m)) = 1. Si
esto no pasa, buscar otra k hasta encontrar uno que sirva.
La clave publica es m y k, y la clave privada es p1, p2 y φ(m).
El algoritmo de codificacion es el siguiente:
Primero hay que convertir el texto en claro en un numero, esto se puede hacer,
por ejemplo, cambiando cada caracter por su numero equivalente en codigo ASCII
(American Standard Code for Information Interchange) el cual es muy conocido.
Al concatenar estos numeros, tendremos un numero a equivalente al mensaje. El
siguiente paso es encontrar el entero 0 ≤ b < m tal que b ≡ ak(mod m) y mandarlo
a la persona que tiene la clave privada.
El algoritmo para la decodificacion es el siguiente:
Usando el algoritmo de Euclides encontrar un entero k′ tal que kk′ ≡ 1(mod φ(m)),
y ası encontrar el unico entero 0 ≤ c < m, tal que c ≡ bk′(mod m). Segun el Lema
4.0.1, deducimos que a = c, y ası tenemos el mensaje descifrado.
Veamos un ejemplo con numeros primos pequenos:
Sean p1 = 31, p2 = 59, tenemos entonces que m = 1829 y φ(m) = (30)(58) =
1740. Tomamos k = 1231, como es primo tenemos que (1231, 1740) = 1, con la
ayuda del algoritmos de Euclides podemos encontrar k′ = 1111.
Sea a = 12 el mensaje, como k y m son publicos, la persona que va a enviar el men-
saje puede hallar b ≡ ak(mod m), 0 ≤ b < m. En este caso b ≡ 121231(mod 1829) y
48
0234
ası b = 1376.
Para descifrar el mensaje, lo que debemos hacer es encontrar c ≡ bk′ ≡ 13761111 ≡12(mod 1829).
Vemos que a debe ser menor que m. De no ser ası, se podrıa enviar el mensaje
por bloques mas pequenos, o cambiar m por un numero mas grande.
La seguridad del sistema RSA depende directamente de que tan posible sea
encontrar los factores del compuesto m; sin embargo, hasta el momento no se ha
encontrado ningun metodo en tiempo polinomial para lograr esa descomposicion
de enteros grandes. En 1993, Meter Shor publico Shor’s algorithm, mostrando que
una computadora cuantica podrıa, en principio, hacer esa descomposicion en tiempo
polinomial. Sin embargo, las computadoras cuanticas no se esperan que sean desar-
rolladas hasta dentro de muchos anos.
49
0234
Referencias
[1] The lucas numbers. Online avaliable http://www.mcs.surrey.ac.uk/
Personal/R.Knott/Fibonacci/lucasNbs.html.
[2] Mathworld. Online avaliable mathworld.wolfram.coml.
[3] The prime pages. Online avaliable http://primes.utm.edu/.
[4] Wikipedia. Online avaliable http://www.wikipedia.org/.
[5] Manindra Agrawal, neeraj Kayal, and Nitin Saxena. Primes is in p. Annals ofMathematics, 160:781–793, 2004.
[6] W.R Alford, Andrew Granville, and C. Pomerance. There are infinitely manycarmichael numbers. Annals of Mathematics, 140:703–722, 1994.
[7] Andre Antibi, raymond Barra, Jacques Burgaud, and Roland Charnole. MathTerm S Specialite. Nathan, 1998.
[8] Francois Arnault. Sur quelques tests probabilistes de primalite. PhD thesis,l’Universite de POITIERS, 1993.
[9] Robert Baillie and S.S. Wagstaff Jr. Lucas pseudoprimes. Matematics of com-putation, 35:1391–1417, 1980.
[10] Johannes Buchmann and Volker Mulller. Primality testing. PhD thesis, Uni-versitat des Saarlandes, 1992.
[11] C.Pomerance, J.Selfridge, and S.S. Wagstaff Jr. The pseudoprimes to 25× 109.Math.Comp., 35:1003–1026, 1980.
[12] Keith Devlin. El lenguaje de las matematicas. Intermedio, 2003.
[13] P. Erdos. On pseudoprimes and carmichael numbers. Publ. Math. Debrecen,4:201–206, 1956.
[14] Andrew Granville. Primality testing and carmichael numbers. Notice of theAmerican Mathematical society, 39:696–700, 1992.
50
0234
[15] Andrew Granville and Carl Pomerance. Two contradictory conjectures con-cerning carmichael number. Mathematics of Computation, 71:873–881, 2002.
[16] Jerrold W. Grossman. Discrete Mathematics. An introduction to concepts,methods, and applications. Macmillan, 1990.
[17] D. H. Lehmer. On lucas’s test for the primality of mersennes’s numbers. Onlineavaliable primes.utm.edu/mersenne/LukeMirror/lit/lit 007s.htm. LehighUniversity, Bethlehem, Pa., U.S.A.
[18] Ivan Niven, Herbert S. Zuckerman, and Hugh L. Montgomery. An introductionto the Theory of Numbers. John Wiley & Sons, Inc., fifth edition, 1991.
[19] R.D.Carmichael. On composite numbers p which satisfy the fermat congruenceaP−1 ≡ (1modp). Amer.Math.Monthly, 19:22–27, 1912.
51