Test de Pocklington-Lehmer

En matemàtiques, el test de Pocklington-Lehmer és una prova de primalidad ideada per Henry Cabourn Pocklington^[1] i per Derrick Henry Lehmer.^[2]

La prova utilisa una factorización parcial de $N - 1$ per a demostrar que un número entero $N$ és primer. Produïx una certea de primalidad en menys esforç que el test de Lucas, que requerix la factorización completa de $N - 1$ .

Criteri de Pocklington

La versió bàsica de la prova es basa en la teorema de Pocklington (o criteri de Pocklington) que es formula de la següent manera:

Siga $N > 1$ un sancer, i suponga's que existixen els número natural $a$ i $p$ tals que:

Plantilla:NumBlk

Plantilla:NumBlk Plantilla:NumBlk

Llavors $N$ és primer.^[3]

Nota: L'equació (Plantilla:EquationNote) és simplement un test de primalidad de Fermat. Si es troba qualsevol valor de $a$ , no divisible per $N$ , tal que l'equació (Plantilla:EquationNote) siga falsa, es pot concloure immediatament que $N$ no és primer (esta condició de divisibilidad no s'establix explícitament perque està implícita en l'equació (Plantilla:EquationNote)). Per eixemple, siga $N = 35$ . En $a = 2$ , es té que $a^{N - 1} \equiv 9 (\mod N)$ . Açò és suficient per a provar que $N$ no és primer.

Demostració

Suponga's que

N

no és primer. Açò significa que deu haver un cosí

q

, tal que

q \leq \sqrt{N}

dividix a

N

.

Ya que $p > \sqrt{N} - 1 \geq q - 1$ , $p > q - 1$ , i com $p$ és primer, $mcd (p, q - 1) = 1$ .

Per lo tant, deu existir un número entero $o$ , un invers multiplicativo de $p$ mòdul $q -1$ , en la propietat de que

Plantilla:NumBlk

i per lo tant, pel menuda teorema de Fermat

Plantilla:NumBlk

Açò implica que

1 \equiv a^{N - 1} (\mod q)

, per (Plantilla:EquationNote) des de

q | N

\equiv (a^{N - 1})^{u} \equiv a^{u (N - 1)} \equiv a^{u p ((N - 1) / p)} \equiv (a^{u p})^{(N - 1) / p} (\mod q)

,

\equiv a^{(N - 1) / p} (\mod q)

, per (Plantilla:EquationNote)

Açò demostra que $q$ dividix el $mcd ()$ en (Plantilla:EquationNote), i per lo tant este $mcd () \neq 1$ ; lo que implica una contradicció^[3]

Dau $N$ , si es poden trobar $p$ i $a$ que satisfacen les condicions de la teorema, llavors $N$ és primer. Ademés, el parell ( $p$ , $a$ ) constituïx una certea de primalidad que pot verificar-se ràpidament per a satisfer les condicions de la teorema, confirmant que $N$ és primer.

La principal dificultat és trobar un valor de $p$ que satisfaça (Plantilla:EquationNote). En primer lloc, sol ser difícil trobar un factor primer gran d'un número gran. En segon lloc, per a molts número primo $N$ , tal $p$ no existix. Per eixemple, $N = 17$ no té $p$ adequat perque $N - 1 = 2^{4}$ i $p = 2 < \sqrt{N} - 1$ , lo que viola la desigualtat en (Plantilla:EquationNote); atres eixemples inclouen els números

N = 19, 37, 41, 61, 71, 73,

i

97

.

Pero dau $p$ , trobar $a$ no és tan difícil.^[4] Si $N$ és primer, llavors per la chicoteta teorema de Fermat, qualsevol $a$ en l'interval $1 \leq a \leq N - 1$ satisfarà (Plantilla:EquationNote) (no obstant, els casos $a = 1$ i $a = N - 1$ són trivials i no satisfaran (Plantilla:EquationNote)). Este $a$ satisfarà (Plantilla:EquationNote) sempre que ord( $a$ ) no dividixca a $(N - 1) / p$ . Per lo tant, un $a$ elegit a l'encert en l'interval $2 \leq a \leq N - 2$ té bones possibilitats de funcionar. Si $a$ és un generador mod $N$ , la seua orde és $N-1$ i, per lo tant, es garantisa que el método funcionarà per a esta elecció.

Prova de Pocklington generalisada

La versió anterior de la versió de la teorema de Pocklington a voltes és impossible d'aplicar perque alguns cosins $N$ són tals que no hi ha cap primer $p$ que dividixca $N - 1$ a on $p > \sqrt{N} - 1$ . La següent versió generalisada de la teorema de Pocklington és més aplicable.^[5]^{<span title="Erro en la seqüencia d'órdens: no existix el mòdul «DecodeEncode».">: Plantilla:R/where}

Teorema: Factorícese $N - 1$ com $N - 1= AB$ , a on $A$ i $B$ són primers relatius, $A > \sqrt{N}$ . Es coneix la descomposició en factors primers de $A$ , pero no necessàriament es coneix la descomposició en factors primers de $B$ .

Si per a cada factor primer $p$ de $A$ existix un sancer $a_{p}$ tal que:

Plantilla:NumBlk

llavors N és primer.

Demostració
Siga $p$ un cosí que dividix a $A$ i siga $p^{e}$ la màxima potència de $p$ que dividix a $A$ . Siga $q$ un factor primer de $N$ . Per a el $a_{p}$ del conjunt corolari $b \equiv a_{p}^{(N - 1) / p^{e}} (\mod q)$ . Açò significa que $b^{p^{e}} \equiv a_{p}^{N - 1} \equiv 1 (\mod q)$ i per $mcd (a_{p}^{(N - 1) / p} - 1, N) = 1$ també $b^{p^{e - 1}} \equiv a_{p}^{(N - 1) / p} \equiv̸ 1 (\mod q)$ . Açò implica que l'orde de $b (\mod q)$ és $p^{e}$ Per lo tant, $p^{e} \| (q - 1)$ . La mateixa observació val per a cada factor de potència primer $p^{e}$ de A, lo que implica que $A \| (q - 1)$ . Específicament, açò significa que $q > A \geq \sqrt{N} .$ Si $N$ fora compost, necessàriament tindria un factor primer menor o igual que $\sqrt{N}$ . S'ha demostrat que no existix tal factor, lo que prova que $N$ és primer.

Comentaris

La prova de primalidad de Pocklington-Lehmer es deriva directament d'este corolari. Per a usar este corolari, primer trobe suficients factors de $N - 1$ per a que el producte d'eixos factors excedixca $\sqrt{N}$ .

Denomine's a este producte $A$ . Després, siga $B = (N - 1)/ A$ la porció restant no factorizada de $N - 1$ . No importa si $B$ és primer. Solament es necessita verificar que cap cosí que dividix a $A$ també dividix a $B$ , és dir, que $A$ i $B$ són primers relatius. Després, per a cada factor primer $p$ de $A$ , trobe's un $a_{p}$ que complixca les condicions (Plantilla:EquationNote) i (Plantilla:EquationNote) del corolari. Si es poden trobar tals $a_{p}$ , el corolari implica que $N$ és primer.

Segons Koblitz, $a_{p}$ = 2 sol funcionar.^[3]

Eixemple

Determinar si

N = 27457

és primer

Primer, busquen-se menuts factors primers de $N - 1$ . Ràpidament es troba que

N - 1 = 2^{6} \cdot 3 \cdot B = 192 \cdot B

.

Es deu determinar si $A = 192$ i $B = (N - 1) / A = 143$ complixen les condicions del corolari.

A^{2} = 36864 > N

, i aixina

A > \sqrt{N}

.

Per lo tant, s'ha factorizado lo suficient de $N - 1$ per a aplicar el corolari. També es deu verificar que $mcd (A, B) = 1$ .

No importa si $B$ és primer (de fet, no ho és).

Finalment, per a cada factor primer $p$ de $A$ , use's el método de prova i error per a trobar un $a p$ que satisfaça (Plantilla:EquationNote) i (Plantilla:EquationNote).

Per a $p = 2$ , prove's en $a_{2} = 2$ . Elevar $a_{2}$ a esta alta potència es pot fer de manera eficient usant exponenciación binaria:

a_{2}^{N - 1} \equiv 2^{27456} \equiv 1 (\mod 27457)

mcd (a_{2}^{(N - 1) / 2} - 1, N) = mcd (2^{13728} - 1, 27457) = 27457

.

Llavors, $a_{2} = 2$ satisfà (Plantilla:EquationNote) pero no (Plantilla:EquationNote). Com es permet un $a p$ diferent per a cada $p$ , prove's $a_{2} = 5$ en el seu lloc:

a_{2}^{N - 1} \equiv 5^{27456} \equiv 1 (\mod 27457)

mcd (a_{2}^{(N - 1) / 2} - 1, N) = mcd (5^{13728} - 1, 27457) = 1

.

Llavors $a_{2} = 5$ satisfà tant (Plantilla:EquationNote) com (Plantilla:EquationNote).

Per a $p = 3$ , el segon factor primer de $A$ , prove's en $a_{3} = 2$ :

a_{3}^{N - 1} \equiv 2^{27456} \equiv 1 (\mod 27457)

.

mcd (a_{3}^{(N - 1) / 3} - 1, N) = mcd (2^{9152} - 1, 27457) = 1

.

$a_{3} = 2$ satisfà tant (Plantilla:EquationNote) com (Plantilla:EquationNote).

Açò completa la demostració de que $N = 27457$ és primer. La certea de primalidad per a $N = 27457$ està basada en els dos parells $(p, a_{p})$ (2, 5) i (3, 2).

S'han elegit números menuts per a este eixemple, pero en la pràctica quan es comença a factorizar $A$ es poden obtindre factors que són en sí mateixos tan grans que el seu primalidad no és òbvia. No es pot provar que $N$ és primer sense provar que els factors de $A$ també són primers. En tal cas, s'usa la mateixa prova recursivamente en els factors grans de $A$ , fins que tots els número primo estiguen per baix d'un llindar raonable.

En l'eixemple anterior, es pot dir en certea que 2 i 3 són primers, i aixina s'ha provat el resultat obtingut. El certificat de primalidad és la llista de parells $(p, a_{p})$ , que es pot comprovar ràpidament en el corolari.

Si l'eixemple haguera inclós grans factors primers, el certificat seria més complicat. Primer consistiria en la ronda inicial de $a p$ que corresponen als factors 'primers' de $A$ . Després, per a cada factor de $A$ a on la primalidad era incerta, es tindrien més $a p$ , i aixina successivament per als factors d'estos factors fins a aplegar als factors dels que la primalidad és certa. Este procés pot continuar en moltes capes successives si el cosí inicial és gran, pero el punt important és que es pot generar un certificat que continga en cada nivell el cosí que es provarà i els $a p$ corresponents, que es poden verificar fàcilment.

Referències

↑ Pocklington, Henry C.. “The determination of the prime or composite nature of large numbers by Fermat's theorem”. Proceedings of the Cambridge Philosophical Society 18: 29–30.
↑ D. H. Lehmer. “Tests for primality by the converse of Fermat's theorem”. Bull. Amer. Math. Soc. 33: 327–340. doi:10.1090/s0002-9904-1927-04368-3.
↑ ^3,0 ^3,1 ^3,2 Koblitz, Neal (1994). A Course in Number Theory and Cryptography, 2nd edició (vol. 144), Springer. ISBN 0-387-94293-9.
↑ (2005) Handbook of Elliptic and Hyperelliptic Curve Cryptography, Boca Raton: Chapman & Hall/CRC.
↑ “New Primality Criteria and Factorizations of 2^m ± 1” . Mathematics of Computation 29: 620–647. doi:10.1090/S0025-5718-1975-0384673-1.

Bibliografia

Leonard Eugene Dickson, "History of the Theory of Numbers" vol 1, p 370, Chelsea Publishing 1952
Henry Pocklington, "Math. Quest. Educat. Claves", (2), 25, 1914, p 43-46 (Mathematical questions and solutions in continuation of the mathematical columns of "the Educational claves".)

Referències

Este artícul conté una traducció derivada de «Test de Pocklington-Lehmer» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[Pocklington-1] Pocklington, Henry C.. “The determination of the prime or composite nature of large numbers by Fermat's theorem”. Proceedings of the Cambridge Philosophical Society 18: 29–30.

[Lehmer-2] D. H. Lehmer. “Tests for primality by the converse of Fermat's theorem”. Bull. Amer. Math. Soc. 33: 327–340. doi:10.1090/s0002-9904-1927-04368-3.

[koblitz-3] 3,0 ^3,1 ^3,2 Koblitz, Neal (1994). A Course in Number Theory and Cryptography, 2nd edició (vol. 144), Springer. ISBN 0-387-94293-9.

[4] (2005) Handbook of Elliptic and Hyperelliptic Curve Cryptography, Boca Raton: Chapman & Hall/CRC.

[BLS75-5] “New Primality Criteria and Factorizations of 2^m ± 1” . Mathematics of Computation 29: 620–647. doi:10.1090/S0025-5718-1975-0384673-1.

[1]

[2]

[3]

[4]

[5]

Plantilla:R/where