Teorema lui Prot

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 28 februarie 2017; verificările necesită 6 modificări .

În teoria numerelor, teorema lui Proth este un test de primalitate pentru numerele lui Proth .

Formulare

Teorema lui Proth spune:

Dacă p este un număr Prota de forma , unde k este impar și , atunci p este prim (numit prim Prota ) dacă și numai dacă pentru un nerezidu pătratic a se face comparația: $k\cdot 2^{n}+1$ $k<2^{n)$

a^{(p-1)/2}\equiv -1{\pmod {p))

Dovada

(a) Fie p prim. Atunci pentru orice nerezidu pătratic a : după criteriul lui Euler . $a^{(p-1)/2}\equiv -1{\pmod {p))$

(b) Fie pentru unele nereziduuri pătratice a . Folosim criteriul Pocklington , unde . Atunci este singurul divizor prim . Să verificăm îndeplinirea condițiilor criteriului: $a^{(p-1)/2}\equiv -1{\pmod {p))$ $n=2^{k}+1$ $q=2$ $n-1$

$a^{n-1}=(a^{(n-1)/2})^{2}\equiv 1{\pmod {n))$ - efectuat.
numerele n și coprime — gata. $a^{(n-1)/q}-1$

Deoarece condiția este îndeplinită, n este prim. [unu] $2^{k}>{\sqrt {n}}-1$

Testarea numerelor Proth pentru primalitate

Teorema lui Proth poate fi folosită pentru a testa primalitatea numerelor Proth. Algoritmul de testare probabilistică bazat pe teoremă este următorul: Un număr întreg este selectat aleatoriu astfel încât și calculează . Sunt posibile următoarele rezultate: $A$ $a\not \equiv 1{\pmod {p}}\$ $b\equiv a^{(p-1)/2}{\pmod {p}}\$

$b\equiv -1{\pmod {p}}\$ , atunci este prim după teorema Proth. $p$
$b\not \equiv \pm 1{\pmod {p}}\$ și , atunci este compus, deoarece sunt divizori netriviali ai . $b^{2}\equiv 1{\pmod {p}}\$ $p$ $gcd(b\pm 1,p)$ $p$
$b^{2}\nu \equiv 1{\pmod {p}}\$ , atunci p este compus după mica teoremă a lui Fermat .
$b\equiv 1{\pmod {p}}\$ , atunci rezultatul testului este necunoscut.

Rezultatul (4) este motivul pentru care testul este probabilist. În cazul (1) , este un modulo patratic nereziduu . Procedura se repetă până când se stabilește simplitatea. Dacă este prim, atunci testul va confirma acest lucru cu o probabilitate într-o iterație, deoarece numărul de nereziduuri patratice modulo este exact . [2] $A$ $p$ $p$ $p$ $1/2$ $p$ $(p-1)/2$

Exemple

pentru p = 3, 2 1 + 1 = 3 este un multiplu al lui 3, deci 3 este prim.
pentru p = 5, 3 2 + 1 = 10 este un multiplu al lui 5, deci 5 este prim.
p = 13, 5 6 + 1 = 15626 este divizibil cu 13, 13 este prim.
pentru p = 9, care nu este prim, nu există b astfel încât a 4 + 1 să fie divizibil cu 9.

Prota prime

Primele Prot formează o secvență:

3 , 5 , 13 , 17 , 41 , 97 , 113 , 193 , 241 , 257 , 353 , 449, 577, 641, 673, 769, 929, 1153 secvența … ( OE8007 )

Din mai 2017, cel mai mare prim cunoscut al lui Proth, 10223 2 31172165 + 1, a fost găsit de proiectul Primegrid . Are 9383761 de cifre zecimale și este cel mai mare prim non-Mersenne cunoscut . [3]

Teorema lui Proth generalizată

Lema. Fie pentru unele prime l și . Fie puterea unui număr prim, unde . Dacă și , atunci n este prim . $n=l^{k)$ $k\geqslant 1$ $r^{e)$ $r\neq l$ $r^{e}{\mathcal {j}}\phi (n)$ $r^{e}>{\sqrt {n)}$

Dovada. este un divizor , deci . Dacă , atunci este o contradicție. Prin urmare , și este simplu.

r^{e)

\phi (n)=(l-1)l^{k-1)

r^{e}{\mathcal {j}}l-1

k>1

\phi (n)\geqslant (l-1)l>r^{2}e>n

k=1

n

Teoremă (teorema lui Proth generalizată). Lăsați câteva numere prime și întregi . Lasă . Dacă și pentru un număr întreg , atunci este prim. $N=r^{e}t+1$ $r$ $e,t\geqslant 1$ $r^{e}>t$ $a^{N-1}\equiv 1(modN)$ $a^{(N-1)/r}\nu \equiv 1(modN)$ $A$ $N$

Dovada teoremei generalizate poate fi găsită în Sze [4] .

Istorie

François Prot (1852-1879) a publicat teorema în jurul anului 1878.

Vezi și

numărul Sierpinski

Note

↑ Public Key Cryptography: Applications and Attacks Arhivat 18 decembrie 2013 la Wayback Machine
↑ Dovada primarității deterministe pe numerele proth arhivate pe 7 mai 2021 la Wayback Machine
↑ Top Twenty Major Known Primes Arhivat 16 iulie 2012 la Wayback Machine
↑ Sze, 2007 .

Link -uri

Weisstein, Teorema lui Eric W. Proth (engleză) pe site-ul Wolfram MathWorld .
„Review of primality checks” , Kuchin, 2005
Sze, T. W. Despre rezolvarea ecuațiilor polinomiale univariate peste câmpuri finite și a unor probleme înrudite . - Universitatea din Maryland, College Park, 2007. - ISBN 9780549451037 .