TESTS PROBABIL´
ISTICOS
DE PRIMALIDAD
J´ulia Bujosa Moya
Facul ad de Ma em´a icas
Depa amen o de ´
Algeb a
J´ulia Bujosa Moya
Es a memo ia se p esen a como pa e de los c i e ios exigidos pa a comple a los
equisi os y ob ene el ´ı ulo del G ado en Ma em´a icas concedido po la
Uni e sidad de Se illa.
Tu o izada po
Jos´e Ma ´ıa To ne o S´anchez
Depa amen o de ´
Algeb a
Junio 2024, Se illa
Pa a empeza di ´e que es el inal. No es un inal eliz, an s´olo es un inal.
Resumen
La idea de es e abajo es de e mina la p imalidad de un n´ume o a pa i de
es s que buscan gana e iciencia a iesgando e icacia. Pese a que suelen usa se co-
mo sin´onimos, la e iciencia hace e e encia a u iliza algo i mos con un meno cos e
compu acional, sin emba go, la e icacia hace e e encia a un esul ado m´as co ec o y
p eciso sin ene en cuen a los ecu sos usados. Realmen e es e abajo p esen a es s
que buscan un equilib io de ambas, al que podemos llama e ec i idad. La mane a
de abaja de es os es s es a a de e i ica cie as p opiedades que sabemos que
cumplen los n´ume os p imos. Y es en la de inici´on de es as p opiedades donde apa e-
cen los dis in os ipos de pseudop imos, n´ume os compues os jugando a se p imos,
es deci , n´ume os que ambi´en cumplen las p opiedades es adas.
En el p ime cap´ı ulo damos unas p ime as nociones que combinadas con algu-
nos esul ados gene ales se ´an he amien as base pa a cons ui los es s que i emos
p esen ando a pos e io i.
A lo la go del segundo cap´ı ulo, in oducimos el p ime es p obabil´ıs ico, el Tes
de Fe ma , basado p opiamen e en el Peque˜no Teo ema de Fe ma . Con ´el apa ece
po p ime a ez una amilia de pseudop imos. P ecisamen e su exis encia hace que
es e es no sea lo e icaz que se desea y mo i a la b´usqueda de p opiedades y es s
al e na i os. Adem´as, es e p ime ipo de pseudop imos, y su e si´on ue e, llama-
dos n´ume os de Ca michael, oman un papel his ´o icamen e muy impo an e en la
b´usqueda de es s de p imalidad po lo que dedicamos una secci´on pa a su es udio.
En el e ce cap´ı ulo exponemos el es p obabil´ıs ico de Solo ay–S assen, basado
en el Teo ema de Eule , dando pie a los pseudop imos de Eule . Pa a la implemen a-
ci´on del es se in oducen los s´ımbolos de Legend e y Jacobi. Es e ´ul imo no necesi a
ac o izaciones pa a se calculado y dada su impo ancia en la e icacia del es , se
in oduce una secci´on p o undizando en el c´alculo e ec i o del mismo.
Siguiendo el o den c onol´ogico, en el cua o cap´ı ulo in oducimos un es p o-
babil´ıs ico que supe ´o en e ec i idad al de Solo ay–S assen, el es de Mille Rabin,
basado en una p opiedad cu iosa de los p imos que cumplen ambi´en los llamados
pseudop imos ue es. Siguiendo la in uici´on que nos acompa˜na du an e el abajo,

es os n´ume os son a´un menos ecuen es que los pseudop imos de Eule , lo que hace
ene a nues o ´ul imo es meno p obabilidad de e o que odos los es s es udiados
an es.
Po ´ul imo, se p esen an los pseudop imos de Lucas espec i os a un pa de
pa ´ame os al que haciendo una buena elecci´on de es os, pa ecen no solapa se con
los dem´as pseudop imos is os (p oblema que sigue abie o). De aqu´ı nace el ´ul imo
es desc i o en es a memo ia, que ecibe el nomb e de Baillie-PSW, y el cual esul a
in alible po el momen o, aunque su co ecci´on depende de una conje u a.
Abs ac
The aim o his wo k is o de e mine he p imali y o a numbe using es s ha
seek o balance e iciency and e ec i eness. Al hough hese e ms a e o en used in-
e changeably, e iciency e e s o using algo i hms wi h lowe compu a ional cos s,
while e ec i eness e e s o ob aining mo e accu a e and p ecise esul s wi hou con-
side ing he esou ces used. In eali y, his wo k p esen s es s ha aim o a balance
o bo h, which we can call e ec i eness. The way hese es s wo k is by ying o
e i y ce ain p ope ies ha we know p ime numbe s sa is y. I is in he de ini ion
o hese p ope ies ha di e en ypes o pseudop imes appea , composi e numbe s
p e ending o be p ime, ha is, numbe s ha also sa is y he es ed p ope ies.
In he i s chap e , we p o ide some ini ial concep s ha , combined wi h some
gene al esul s, will be basic ools o cons uc ing he es s we will p esen la e .
In he second chap e , we in oduce he i s p obabilis ic es , he Fe ma Tes ,
which is based on Fe ma ’s Li le Theo em. Wi h i , a amily o pseudop imes appea s
o he i s ime. The exis ence o hese pseudop imes makes his es no as e ec i e
as desi ed and mo i a es he sea ch o al e na i e p ope ies and es s. Addi ionally,
his i s ype o pseudop imes, and hei s onge e sion called Ca michael numbe s,
play a his o ically impo an ole in he sea ch o p imali y es s, so we dedica e a
sec ion o hei s udy.
In he hi d chap e , we p esen he p obabilis ic Solo ay-S assen es , based on
Eule ’s Theo em, gi ing ise o Eule pseudop imes. Fo he implemen a ion o he
es , he Legend e and Jacobi symbols a e in oduced. The la e does no equi e
ac o iza ions o be calcula ed, and gi en i s impo ance in he es ’s e ec i eness, we
include a sec ion del ing in o i s e ec i e calcula ion.
Following he ch onological o de , in he ou h chap e , we in oduce a p oba-
bilis ic es ha su passed he Solo ay-S assen es in e ec i eness, he Mille -Rabin
es , based on a cu ious p ope y o p imes ha also sa is ies he so-called s ong
pseudop imes. Following he in ui ion ha guides us h oughou he wo k, hese
numbe s a e e en less equen han Eule pseudop imes, which gi es ou las es a
lowe p obabili y o e o han all he es s s udied be o e.
Finally, he Lucas pseudop imes co esponding o a pai o pa ame e s a e p e-
sen ed. Wi h a good choice o hese pa ame e s, hey seem no o o e lap wi h he
o he pseudop imes seen (a p oblem ha emains open). F om his a ises he las
es desc ibed in his epo , called he Baillie-PSW es , which is in allible o now,
al hough i s co ec ness depends on a conjec u e.
´
Indice
In oducci´on 2
1. En busca de la p imalidad 4
1.1. P ime asnociones ............................. 4
1.2. Resul ados gene ales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2. Tes de Fe ma 9
2.1. Pseudop imos de Fe ma . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2. N´ume os de Ca michael . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3. Tes de Solo ay–S assen 18
3.1. Pseudop imos de Eule . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2. C´alculo e ec i o del s´ımbolo de Jacobi . . . . . . . . . . . . . . . . . . 25
4. Tes de Mille –Rabin 31
5. Tes de Baillie-PSW 41
5.1. Pseudop imos de Lucas . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.2. Ejemplo de aplicaci´on con SageMa h ................... 47
Ap´endice: Implemen aci´on en SageMa h 48
5.2.1. Elecci´on de niconSageMa h ................... 48
5.2.2. P imalidad de nicon Solo ay-S assen . . . . . . . . . . . . . . 48
5.2.3. P imalidad de nicon Mille -Rabin . . . . . . . . . . . . . . . . 49
5.2.4. P imalidad de nicon Baillie-PSW . . . . . . . . . . . . . . . . 51
5.2.5. Ejemplo pseudop imo de Lucas . . . . . . . . . . . . . . . . . . 52
5.2.6. C´alculo de π(x) con xen e 1010 y 2,5×1010 u ilizando el
algo i mo de Mille -Rabin . . . . . . . . . . . . . . . . . . . . . 53
Bibliog a ´ıa 54
1
1.2. RESULTADOS GENERALES
Es e esul ado es de g an ele ancia con espec o a los n´ume os p imos, pese a no
habe sido demos ado a´un. Tan o es as´ı que un g an n´ume o de enunciados se han
p obado asumiendo que es cie o. En pocas palab as, lo que Riemann descub i´o que la
dis ibuci´on de los ce os de la unci´on ze a de Riemann es ´a ´ın imamen e elacionada
con la dis ibuci´on de los n´ume os p imos, e elando una conexi´on p o unda y una
dualidad en e ambos concep os. Es a e elaci´on sugie e que no exis e una ´o mula o
pa ´on simple que p ediga la dis ibuci´on de los n´ume os p imos. Es es o lo que nos
mo i a a segui cons uyendo algo i mos que nos ayuden a de e mina la p imalidad
de un n´ume o. En emos en el asun o.

Cap´ı ulo 2
Tes de Fe ma
Vous me demandez si le nomb e 100.895.598.169 es p emie ou non, e une m´e ho-
de pou d´ecou i , dans l’espace cun jou , s’il es p emie ou compos´e. A ce e ques-
ion, je ´eponds que ce nomb e es compos´e e se ai du p odui de ces deux: 898.423
e 112.303, qui son p emie s.
Pie e de Fe ma [12]
2.1. Pseudop imos de Fe ma
A mediados del siglo XVII, el ma em´a ico anc´es Pie e de Fe ma esc ibi´o una
ca a a su amigo y con iden e F ´enicle de Bessy, en la que expon´ıa lo que m´as a de
se conoce ´ıa como su Peque˜no Teo ema [8], que no es m´as que el Teo ema de Eule
1.10 aplicado a los p imos.
Teo ema 2.1 (Peque˜no Teo ema de Fe ma ) Sea pun n´ume o p imo y aun
en e o al que gcd(a, p) = 1. En onces,
ap−1≡1 (m´od p) (2.1)
Es e esul ado es la base de los es s que e emos m´as adelan e. La p egun a cla e
es la siguien e: ¿se ´ıa cie o el ec´ıp oco? Si as´ı ue a, el siguien e es , basado en la
comp obaci´on de (2.1), se ´ıa la soluci´on al p oblema de la p imalidad.
En ada: (n, k)∈N≥3×N, con nimpa y kuna co a pa a el n´ume o de i e aciones
Salida: False, si nes compues o, o bien npasa el es .
9
2.1. PSEUDOPRIMOS DE FERMAT
Algo i hm 1 Tes de p imalidad de Fe ma (ki e aciones)
En ada: (n, k)∈N≥3×N, con nimpa y kuna co a pa a el n´ume o de i e aciones
Salida: False, si nes compues o, o bien npasa el es .
1: i←0
2: while i<kdo
3: Elegi a∈Z/nZ {0}
4: i gcd(a, n)= 1 hen
5: e u n False
6: else
7: i an−1≡ 1 (m´od n) hen
8: e u n False
9: else
10: i←i+ 1
11: end i
12: end i
13: end while
14: e u n npasa el es
Obse aci´on 2.2 En caso de que el algo imo inaliza a en la l´ınea 5 u 8, la base a
que es amos es ando se ´ıa nues o es igo de composici´on.
Obse aci´on 2.3 Cabe ema ca que el algo i mo es e icien e. El paso 4 consis e en
calcula el m´aximo com´un di iso de dos n´ume os, lo cual se puede hace usando el
algo i mo de Euclides con complejidad O(log3(n)) [10].
El paso 7 equie e la denominada exponenciaci´on modula . Pa a lle a a cabo
es o, exis e un m´e odo e icien e, el algo i mo de cuad ados epe idos, que consis e en
abaja con el exponen e en base 2 e i calculando cuad ados m´odulo nen unci´on
de dicha descomposici´on del exponen e. Con es e m´e odo halla an−1m´od n iene
complejidad O(log(n) log2(a)) [10], es deci , polinomial an o en el ama˜no de acomo
en el de n.
Sin emba go, no odo es an sencillo como pa ece y es es e el pun o c ´ı ico a pa i
del cual nace la mo i aci´on del abajo. El Peque˜no Teo ema de Fe ma p opo cio-
na una condici´on necesa ia, no su icien e, pa a los n´ume os p imos. E ec i amen e, el
ec´ıp oco del eo ema no es cie o, en gene al, pues o que apa ecen n´ume os compues-
os que pasan el es , es deci , pod ´ıan se e ´oneamen e iden i icados como p imos.
Veamos qui´enes son es os n´ume os y su impo ancia den o del campo de la p imali-
dad.
2.2. N´
UMEROS DE CARMICHAEL
De inici´on 2.4 Sea n∈Z≥1, y aun n´ume o al que gcd(a, n) = 1, en onces se dice
que nes un pseudop imo (de Fe ma ) espec o de la base asi:
an−1≡1 (m´od n).(2.2)
Po ejemplo, pa a n= 91 = 7 ·13 y a= 3, e ec i amen e se cumple la equi alencia
390 ≡1 (m´od 91). Eso es, 91 es pseudop imo espec o de la base 3.
Sin emba go, 290 ≡40 (m´od 91), es deci , 91 no es pseudop imo espec o de la
base 2, po lo an o el es de ec a ´ıa que nes compues o y 2 se ´ıa un es igo de
composici´on. Es o no ocu e con 1105 = 5 ·13 ·17, ya que es pseudop imo an o pa a
la base 2 como pa a la base 3, de hecho lo es pa a oda base.
Es e ´ul imo ejemplo da luga a una nue a de inici´on que juega un papel ealmen e
ele an e en el campo de la p imalidad. En e ec o, los n´ume os de Ca michael de inidos
a con inuaci´on, inci a on a los in es igado es a busca p opiedades que cumplan los
n´ume os p imos dis in as a (2.2).
2.2. N´ume os de Ca michael
De inici´on 2.5 Un en e o ncompues o se dice que es un n´ume o de Ca michael
si es pseudop imo espec o a oda base, es deci ,
an−1≡1 (m´od n)∀a∈Zcon 0 < a < n, gcd(a, n) = 1 (2.3)
Veamos algunos ejemplos de n´ume os de Ca michael con p opiedades que i emos
explo ando a medida que a anzamos en el campo de la pseudop imalidad. Algunos
de es os los hemos sacado de [27]. En conc e o:
561 = 3 ·11 ·17,2821 = 7 ·13 ·31,15841 = 7 ·31 ·73
son n´ume os de Ca michael. Es impo an e hace no a el n´ume o de ac o es p imos
que poseen, ya que m´as adelan e e emos una co a in e io de es e n´ume o.
Veamos qu´e ocu e si aplicamos el es de Fe ma al ´ul imo ejemplo. Es a sesi´on
SAGE y odas las pos e io es se encuen an ecopiladas en el Ap´endice.
1de e ma _ es (n , k):
2 o _in ange (k):
3a = andin (2, n - 2)
4i powe _mod (a , n - 1, n) != 1:
5p in (n , "es compues o y alla el es en la i e acion ", i ,
"con la base ", a)
6 e u n False
2.2. N´
UMEROS DE CARMICHAEL
7p in (n , "es p obablemen e p imo y pasa el es as ", k, "
i e aciones ")
8 e u n T ue
9
10 e ma _ es (15841 , 20)
11 OUT:
12 15841 es p obablemen e p imo y pasa el es as 20 i e aciones
Lo cual es e ´oneo como hemos acla ado a iba. ¿Pod ´ıa implemen a se es e es
como un algo i mo e ec i o de p imalidad sal o po la posibilidad de que el n´ume o
e aluado nsea un n´ume o de Ca michael?
Si nos ponemos en el mejo de los casos, y suponemos que nno es un n´ume o de
Ca michael y ampoco es un n´ume o p imo, en onces pa a es udia la e icacia del es
de Fe ma , nos debemos p egun a pa a cu´an as bases pod ´ıa nse pseudop imo. De
hecho, como e emos, se puede demos a que, en esas condiciones, nes pseudop imo
espec o de menos de la mi ad de las posibles bases a.
Lema 2.6 Sea n∈Z≥2compues o. El conjun o
H=a∈Un|an−1= 1
es un subg upo de Un.
Demos aci´on: Pa a demos a que Hes un subg upo de Un, e i icamos las dos
condiciones usuales:
1. El p oduc o es ce ado: Sean a, b ∈H. Es o implica que an−1= 1 y bn−1= 1
(po de inici´on de H). En onces,
(ab)n−1=an−1bn−1= 1 ·1 = 1 (m´od n),
lo que signi ica que ab ∈H.
2. Elemen o in e so: Pa a cada a∈H, que emos p oba que a−1∈H. Sabemos
que an−1≡1 m´od n(po de inici´on de H), en onces a−1=an−2y
an−2n−1=an−1n−2≡1n−2≡1 m´od n,
po lo an o a−1∈H.
Luego Hes un subg upo de Un.□
Teo ema 2.7 Si nno es un n´ume o de Ca michael (es deci , no e i ica (2.2) pa a
alguna base a∈Un), en onces nno e i ica (2.2) pa a al menos la mi ad de las
posibles bases a∈Un.
2.2. N´
UMEROS DE CARMICHAEL
Demos aci´on: Sea Hel subg upo de inido en el lema an e io , y no emos h=|H|
ym=|Un|=φ(n). Po el Teo ema de Lag ange [8], sabemos que hdi ide a m, es
deci , que exis e un d∈N al que dh =m.
Al no se nun n´ume o de Ca michael enemos que h < m, y en onces d≥2, po
an o h≤m/2. □
En consecuencia, suponiendo que nno es un n´ume o de Ca michael, si el ou pu del
Tes de Fe ma es npasa el es ,nse ´a compues o con una p obabilidad meno que
1/2, es deci , el es alla con p obabilidad in e io al 50 %. Si ealizamos ki e aciones,
la p obabilidad de que npase odos los es s sin se p imo es en onces in e io a 1/2k.
Como el algo i mo solo se puede conside a p eciso bajo la condici´on de que nno
sea un n´ume o de Ca michael, necesi amos a e igua un poco m´as sob e es os cu iosos
n´ume os.
En 1899 Ko sel , en espues a al P obl`eme Chinois de L’in e m´ediai e des Ma h´e-
ma iciens1, demos ´o el siguien e esul ado.
Teo ema 2.8 (Ko sel [20]) Sea nun en e o compues o. Las dos condiciones si-
guien es son equi alen es:
1. El en e o nes un n´ume o de Ca michael.
2. El en e o nes lib e de cuad ados y pa a odo p imo pque di ide a n, se cumple
que (p−1) |(n−1).
Demos aci´on: Sea nun n´ume o de Ca michael y puno de sus di iso es p imos. En
p ime luga eamos que nes lib e de cuad ados. Es cla o que exis e una descomposi-
ci´on de n al que n=pk·m, donde pes p imo, k≥1 y gcd(p, m) = 1. Demos amos
que k= 1 po educci´on al absu do.
Supongamos que k > 1, caso en el que p2|n. Po el Teo ema Chino del Res o,
exis e un ´unico a∈Z/nZ al que
a≡1 + p(m´od pk), a ≡1 (m´od m).
En ese caso gcd(a, n) = 1, de modo que po se nun n´ume o de Ca michael se iene
an−1≡1 (m´od n) y po an o,
(1 + p)n−1≡1 (m´od p2).
1Pe i´odico anc´es undado en 1894 y equi alen e en esa ´epoca al ac ual The Ame ican Ma he-
ma ical Mon hly.

2.2. N´
UMEROS DE CARMICHAEL
El Teo ema del Binomio ga an iza
(1 + p)n−1≡1+(n−1)p(m´od p2),
pe o como n−1≡ −1 (m´od p2), se e i ica
(1 + p)n−1≡1−p(m´od p2).
En consecuencia, se ob iene 1 ≡1−p(m´od p2), que es cla amen e un absu do. Po
ello, solo es posible que k= 1 y nsea lib e de cuad ados.
Veamos aho a que (p−1) |(n−1). Como nes lib e de cuad ados, gcd(n/p, p) = 1.
Sea bun elemen o de Fpque sea gene ado de Up. El Teo ema Chino del Res o
ga an iza que exis e un ´unico a∈Z/nZ al que
a≡b(m´od p), a ≡1 (m´od n/p).
Es as condiciones nos ga an izan que ap−1≡1 an o en m´odulo pcomo en m´odulo
n/p. Po an o, de nue o po el Teo ema Chino del Res o, ap−1≡1 (m´od n), y po
se nun n´ume o de Ca michael debe ene se que (p−1) |(n−1).
P obemos en onces que la condici´on (2) implica que nes de Ca michael. Sea
en onces n > 2 un en e o compues o y lib e de cuad ados al que (p−1) |(n−1) pa a
cada pp imo di iso de n. Dado a∈Un, el Peque˜no Teo ema de Fe ma ga an iza
que ap−1≡1 (m´od p), pa a odo pdi iso p imo de n. Po lo an o, se cumple
que an−1≡1 (m´od p). En consecuencia, an−1≡1 (m´od n), esul ando que nes un
n´ume o de Ca michael. □
P oposici´on 2.9 Si nes un n´ume o de Ca michael, en onces iene al menos es
ac o es p imos dis in os.
Demos aci´on: Como nes de Ca michael, nno es p imo, luego iene al menos dos
ac o es dis in os, pues nes lib e de cuad ados. Veamos que no puede ene s´olo dos.
Si ue a el caso, se ´ıa n=pq, con p=q. En onces,
n−1 = pq −1 = (p−1)q+ (q−1).
Po o o lado, (p−1) |(n−1) po se de Ca michael, luego (p−1) |(q−1). De la
misma o ma, (q−1) |(p−1) y se iene p=q, lo que no es posible. □
Despu´es de analiza es os n´ume os nos in ade la duda de si ealmen e son an
impo an es como pa a ene los en cuen a a la ho a de es a la p imalidad de un
2.2. N´
UMEROS DE CARMICHAEL
n´ume o ¿Cu´an os n´ume os de Ca michael meno es que un x∈Zdado exis en? ¿Hay
in ini os n´ume os de Ca michael? En caso a i ma i o, ¿con qu´e ecuencia encon amos
n´ume os de Ca michael en e los n´ume os na u ales? En o as palab as, ¿podemos
compa a el c ecimien o de los n´ume os de Ca michael con alguna unci´on conocida
como hacemos con π(x) en el eo ema de n´ume os p imos?
Pa a analiza heu ´ıs icamen e es e en´omeno, deno a emos en lo sucesi o,
C(x)=#n≤x|nes de Ca michael.
Si omamos x= 1016 pa a e un ejemplo o ien a i o de la densidad de los n´ume os
de Ca michael, enemos po ejemplo
C(x) = 246683 ≈2,5·105, π(x) = 279238341033925 ≈2,8·1014.
El abajo de Al o d, Pome ance y G an ille [1], in oluc ando a la ez ´ecnicas
compu acionales y su iles a gumen os de eo ´ıa anal´ı ica de n´ume os, p ueba que hay
in ini os n´ume os de Ca michael aunque es cie o que son menos ecuen es que los
p imos. Aun as´ı, no son an poco ecuen es como pa a igno a los. En la Tabla 1 ( e
m´as adelan e) se mues a una compa a i a.
Es m´as, se puede demos a un esul ado an´alogo al Teo ema de los N´ume os
P imos.
Teo ema 2.10 ([26]) En las condiciones an e io es, sea
L(x) = exp −log(x) log log log(x)
log log x
En onces, pa a xsu icien emen e g ande, se iene que x2/7≪C(x)≪xL(x).
Pese a que no sea el ema p incipal y los de alles de la p ueba se queden ue a del
alcance de es e abajo, emos opo uno da una idea de la p ueba de es e eo ema,
el cual esul a un an´alogo al Teo ema de los N´ume os P imos. La co a supe io ue
suge ida po ¨
E dos y se puede e una p ueba en [28]. Damos una idea de la demos-
aci´on de la p ueba que p opo ciona on Al o d, Pome ance y G an ille en [1] pa a
la co a in e io (que p ueba la exis encia de in ini os n´ume os de Ca michael).
La demos aci´on pa e de la unci´on
ψ:R2−→ N
(x, y)7−→ #n∈Z|nes p imo, n|kpa a alg´un k≤x, n ≤y
y de es esul ados p incipales que mencionamos a con inuaci´on.
El p ime o es el Lema de De B uijn [6] el cual p opo ciona una es imaci´on p ecisa
de la unci´on ψ(x, y) en ´e minos de xeycuando xes lo su icien emen e g ande en
elaci´on con y.
2.2. N´
UMEROS DE CARMICHAEL
Lema 2.11 (De B uijn) Pa a cada ε > 0, exis e un x0(ε) al que si x > x0(ε),
ln x≤y≤x, y u= ln x/ ln y, en onces
ψ(x, y)≤x·exp (−(1 −ε)uln u).
Adem´as, la demos aci´on hace uso del eo ema de Rosse [33], el cual es ablece una
elaci´on undamen al en e los n´ume os p imos y el loga i mo na u al, p opo cionando
l´ımi es supe io es e in e io es p ecisos pa a el n-´esimo n´ume o p imo:
Teo ema 2.12 (Rosse ) Sea {Pn}n≥1la sucesi´on de los n´ume os p imos. Pa a odo
n´ume o na u al nse e i ica que
nln(n)< Pn<2nln(n).
Y como ´ul imo esul ado p incipal se apoya en la F´o mula de Abel [11], muy
impo an e en Teo ´ıa An´ali ica de N´ume os.
Teo ema 2.13 (F´o mula de Abel) Pa a cada unci´on a i m´e ica an, de inimos
A(x) = X
n≤x
a(n),
donde A(x) = 0 si x < 0. Supongamos que (x) iene una de i ada con inua en el
in e alo [x, y], con 0 < x < y. En onces,
X
x≤n≤y
a(n) (n) = A(y) (y)−A(x) (x)−Zy
x
A( ) ′( )d
La p ueba del eo ema se basa en onces en di idi los n´ume os de Ca michael
n≤xen es clases con 0 < δ < 1. En conc e o:
1. Los que e i ican n≤x1−δ.
2. Los que e i ican x1−δ< n ≤xyn iene un ac o p imo p≥xδ.
3. Los que e i ican x1−δ< n ≤xy odo ac o p imo de nes meno que xδ.
El siguien e obje i o es encon a una co a supe io pa a cada una de es as clases.
La cons ucci´on y demos aci´on de es as co as implican el uso de he amien as y lemas
adicionales, cuya exposici´on de allada eque i ´ıa un abajo apa e.
La abla de la siguien e p´agina ( e [17]) mues a la e oluci´on de C(x). Se a˜nade
la ´ul ima columna (ex a´ıda de [14]) con el p op´osi o de hace no a la di e encia de
densidades de p imos y n´ume os de Ca michael.
2.2. N´
UMEROS DE CARMICHAEL
Dadas las limi aciones del Tes de Fe ma causadas po la p esencia de es os n´ume-
os an especiales y que desg aciadamen e no pasan desape cibidos, en los p ´oximos
cap´ı ulos abo da emos o os es s de p imalidad p obabil´ıs icos que supe an el p o-
blema de la exis encia de n´ume os de Ca michael y o ecen un uncionamien o m´as
iable, a la pa que e icien e.
x C(x) A˜no Descub ido (es) π(x)
1031 1910 Ca michael 168
1047 1912 Ca michael 1229
10516 9592
10643 78498
107105 664579
108255 1938 Poule 5761455
109646 1975 Swi 50847534
1010 1547 455052511
2.5 ×1010 2163 1980 Pome ance, Sel idge, Wags a 21099985405
1011 3605 4118054813
1012 8241 1990 Jaeschke 37607912018
1013 19279 346065536839
1014 44706 3204941750802
1015 105212 1992 Pinch 29844570422669
2Calculado en la secci´on 5.2.
3.1. PSEUDOPRIMOS DE EULER
Es amos en condiciones de in oduci el Tes de Solo ay–S assen, algo i mo p o-
babil´ıs ico que conduce o a la conclusi´on de que nes compues o o a la conclusi´on de
que es p obablemen e p imo. El algo i mo se a a basa simplemen e en escoge una
base 0 < a < n y e qu´e ocu e con la cong uencia
a(n−1)/2≡a
n(m´od n).
Si npasa el es pa a la base a, no se puede asegu a que nsea p imo, has a que
p obemos con odos los a∈Un. Aho a bien, lo que hemos mejo ado eliminando la
posibilidad de que en en en juego los n´ume os de Ca michael es la p obabilidad de
e o , ya que si nes compues o,
Pnpasa el es ≤1
2k
con kel n´ume o de eces que epe imos el algo i mo pa a di e en es bases.
Algo i hm 2 Tes de p imalidad de Solo ay–S assen (ki e aciones)
En ada: (n, k)∈N≥3×N, con nimpa y kuna co a pa a el n´ume o de i e aciones
Salida: False, si nes compues o, o bien npasa el es
1: i←0
2: while i<kdo
3: Elegi a∈Z/nZ
4: i gcd(a, n)= 1 hen
5: e u n False
6: else
7: i a(n−1)/2≡ a
n(m´od n) hen
8: e u n False
9: else
10: i←i+ 1
11: end i
12: end i
13: end while
14: e u n npasa el es
Obse aci´on 3.13 En cuan o a complejidad, encon a el lado de echo a(n−1)/2 oma
O(log3n) ope aciones de bi s, u ilizando el m´e odo de exponenciaci´on modula que
mencionamos en el cap´ı ulo an e io . Lo que esul a no edoso y bene icioso a la pa
es la complejidad de calcula el s´ımbolo de Jacobi en el lado izquie do. Pa ece que el
s´ımbolo de Jacobi exige ac o iza npa a e i ica la igualdad, pe o no es as´ı.
De hecho se in oduce es e nue o concep o po que pa a su c´alculo, en caso de que
no sepamos si nes p imo o no, podemos calcula lo sin ac o iza n, a ea que hab ´ıa

3.2. C´
ALCULO EFECTIVO DEL S´
IMBOLO DE JACOBI
esul ado incluso m´as compleja que de e mina su p imalidad. Aunque ha emos ´en asis
en es o en la siguien e secci´on, adelan amos que el segundo lado de la igualdad ambi´en
oma O(log3n) ope aciones de bi s. Luego siendo kel n´ume o de eces que epe imos
el algo i mo, es e iene complejidad O(klog3n). Po an o emos que es un algo i mo
e icien e, aunque eso s´ı, p obabil´ıs ico.
Como hemos comen ado ya, se ha implemen ado en el ap´endice una e si´on de cada
es que p esen a emos en es e abajo, omando 3 ejemplos de la misma magni ud
pe o con ca ac e ´ıs icas dis in as pa a p oba los es s sob e ellos. Dejamos los c´alculos
en el ap´endice mos ando ´unicamen e los esul ados, que como emos nos dan, cuando
p ocede, es igos de composici´on:
12432902008176640000 es compues o y alla el es en la i e a c i n 1 con
2la base 1868969210451108746
33044260448006092643 es compues o y alla el es en la i e a c i n 1 con
4la base 2680792065180999020
51816787885244115403 es p obablemen e p imo y pasa el es as 20
6i e aciones
3.2. C´alculo e ec i o del s´ımbolo de Jacobi
Como se ha in oducido an e io men e, al igual que el Algo i mo de Euclides p o-
po ciona un m´e odo e icien e pa a el c´alculo del gcd(a, b) sin necesidad de halla
ac o izaciones, el s´ımbolo de Jacobi nos pe mi e hace lo mismo aunque no pa ezca
e iden e con la de inici´on que hemos dado. Es a es una en aja no able, ya que, como
mencionamos en la in oducci´on, no se conoce ning´un algo i mo e icien e pa a calcula
ac o izaciones de en e os. El con enido de es a secci´on se basa esencialmen e en el
a amien o de [35].
Todo comienza con Gauss, quien denomin´o al siguien e esul ado como el Teo e-
ma ´
Au eo. Se conoce hoy como la Ley de Recip ocidad Cuad ´a ica de Gauss, uno de
los esul ados con m´as demos aciones dis in as de la His o ia de las Ma em´a icas,
con ando ac ualmen e con mas de 200. La demos aci´on o iginal (po inducci´on) se
encuen a en [13]. Pese a que no da emos la demos aci´on, eamos una b e e explica-
ci´on:
Teo ema 3.14 (Ley de Recip ocidad de Gauss) Sean pyqp imos impa es dis-
in os.
1. −1
p= (−1)(p−1)/2=(1 si p≡1 (m´od 4)
−1 si p≡3 (m´od 4)
3.2. C´
ALCULO EFECTIVO DEL S´
IMBOLO DE JACOBI
2. 2
p= (−1)(p2−1)/8=(1 si p≡1,7 (m´od 8)
−1 si p≡3,5 (m´od 8)
3. q
pp
q= (−1)(p−1)(q−1)/4
Obse aci´on 3.15 El apa ado (1) es en ealidad el C i e io de Eule (Teo ema 3.8)
aplicado a a=−1, jun o con la obse aci´on de que si p= 4s+ , en onces
(−1)(p−1)/2= (−1)( −1)/2,
donde s´olo puede se 1 o 3. En el segundo, lo di ´ıcil es p oba el p ime caso ( e
[32]). Po ´ul imo, no emos que el e ce o puede e o mula se as´ı:
p
q=








−q
psi p≡1 (m´od 4) o si q≡1 (m´od 4)
q
psi p≡q≡3 (m´od 4).
Obse aci´on 3.16 Al igual que nos plan eamos qu´e es lo que ocu e con los esiduos
cuad ´a icos, ambi´en pod ´ıamos analiza lo mismo pa a los esiduos de po encias
mayo es. De hecho, Gauss explo ´o la posibilidad de ex ende su Ley de Recip ocidad
Cuad ´a ica a esiduos de po encias mayo es que 2. Sin emba go, se pe ca ´o de que
pa a abo da es e p oblema e a necesa io conside a los n´ume os complejos y las
a´ıces de la unidad. Es a ue una de las azones po las cuales in odujo los en e os
gaussianos Z[i]. No obs an e, ue Eisens ein en 1844 el p ime o que p opo cion´o una
p ueba comple a de las co espondien es leyes de ecip ocidad c´ubica y bicuad ´a ica
haciendo uso de ex ensiones de Z, de lo que podemos lee m´as en [3] .
Ejemplo: Veamos c´omo usa es as p opiedades pa a un c´alculo expl´ıci o del
s´ımbolo de Legend e. En es as igualdades hemos ma cado con Fel uso de la ac-
o izaci´on en p imos, con Rel uso de la Ley de Recip ocidad y con Del uso de la
di isi´on eucl´ıdea.
26
31F
=2
3113
31R
= 1 ·31
13D
=5
13R
=13
5D
=3
5R
=5
3D
=2
3R
=−1
Obse amos que en el p ime caso se ha necesi ado ac o iza . Sin emba go, g acias
al esul ado de Jacobi que demos a emos a con inuaci´on y que, en cie o sen ido,
gene aliza la Ley de Recip ocidad Cuad ´a ica de Gauss, pod emos hace es e c´alculo,
pa a nno necesa iamen e p imo, sin necesidad de ac o iza . Veamos la cons ucci´on.
Sean nymdeno an en e os posi i os impa es, y ayben e os a bi a ios. Son
inmedia as de comp oba las siguien es p opiedades:
3.2. C´
ALCULO EFECTIVO DEL S´
IMBOLO DE JACOBI
a
n=b
nsi a≡b(m´od n), equi ale a Den el ejemplo an e io .
1
n= 1, 0
n= 0
a
nb
n=ab
n
Pa a las siguien es p opiedades s´ı p ocede da una demos aci´on:
Teo ema 3.17 (Ley de Recip ocidad de Jacobi) Sean aynen e os mayo es
que 3. En onces,
1. −1
n= (−1)(n−1)/2=(1 si n≡1 (m´od 4)
−1 si n≡3 (m´od 4)
2. 2
n= (−1)(n2−1)/8=(1 si n≡1,7 (m´od 4)
−1 si n≡3,5 (m´od 4)
3. a
nn
a= (−1)(a−1)(n−1)/4=(1 si n≡1 (m´od 4)
−1 si n≡3 (m´od 4)
An es de p oba es e esul ado, p esen amos dos lemas b e es:
Lema 3.18 La aplicaci´on
γ:U4→ {±1}, n 7→ (−1)(n−1)/2
es un homomo ismo de g upos.
Demos aci´on: Sean a, n ∈U4={1,3}(obse emos que son impa es). Hay que
p oba que γ(an) = γ(a)γ(n), es deci , que:
(−1)(an−1)/2= (−1)(a−1)/2(−1)(n−1)/2
Es a ecuaci´on equi ale a
(−1)(an−1)/2−(a−1)/2−(n−1)/2= 1,
lo que a su ez equi ale a que
an −1
2−a−1
2−n−1
2
sea pa . Vemos ´acilmen e que
an −1
2−a−1
2−n−1
2=1
2(an −1−n+ 1 −a+ 1) = 1
2(n−1)(a−1).
Como aynson impa es, (n−1)(a−1) es di isible po 4, luego la ´ul ima exp esi´on
es m´ul iplo de 2, y po an o, pa . □
3.2. C´
ALCULO EFECTIVO DEL S´
IMBOLO DE JACOBI
Lema 3.19 La aplicaci´on
β:U8→ {±1}, n 7→ (−1)(n2−1)/8
es un homomo ismo de g upos.
Demos aci´on: An´alogamen e, sean a, n ∈U8={1,3,5,7}. De nue o son impa es y
hay que p oba que β(an) = β(a)β(n), es deci , que
(−1)((an)2−1)/8= (−1)(a2−1)/8(−1)(n2−1)/8,
lo que equi ale a que
(an)2−1
8−a2−1
8−n2−1
8
sea pa . Vemos en onces, como en el caso an e io , que
(an)2−1
8−a2−1
8−n2−1
8=1
8(an)2−1−a2+ 1 −n2+ 1=1
8(n2−1)(a2−1).
Aho a bien, obse emos que si n∈U8={1,3,5,7}, en onces n2≡1 (m´od 8), y lo
mismo ocu e pa a a. Po an o, como (n2−1) y (a2−1) son m´ul iplos de 8, se ob iene
el esul ado ya que la ´ul ima exp esi´on es m´ul iplo de 8 y po ende pa . □
Ya es amos en condiciones de demos a la Ley de Recip ocidad Cuad ´a ica de Ja-
cobi bas´andonos an o en es os dos lemas como en la Ley de Recip ocidad Cuad ´a ica
de Gauss.
Demos aci´on: Sean γyβlos mo ismos de los lemas an e io es, y sean
n=
Y
i=1
pei
i, a =
s
Y
i=1
q i
i
las ac o izaciones en p imos de nya espec i amen e. Pa a demos a (1) no amos
que γ(p) = −1
ppa a odo p imo impa ppo pu a de inici´on de γ. As´ı enemos que
−1
n=
Y
i=1 −1
piei
=
Y
i=1
γ(pi)ei=γ
Y
i=1
pei
i!=γ(n)
P oba (2) es simila , ap o echando la de inici´on de βy su es uc u a de homomo -
ismo de g upos β(pi) = 2
pi,
2
n=
Y
i=1 2
piei
=
Y
i=1
β(pi)ei=β
Y
i=1
pei
i!=β(n)
El e ce pun o es pa ecido, aunque hacemos uso de la Ley de Recip ocidad de Gauss
3.2. C´
ALCULO EFECTIVO DEL S´
IMBOLO DE JACOBI
y de la e ce a p opiedad in uducida como inmedia a:
a
nn
a=
Y
i=1 a
piei
·
s
Y
j=1 n
qj j
=
Y
i=1 

s
Y
j=1 qj
pi j

ei
·
s
Y
j=1
Y
i=1 pi
qjei! j
=
Y
i=1
s
Y
j=1 qj
pi jeipi
qjei j!
=
Y
i=1
s
Y
j=1 qj
pi2
(−1)(pi−1)/2·(qj−1)/2!ei j
Pe o qj
pi2= 1, luego enemos:
a
nn
a=
s
Y
i=1
s
Y
j=1
(−1)ei j(pi−1)/2·(qj−1)/2
=
Y
i=1 

s
Y
j=1
(−1) j(qj−1)/2

ei
=
Y
i=1
γ(a)ei(pi−1)/2
=(1 si γ(a) = 1 o si γ(n)=1
−1 si γ(a) = γ(n) = −1
=(1 si a≡1 (m´od 4) o si n≡1 (m´od 4)
−1 si a≡n≡3 (m´od 4)
□
Demos una idea gene al del p ocedimien o del c´alculo de mane a e ec i a sin la
necesidad de ac o iza como al.
En p ime luga , se educe ex ayendo ac o es 2 del siguien e modo : 2a
n=a
n
si n≡ ±1 (m´od 8); en o o caso, 2a
n=−a
n=m
n, a endiendo al segundo
pun o de la Ley de Recip ocidad (R2).
Una ez hecho es o, si mynson ambos impa es, en onces m
n=n
m=b
m
sal o que mynsean ambos cong uen es con 3 m´odulo 4, en cuyo caso m
n=
−n
m=b
m, es deci , aplica el e ce pun o de la Ley de Recip ocidad (R3).
Aho a oca calcula la di isi´on eucl´ıdea (D) y educi bm´odulo m, quedando

m.

3.2. C´
ALCULO EFECTIVO DEL S´
IMBOLO DE JACOBI
Vol emos al pun o de pa ida y epe imos odos los pasos las eces que sea ne-
cesa io has a llega a una si uaci´on −1
poq
p, con q < p p imos (es a ´ıamos en
el caso del s´ımbolo de Legend e), acudiendo a la Ley de Recip ocidad de Gauss de
nue o pa a el c´alculo inal y di ec o del esul ado.
Veamos c´omo calcula el s´ımbolo de Jacobi 1008
2307 u ilizando las p opiedades is-
as.
1008
2307R2
=2
2307 2
2307 2
2307 2
2307 63
2307
R2
= (−1)463
2307=63
2307
R3
= (−1) 2307
63 
D
= (−1) 39
63
R3
= (−1)(−1) 63
39=63
39
R3
=24
39
R2
=2
392
392
393
39= 133
39
R3
= (−1) 39
3= 0.
Po lo an o, g acias a es e c´alculo del s´ımbolo de Jacobi y la exponenciaci´on
modula , ambos equi iendo O(log3(n)), el iempo o al pa a ki e aciones del Tes
de Solo ay–S assen es O(klog3(n)), como adelan amos en la secci´on p e ia.
Aunque es e es es simple y ´acil de implemen a , lo que lo hace ´apido pa a
n´ume os peque˜nos y medianos, no es e icien e pa a n´ume os muy g andes, ya que la
complejidad del iempo c ece c´ubicamen e con el ama˜no de en ada. A con inuaci´on,
se p esen a un es cuya p obabilidad de e o es meno que la de Solo ay-S assen,
po lo que en la ac ualidad es e ´ul imo ha quedado supe ado.
Cap´ı ulo 4
Tes de Mille –Rabin
His ´o icamen e, el Tes de Solo ay–S assen ue el p ime es p obabil´ıs ico de
p imalidad. Poco despu´es de que apa ecie a es e es , ue eclipsado po el Tes de
Mille –Rabin, que es m´as ´acil de implemen a (no se necesi an s´ımbolos de Jacobi)
y m´as e ec i o, ya que a pesa de se un es p obabil´ıs ico, educe la p obabilidad de
e o m´as ´apidamen e que Solo ay–S assen, como e emos al inal del cap´ı ulo.
Su o igen se emon a a 1976. Las ideas o iginales de Ga y Mille es aban ´ın i-
mamen e elacionadas con uno de los p oblemas abie os m´as ese˜nables en eo ´ıa
de n´ume os: la Hip´o esis Gene alizada de Riemann (GRH), una gene alizaci´on de
la Conje u a 1.12 que debemos a Pil z, a inales del siglo XIX. En e ec o, si es a
ue a cie a, en onces el es de e minis a o iginal end ´ıa una complejidad de o den
O(log4n) [23], ela i amen e e icien e en compa aci´on con muchos o os p oblemas
compu acionales. Aunque, como ya an icipamos en la secci´on de esul ados gene a-
les, la Hip´o esis Gene alizada de Riemann pese a que es conside ado un p oblema
de eno me impo ancia en la ma em´a ica con empo ´anea, sigue abie o a d´ıa de hoy,
luego no esul a de ini i o ene un es e ec i o si pa a su implemen aci´on hacemos
uso de ´el.
Fue Michael Rabin, sob e el a˜no 1980 [30], quien modi ic´o el es eliminando la
dependencia de la GRH. No obs an e, es a nue a e si´on hizo al algo imo pe de
e iciencia compu acional y es la que ecibe hoy en d´ıa el nomb e de Tes de Mille –
Rabin. P esen amos a con inuaci´on es e es p obabil´ıs ico de ipo Mon eca lo.
Obse aci´on 4.1 Reco demos, como ya ha apa ecido alguna ez en es a memo ia,
que si pes un p imo y aun en e o al que a2≡1 (m´od p), en onces a≡1 (m´od p)
o bien a≡ −1 (m´od p).
Es o es di ec o, ya que dado un p imo p, en el cue po Fp, las ´unicas a´ıces de 1
31
(es deci , las a´ıces del polinomio x2−1) son 1 y −1.
Lema 4.2 Sea un p imo n > 2 y sea a∈Un. Esc ibamos n= 2sd+ 1 con dimpa .
En onces se e i ica una de las dos condiciones siguien es,
1. ad≡1 (m´od n).
2. a2 d≡ −1 (m´od n), pa a alg´un 0 ≤ < s.
Demos aci´on: Conside emos la sucesi´on
a2sd, a2s−1d, . . . , a2d, ad;
donde obse emos que cada ´e mino de la sucesi´on es el cuad ado del pos e io .
Po el eo ema de Fe ma ,
a2sd=an−1≡1 (m´od n),
luego (a2s−1d)2≡1 (m´od n) y po lo an o a2s−1des una a´ız cuad ada de 1 m´odulo
n. Po la obse aci´on an e io , ob enemos que
a2s−1d≡ ±1 (m´od n)
Si a2s−1d≡ −1 (m´od n), ob enemos el esul ado. En caso con a io, a2s−1d≡1
(m´od n), luego (a2s−2d)2≡1 (m´od n) y po lo an o a2s−2des una a´ız cuad ada de
1 m´odulo ny en consecuencia a2s−2d≡ ±1 (m´od n).
I e ando el azonamien o an e io , concluimos que alguno de los ´e minos de la
sucesi´on a2 d≡ −1 (m´od n), o bien odos los ´e minos son cong uen es a 1, en pa -
icula ad≡1 (m´od n). □
Nos encon amos en la misma si uaci´on que en el cap´ı ulo p e io, acabamos de
in oduci una nue a p opiedad que cumplen los n´ume os p imos. Sin emba go, nos
uel e a a aca la duda de si es a condici´on es es su icien e o necesa ia. ¿Todo nimpa
que cumpla la p opiedad del Lema 4.2 es p imo?
De inici´on 4.3 Sea un nun en e o impa de la o ma n= 2sd+ 1, con dimpa . Se
dice que nes un pseudop imo ( ue e) espec o de la base a∈Unsi cumple
alguna de las condiciones del Lema 4.2.
La siguien e p oposici´on pone de mani ies o que se pseudop imo ue e es m´as
exigen e que se pseudop imo de Eule y, po an o en pa icula no exis e el an´alogo
a los n´ume os de Ca michael pa a la p opiedad se pseudop imo ue e. Recupe ando
de nue o el ejemplo n= 2821, obse amos que es e es el meno n´ume o de Ca michael
que no es ni pseudop imo de Eule ni ue e en base 2.
P oposici´on 4.4 Sea nun pseudop imo ue e espec o de la base a, en onces nes
pseudop imo de Eule espec o de la base a.
Demos aci´on: Sea n−1 = 2sdcon dimpa y supongamos que nes pseudop imo
ue e en la base a. Tenemos que dis ingui dos casos, en pa alelo a la p opia de inici´on
de pseudop imalidad ue e.
Caso 1: Si ad≡1 (m´od n), en onces
a(n−1)/2=a2s−1d≡1 (m´od n),
y como des impa conse a el signo como exponen e, en onces
a
n=a
nd=ad
n=1
n= 1.
Caso 2: Supongamos que a2 d≡ −1 (m´od n) con 0 ≤ < s. Sea pun di iso p imo
de ny pongamos p−1 = 2 c, con cimpa . En onces
a2 dc ≡ −1 (m´od n)
y, po an o,
a2 dc ≡ −1 (m´od p) (4.1)
Po el Peque˜no Teo ema de Fe ma ambi´en enemos que
a2 dc =a2 cd≡1 (m´od p) (4.2)
De (4.1) y (4.2) se deduce que > . As´ı, u ilizando el C i e io de Eule (Teo ema
3.8) pa a p enemos
a
p=a
pd
=a(p−1)/2d=a2 −1dc =a2 dc2 −( +1)
= (−1)2 −( +1) (m´od p),
es deci ,
a
p=(1 si > + 1;
−1 si = + 1.(4.3)
Aho a bien, si npasa la p ueba pa a odas nues as elecciones alea o ias de a
(supongamos que in en amos kbases di e en es a) en onces sabemos po el Teo ema
4.7 que la p obabilidad de que nsea compues o,
Pnpasa el es ≤1
4k
,
Obs´e ese que es o es mejo que en el caso de la p ueba de Solo ay–S assen, donde
la es imaci´on an´aloga es una p obabilidad de 1/2k.
El c´alculo de nues os ejemplos el cual encon amos en el ap´endice, esul a:
12432902008176640000 compues o , es di isible po 2
23044260448006092643 compues o , pa o en la i e acion 0 con la base
1446122688032912871
31816787885244115403 p obablemen e p imo , pasa el es despues de 19
i e aciones
4T ue
A pesa de la baja p obabilidad de e o que podemos ob ene al i e a an as
eces como que amos, sigue habiendo una ca encia a la ho a de usa es e es , una
ca encia de independencia. Supongamos que a1ya2se eligen de an emano. Si nes
un pseudop imo en base a1, en onces es m´as p obable que sea pseudop imo en base
a2que un n´ume o que no lo e a en base a1. Po ejemplo, un pseudop imo en base 2 es
pseudop imo pa a muchas m´as bases que el n´ume o compues o impa p omedio del
mismo ama˜no no pseudop imo en base 2. De hecho, de los 21853 pseudop imos en
base 2 meno es que 25 ·109, 4709 de ellos ambi´en son pseudop imos en base 3; 2522
de ellos son pseudop imos en base 2, en base 3 y en base 5 simul ´aneamen e; y 1770
de ellos son pseudop imos en base 2, en base 3, en base 5 y en base 7 simul ´aneamen e
[27]. Si los hechos se pseudop imo en base a1y se pseudop imo en base a2 ue an
independien es, espe a ´ıamos que ninguno de los p ime os 21853 pseudop imos en
base 2 ue a pseudop imo en base 3, 5 ´o 7.
¿Pod ´ıamos elimina es a dependencia de alg´un modo? Pa a discu i es a a i ma-
ci´on, damos paso a una nue a de inici´on de pseudop imos y al ´ul imo es que nos
concie ne.

Cap´ı ulo 5
Tes de Baillie-PSW
5.1. Pseudop imos de Lucas
Pa a in oduci el ´ul imo ipo de pseudop imos hemos de de ini en p ime a ins-
ancia una amilia de sucesiones, que son la base de nues o nue o concep o.
De inici´on 5.1 ([2]) Sean D,PyQen e os al que D=P2−4Q= 0, y P > 0.
Sea U0= 0, U1= 1, V0= 2 y V1=P. De inimos ecu si amen e las sucesiones de
Lucas {Uk}y{Vk}con pa ´ame os {D, P, Q}como
Uk=PUk−1−QUk−2, Vk=P Vk−1−QVk−2.
Como podemos obse a , es as dos sucesiones ienen la misma ecu encia, su
´unica di e encia son las condiciones iniciales. Podemos e un an´alisis p o undo de
es as sucesiones en [4, Sec. 4]. Veamos a con inuaci´on una p opiedad que cumplen sin
da su demos aci´on, pues ecae en p opiedades gen´e icas de sucesiones.
P opiedad 5.2 ([2]) Sean αyβdos a´ıces del polinomio x2−Px +Q. Tomando
k≥0, enemos que
Uk=αk−βk
α−β, Vk=αk+βk.
De inici´on 5.3 En las condiciones an e io es, pa a odo nen e o impa , de inimos
δ(n) = n−ϵ(n), siendo ϵ(n) = D
nel s´ımbolo de Jacobi in oducido en el cap´ı ulo 3.
Obse aci´on 5.4 La unci´on δ(n) ´unicamen e oma los alo es {n−1, n, n + 1}.
41
5.1. PSEUDOPRIMOS DE LUCAS
Teo ema 5.5 Sea pun p imo impa al que gcd(Q, p) = 1, en onces Uδ(p)≡0
(m´od p).
Demos aci´on: La siguien e demos aci´on es ´a basada en de [25]. Igual que an es,
llamamos αyβa las a´ıces de x2−Px +Q. Pongamos
α=P+√D
2, β =P−√D
2.
Tenemos en onces
Un=αn−βn
√D,con αn= P+√D
2!n
, βn= P−√D
2!n
.
Despejamos P+√Dn−P−√Dny aplicamos la exp esi´on del binomio:
Un√D2n=P+√Dn−P−√Dn
=
n
X
k=0 n
kPn−k√Dk−
n
X
k=0 n
kPn−k−√Dk
=
n
X
k=0 n
kPn−kDk/2−(−1)kDk/2
= 2
n
X
k=1
kimpa n
kPn−kDk/2.
De es a mane a, enemos
Un=1
2n−1
n
X
k=1
kimpa n
kPn−kD(k−1)/2.
Aho a eamos qu´e alo es puede oma δ(p) con psea p imo, y hallemos Uδ(p)m´od p.
Caso 1: δ(p) = p. En onces, D
p≡0 m´od p. No ando que
p
k≡0,pa a 1 ≤k≤p−1,
emos que solo sob e i e el ´ul imo sumando:
Uδ(p)=Up= 21−pp
pP0D(p−1)/2= 21−pD(p−1)/2≡21−pD
p≡0 m´od p,
donde hemos u ilizado el C i e io de Eule 3.1 pa a ob ene inalmen e Uδ(p)≡0
m´od p.
5.1. PSEUDOPRIMOS DE LUCAS
Caso 2: δp=p+ 1. En onces, D
p≡ −1 m´od p. De nue o p+1
k≡0 m´od ppa a
2≤k≤p−1, as´ı:
Uδ(p)=Up+1 = 21−(p+1)
p
X
k=1
kimpa p+ 1
kPp+1−kD(k−1)/2
≡2−p(p+ 1)Pp+ (p+ 1)PD(p−1)/2
≡2−p(p+ 1)P(Pp−1+D(p−1)/2)
≡2−1P1 + D
p≡0 m´od p,
donde, apa e del C i e io de Eule , hemos usado el Peque˜no Teo ema de Fe ma con
P(p−1) ≡1 m´od p.
Caso 3: δp=p−1, es deci D
p≡1 m´od p. Aho a po de inici´on,
Up+1 =PUp−QUp−1
As´ı que,
QUp−1=PUp−Up+1 ≡PD
p−2−1P1 + D
p≡P−2−1P·2≡0 m´od p.
Aho a, como pno di ide a Q,Uδ(p)=Up−1≡0 m´od p.□
Podemos obse a que es a p opiedad que cumplen los p imos es an´aloga al Pe-
que˜no Teo ema de Fe ma pa a las sucesiones de Lucas, po lo que nos lle a a la
misma p egun a que nos hemos es ado haciendo has a aho a en cada cap´ı ulo: ¿Apa-
ecen n´ume os compues os cumpliendo es a p opiedad o po el con a io es cie o el
ec´ıp oco del Teo ema 5.5?
De inici´on 5.6 Un n´ume o compues o nse dice pseudop imo de Lucas con pa ´ame-
os PyQsi Uδ(n)≡0 m´od n.
En e ec o, seguimos sin ene una condici´on su icien e de p imalidad, un ejemplo de
pseudop imalidad de Lucas es 14209 = 13·1093 con los pa ´ame os P= 1, Q =−3.
5.2.5
Podemos encon a di e sos esul ados sob e la densidad de los pseudop imos de
Lucas que ponen en mani ies o su ango de apa ici´on en las se ies de Lucas en [25],
donde adem´as encon amos una co a an´aloga a la que dimos pa a los n´ume os de
Ca michael que con ola la ecuencia de es os.
5.1. PSEUDOPRIMOS DE LUCAS
Teo ema 5.7 Dados PyQ, deno amos po Lc(x) el n´ume o de pseudop imos de
Lucas con pa ´ame os PyQmeno es que x. Exis e una cons an e c al que pa a un
xlo su icien emen e g ande:
Lc(x)< x exp −cplog xlog log x
No obs an e, nues o obje i o no es an o analiza con p o undidad es os ipos de
pseudop imos, si pone los en elaci´on con los o os ipos de pseudop imos que hemos
p esen ado p e iamen e.
Un p ime esul ado que nos encamina al es que que emos p esen a y que p e-
ende da soluci´on al ema de la dependencia que in odujimos al inal del cap´ı ulo
an e io ue dado po Baillie y Wags a en [2]. En es e abajo, decla an habe p o-
bado 50 n´ume os de Ca michael peque˜nos con un es de p imalidad de Lucas y odos
ellos ue on de e minados co ec amen e como compues os. Es m´as, p ueban que los
21853 pseudop imos en base 2 que hay po debajo del umb al 25·109 ambi´en alla on
pa a es s de p imalidad de Lucas siguiendo las elecciones de pa ´ame os A y B que
aho a in oduci emos. E ec i amen e es azonable pensa que no hay solapamien os
(o hay muy pocos) en e los dos ipos de n´ume os y que una mane a muy e ec i a de
p oba la p imalidad se ´ıa combina un es de Mille con un es de Lucas.
No obs an e, pa a de e mina si un n´ume o es pseudop imo de Lucas, debemos
ija an es PyQ. ¿Hay p e e encias pa a la elecci´on de es os pa ´ame os?
En p ime luga , no escoge emos un Dque sea un esiduo cuad ´a ico m´odulo n1.
La az´on es sencilla: si D=b2, es deci , D
n= 1, y P=b+ 2, en onces Q=b+ 1 y
α=P+√D
2≡P+b
2=b+ 1 = Qm´od n, β =P−√D
2≡P−b
2= 1 m´od n
y, po an o
Uδ(n)=Un−1≡Qn−1−1
Q−1.
Po lo que Qn−1≡1 m´od n, es deci , es a ´ıamos ealizando una me a p ueba de
p imalidad como la de Solo ay-S assen. Una buena mane a de p e eni es o es ija
D
n=−1. Ob iamen e, si en la b´usqueda de un Dcumpliendo es o opamos con
D
n= 0 hab ´ıamos hallado un ac o de n(un es igo de p imalidad).
Aunque haya muchos m´e odos de hace la elecci´on [2], los dos m´as conocidos son:
M´e odo A (p opues o po John Sel idge): Sea Del p ime elemen o de la suce-
si´on 5,−7,9,−11,13, . . . pa a el cual D
n=−1. Sea P= 1 y Q= (1 −D)/4.
1Si en el segundo paso no se exige que el s´ımbolo de Jacobi D
n=−1, en onces un s´upe n´ume o
de Ca michael pasa el es , una nue a de inici´on de pseudop imo que dejamos como in e ´es del lec o .
5.1. PSEUDOPRIMOS DE LUCAS
M´e odo B (p e e ido po Baillie): Sea Del p ime elemen o de la sucesi´on
5,9,13, . . . al que D
n=−1. Sea Pel meno en e o impa que sea mayo a D1/2y
Q= (P2−D)/4.
Obse aci´on 5.8 [25] En el M´e odo A no in e esa D=−3, ya que en ese caso
P=Q= 1, lo cual gene a una sucesi´on de Lucas pe i´odica y, pa a es a, odos los n
impa es que no sean m´ul iplos de 3 son pseudop imos de Lucas con pa ´ame os 1, 1.
Obse aci´on 5.9 Con el M´e odo A los p ime os pseudop imos de Lucas que encon-
amos son: 323, 377, 1159, 1829 y 3827; mien as que con el M´e odo B hallamos: 323,
377, 1349, 2033 y 2651. Se deja al lec o cu iosea sob e la lis a de es os pseudop imos
y de odos los is os has a aho a en OEIS 2.
Realmen e no es cie o que ning´un pseudop imo de Fe ma es pseudop imo de
Lucas, de hecho 341 es pseudop imo espec o a la base 2 y pseudop imo de Lucas
(7,2). Lo que Baillie y Wags a de ienden en [25] es que dado un pseudop imo en
base a, si buscamos sucesiones de Lucas pa a las cuales D
n=−1, acaba ´aemos
encon ´andolas, segu amen e.
Sin emba go, la mayo ´ıa de pseudop imos de Lucas con D
n=−1 son pseudop i-
mos de Fe ma pa a muy pocas bases a. Es a es la az´on po la que combinando los
pseudop imos ue es (que supe an el p oblema de los n´ume os de Ca michael) y los
pseudop imos de Lucas haciendo buena elecci´on de los pa ´ame os, ob enemos una
muy buena e idencia de p imalidad.
Aqu´ı nace el es que da nomb e a es e cap´ı ulo, concebido po p ime a ez po
Baillie (1980) con mejo as a˜nadidas po Pome ance, Sel idge y Wags a , que no es
o a cosa que una combinaci´on del es de Mille –Rabin y el de Lucas. Un pseudop imo
que pase el es ecibe el nomb e de BPSW.
Ca l Pome ance (1984) conje u ´o en [29] que hay in ini os pseudop imos BPSW,
a gumen ando ambi´en que pa a xlo su icien emen e g ande, el n´ume o de pseudo-
p imos BPSW meno es que xsupe a x1−µ, donde µes un n´ume o posi i o a bi a-
iamen e peque˜no p ede inido.
No obs an e, po el momen o no se han encon ado ejemplos de ales pseudop i-
mos, po lo que en caso de no exis i , implica ´ıa la exis encia de un es de p imalidad
2OEIS(Online Encyclopedia o In ege Sequences). Es una base de da os en l´ınea que con iene
in o maci´on sob e una a iedad de sucesiones num´e icas, incluidos los n´ume os de Ca michael, pseu-
dop imos de Eule , ue es y de Lucas, en e nume osas cosas m´as. Una ez que encuen es la sucesi´on
que es ´as buscando, puedes explo a sus p opiedades, ´o mulas ma em´a icas asociadas, e e encias
bibliog ´a icas y o os de alles que es ´en disponibles h p://oeis.o g/A005845

5.1. PSEUDOPRIMOS DE LUCAS
de e minis a en iempo polinomial . Es m´as, el 13 de junio de 2009, Je Gilch is
[15] con i m´o que no hay pseudop imos BPSW meno es que 1017 y es in e esan e con-
sul a es a e e encia, donde podemos obse a su abajo expl´ıci amen e. Tambi´en
se demues a en [24] que no exix e ning´un pseudop imo BPSW po debajo de 264
(264 ≈1845 ·1019).
In oduzcamos po in el algo i mo de una a ian e del es dada po Pome ance
en 1984:
Algo i hm 4 Algo i mo BPSW
En ada: (n, M)∈N≥3×N, con nimpa y Muna co a supe io pa a di iso es
sencillos
Salida: n compues o on p obablemen e p imo
1: Comp oba si n iene di iso es meno es que M.
2: Realice a nuna p ueba de Mille –Rabin en base 2.
1. Si nno es un pseudop imo ue e con base 2, de ene se; n compues o.
2. Si lo es, con inua con el paso siguien e.
3: Realice a nuna p ueba de Lucas median e las elecciones del M´e odo A o B.
1. Si nno es un pseudop imo de Lucas, de ene se; n compues o.
2. Si lo es, n p obablemen e p imo.
Obse aci´on 5.10 El p ime paso es s´olo po e icacia ya que en caso de que enga un
di iso p imo peque˜no no end ´ıa sen ido con inua con el algo imo. En el segundo
paso se elige la base 2 pues se conocen muchos esul ados sob e los pseudop imos
ue es en base 2 que los dis inguen de los pseudop imos de Lucas, y po an o, su
combinaci´on hace buen abajo en dis ingui los n´ume os p imos de los compues os.
No obs an e, o as bases pod ´ıan unciona igual de bien.
Obse aci´on 5.11 No hay mejo a en cuan o al o den de complejidad espec o a los
algo i mos ya is os pues es una combinaci´on de ambos, y an o el es de Mille –
Rabin como el de Lucas ienen complejidad O(log3n).
Aplicando el alo imo a nues os ejemplos implemen ado en el Ap´endice 5.2.4
ob enemos:
1is_p obable_bpsw_p ime (n1 ,20)
2OUT: ’compues o , iene como ac o ’, 2
3is_p obable_bpsw_p ime (n2 ,20)
4OUT: ’compues o , alla es de Mille en base 2’
5is_p obable_bpsw_p ime (n3 ,20)
5.2. EJEMPLO DE APLICACI´
ON CON SAGEMATH
6OUT: 1375749999709520848 1001324354255196490
7’compues o , alla es de Lucas pa a los pa ame os an e io es ’
5.2. Ejemplo de aplicaci´on con SageMa h
Muchos sis emas de ´algeb a compu acional y paque es de so wa e u ilizan alguna
e si´on de la p ueba de p imalidad de Baillie-PSW. Algunos ejemplos son la unci´on
isp ime de Maple, la unci´on P imeQ de Ma hema ica, las unciones isp ime y ispseu-
dop ime de PARI/GP, en e muchos o os. Un en pa icula y de nues o in e ´es es
la unci´on en SageMa h is pseudop ime de SageMa h documen a ion, que usa una
e si´on de la p ueba de p imalidad de Baillie-PSW combinando una p ueba de p imos
p obables ue es de Fe ma y una p ueba de Lucas.
Como hemos is o p e iamen e, es e es esul a in alible pa a n´ume os meno es
que 264 [24], po lo que se con ie e en un algo imo de e minis a al abaja con n´ume-
os meno es que es a magni ud. Es o nos ha pe mi ido calcula el da o π(2,5×1010)
de la abla compa a i a en e n´ume os de Ca michael y p imos meno es que x. Debi-
do a que ya en´ıamos el da o π(1010), hemos in en ado aho a memo ia calculando
´unicamen e los p imos en e los umb ales. El p ocedimien o ha sido el siguien e:
1de con a _p imos (n , x):
2con ado = 0
3 o iin ange (n + 1, x):
4i is_pseudop ime (i):
5con ado += 1
6 e u n con ado
7
8con a _p imos (10^(10) , in (2.5*10^(16)))
9OUT:
10 636934894
Po lo an o, g acias al da o π(1010) de la abla 2.2, ob enemos con o al iabilidad
π(2,5·1010) = 636934894 + 455052511 = 1099985405.
Es in e esan e compa a es e esul ado con la misma p ueba usando ´unicamen e
Mille -Rabin con k= 5 bases, cuyo c´alculo encon a ´eis en la secci´on del Ap´endice
5.2.6. El c´alculo ealizado con SageMa h, que lle ´o m´as de 30 ho as, dio el mismo
esul ado que usando el es Baillie-PSW. Con es o concluimos que e ec i amen e no
hay pseudop imos ue es que sean a su ez pseudop imos de Lucas pa a n´ume os
meno es que el umb al π(2,5·1010).
Ap´endice: Implemen aci´on en
SageMa h
P esen amos en es e ap´endice la implemen aci´on con ejemplos en SageMa h de
los algo i mos expues os en el abajo; en pa icula , el de Solo ay-S assen, Mille -
Rabin y Baillie-PSW. Adem´as, se comp ueba la pseudop imalidad de un pseudop imo
de Lucas y se p esen a el c´alculo de π(x) con xen e 1010 y 2,5×1010 u ilizando
Mille -Rabin.
5.2.1. Elecci´on de nicon SageMa h
1# N ’ ume o de 19 ci as con ac o es p imos peque ~ nos
2n1 = ac o ial (20)
3
4# C ’ alculo de dos p imos g andes cuyo p oduc o esul e en un n ’ ume o
de 19
5ci as
6k = 9
7a = ZZ . andom_elemen (10^( k -1) , 10^ k). nex _p ime ()
8b = ZZ . and om_ ele men (10^(( k +1) -1) , 10^( k +1) ). nex _p ime ()
9n2 = a * b
10 # Calculo de un p imo de 19 ci as
11 l = 19
12 n3 = ZZ. andom_elemen (10^(l -1) , 10^ l). nex _p ime ()
13 # Mos a los esul ados
14 p in ("n1 :", 2432902008176640000)
15 p in ("n2 :", 3840536061136845209)
16 p in ("n3 :", 1816787885244115403)
5.2.2. P imalidad de nicon Solo ay-S assen
Implemen amos el algo i mo de Solo ay-S assen, pa a ello se usan las uncio-
nes implemen adas en SageMa h: jacobi symbol, impo ada de sage.a i h.misc,
48
5.2. EJEMPLO DE APLICACI´
ON CON SAGEMATH
ypowe mod, las cuales hacen un c´alculo e ec i o del S´ımbolo de Jacobi y la ex-
ponenciaci´on modula espec i amen e, con una peque˜na modi icaci´on de la unci´on
jacobi symbol como sigue:
1 om sage . a i h . misc impo jacobi_symbol
2de jacobi (a ,n ):
3i jacobi_symbol (a, n)== -1:
4 e u n n -1
5else:
6 e u n jacobi_symbol (a , n)
As´ı queda:
1impo andom
2de Solo ayS assen (n , k):
3 o iin ange (1, k+1):
4a = andom . andin (2 , n -1)
5i gcd (a,n) !=1:
6p in (n , "es compues o y alla el es en la i e acion ", i ,
"con la base ", a)
7 e u n False
8i jacobi (a , n) != powe _mod (a , (n -1) //2 , n):
9p in (n , "es compues o y alla el es en la i e acion ", i ,
"con la base ", a)
10 e u n False
11
12 p in (n , "es p obablemen e p imo y pasa el es as 20 i e aciones "
)
13 e u n T ue
14
15 Solo ayS assen (n1 , 20)
16 Solo ayS assen (n2 , 20)
17 Solo ayS assen (n3 , 20)
18
19 OUT:
20 2432902008176640000 es compues o y alla el es en la i e acion 1 con
la base 1868969210451108746
21 3044260448006092643 es compues o y alla el es en la i e acion 1 con
la base 2680792065180999020
22 1816787885244115403 es p obablemen e p imo y pasa el es as 20
i e aciones
5.2.3. P imalidad de nicon Mille -Rabin
1impo andom
2de mille _ abin(n, k=20):
3i n <= 1:
4 e u n False
BIBLIOGRAF´
IA
[28] C. Pome ance: On he dis ibu ion o pseudop imes. Ma h. Comp. 37 (1981)
587–593.
[29] C. Pome ance: A e he e coun e -examples o he Baillie-PSW p imali y
es ? P ep in (1984) h ps://web.a chi e.o g/web/20191121062007/h p:
//www.pseudop ime.com/dopo.pd
[30] M. O. Rabin P obabilis ic Algo i hm o Tes ing P imali y. Jou nal o Numbe
Theo y 12 (1980) 128–138.
[31] R. Ri es , A. Shami , L. Adleman: A Me hod o Ob aining Digi al Signa u es
and Public-Key C yp osys ems. Communica ions o he ACM 21 (2) 120–126.
[32] K.H. Rosen: Elemen a y numbe heo y and i s applica ions, 5 h Edi ion.
Pea son/Addison-Wesley (2005).
[33] B. Rosse : The n- h p ime is g ea e han nlog(n).P oceedings o he London
Ma hema ical Socie y 2(1939) 21–44.
[34] R.M. Solo ay, V. S assen: A as Mon e-Ca lo es o p imali y. SIAM Jou nal
on Compu ing 6(1977) 84–85.
[35] J.L. Va ona: Reco idos po la Teo ´ıa de N´ume os, 2a Edici´on. Elec olib is
(2019).