Protin lause

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 28. helmikuuta 2017 tarkistetusta versiosta . tarkastukset vaativat 6 muokkausta .

Lukuteoriassa Prothin lause on Prothin lukujen primaalisuustesti .

Sanamuoto

Prothin lause sanoo:

Jos p on muodon Prota-luku , jossa k on pariton ja , niin p on alkuluku (kutsutaan Prota-alkuluvuksi ) silloin ja vain, jos vertailu suoritetaan jollekin neliölliselle ei-jäännökselle a : $k\cdot 2^{n}+1$ ${\displaystyle k<2^{n))$

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

Todiste

(a) Olkoon p alkuluku. Sitten mille tahansa neliölliselle ei-jäännökselle a : Eulerin kriteerillä . $a^{(p-1)/2}\equiv -1{\pmod {p))$

(b) Olkoon jollekin neliölliselle ei-jäännökselle a . Käytämme Pocklingtonin kriteeriä , jossa . Sitten on ainoa alkujakaja . Tarkastellaan kriteerin ehtojen täyttymistä: $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))$ - suoritettu.
numerot n ja koprime — tehty. $a^{(n-1)/q}-1$

Koska ehto täyttyy, n on alkuluku. [yksi] $2^{k}>{\sqrt {n}}-1$

Proth-lukujen testaaminen primaalisuuden varalta

Prothin teoreemaa voidaan käyttää Proth-lukujen primaalisuuden testaamiseen. Lauseen perustuva todennäköisyystestausalgoritmi on seuraava: Kokonaisluku valitaan satunnaisesti siten, että ja laskee . Seuraavat tulokset ovat mahdollisia: $a$ $a\not \equiv 1{\pmod {p}}\$ $b\equiv a^{(p-1)/2}{\pmod {p}}\$

$b\equiv -1{\pmod {p}}\$ , on sitten alkuluku Prothin lauseen mukaan. $s$
$b\not \equiv \pm 1{\pmod {p}}\$ Ja Sitten on komposiitti, koska ovat ei-triviaalit jakajat . $b^{2}\equiv 1{\pmod {p}}\$ $s$ $gcd(b\pm 1,p)$ $s$
$b^{2}\not \equiv 1{\pmod {p}}\$ , silloin p on yhdistelmä Fermatin pienellä lauseella .
$b\equiv 1{\pmod {p}}\$ , niin testitulos on tuntematon.

Tulos (4) on syy, miksi testi on todennäköisyys. Tapauksessa (1) se on neliöllinen ei-jäännösmoduuli . Toimenpide toistetaan, kunnes yksinkertaisuus on todettu. Jos on alkuluku, niin testi vahvistaa tämän todennäköisyydellä yhdessä iteraatiossa, koska neliöllisten ei-jäännösten lukumäärä modulo on täsmälleen . [2] $a$ $s$ $s$ $s$ $1/2$ $s$ ${\näyttötyyli (p-1)/2}$

Esimerkkejä

jos p = 3, 2 1 + 1 = 3 on 3:n kerrannainen, joten 3 on alkuluku.
jos p = 5, 3 2 + 1 = 10 on luvun 5 kerrannainen, joten 5 on alkuluku.
p = 13, 5 6 + 1 = 15626 on jaollinen luvulla 13, 13 on alkuluku.
jos p = 9, joka ei ole alkuluku, ei ole olemassa b :tä , joka a 4 + 1 olisi jaollinen 9:llä.

Prota alkuluvut

Prot-alkuluvut muodostavat sekvenssin:

3 , 5 , 13 , 17 , 41 , 97 , 113 , 193 , 241 , 257 , 353 , 449, 577, 641, 673, 769, 929, 1153… 0 ( OEIS6 A )

Toukokuusta 2017 lähtien Prothin suurin tunnettu alkuluku, 10223 2 31172165 + 1, on löydetty Primegrid- projektista . Siinä on 9383761 desimaalilukua ja se on suurin tunnettu ei- Mersennen alkuluku . [3]

Yleistetty Prothin lause

Lemma. Anna jonkin verran prime l ja . Antaa olla valta alkuluku, jossa . Jos ja , niin n on alkuluku . ${\näyttötyyli n=l^{k))$ $k\geqslant 1$ $r^{e}$ $r\neq l$ $r^{e}{\mathcal {j}}\phi (n)$ $r^{e}>{\sqrt {n))$

Todiste. on jakaja , joten . Jos , niin on ristiriita. Siksi ja on yksinkertainen.

r^{e}

{\displaystyle \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

Lause (yleistetty Prothin lause). Olkoon joitakin alkulukuja ja kokonaislukuja . Anna . Jos ja jollekin kokonaisluvulle , niin on alkuluku. $N=r^{e}t+1$ $r$ $e,t\geqslant 1$ $r^{e}>t$ $a^{N-1}\equiv 1(modN)$ $a^{(N-1)/r}\not \equiv 1(modN)$ $a$ $N$

Yleistetyn lauseen todistus löytyy julkaisusta Sze [4] .

Historia

François Prot (1852-1879) julkaisi lauseen noin 1878.

Katso myös

Sierpinskin numero

Muistiinpanot

↑ Julkisen avaimen salaus: Sovellukset ja hyökkäykset arkistoitu 18. joulukuuta 2013 Wayback Machinessa
↑ Deterministinen primaalisuuden todistaminen Proth-luvuilla arkistoitu 7. toukokuuta 2021 Wayback Machinessa
↑ Top Twenty Largest Known Primes Arkistoitu 16. heinäkuuta 2012 Wayback Machinessa
↑ Sze, 2007 .

Linkit

Weisstein, Eric W. Proth's Theorem (englanniksi) Wolfram MathWorld -verkkosivustolla .
"Primaliteettitarkastusten tarkistus" , Kuchin, 2005
Sze, T. W. Yksimuuttujaisten polynomiyhtälöiden ratkaisemisesta äärellisten kenttien yli ja joihinkin niihin liittyviin ongelmiin . - Marylandin yliopisto, College Park, 2007. - ISBN 9780549451037 .