Prots teorem

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 28 februari 2017; kontroller kräver 6 redigeringar .

I talteorin är Proths sats ett primatitetstest för Proths tal .

Formulering

Proths teorem säger:

Om p är ett Prota-tal av formen , där k är udda och , då är p primtal (kallat ett Prota-primtal ) om och endast om jämförelsen görs för någon kvadratisk icke-rest a : $k\cdot 2^{n}+1$ ${\displaystyle k<2^{n))$

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

Bevis

(a) Låt p vara primtal. Sedan för varje kvadratisk icke-rest a : enligt Eulers kriterium . $a^{(p-1)/2}\equiv -1{\pmod {p))$

(b) Låt för någon kvadratisk icke-rest a . Vi använder Pocklington-kriteriet , där . Då är den enda primtalsdivisorn . Låt oss kontrollera uppfyllandet av villkoren för kriteriet: $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))$ - genomförde.
tal n och coprime — klar. $a^{(n-1)/q}-1$

Eftersom villkoret är uppfyllt är n primtal. [ett] $2^{k}>{\sqrt {n}}-1$

Testa Proth-nummer för primalitet

Proths sats kan användas för att testa primaliteten hos Proth-tal. Den probabilistiska testalgoritmen baserad på teoremet är följande: Ett heltal väljs slumpmässigt så att och beräknar . Följande resultat är möjliga: $a$ $a\not \equiv 1{\pmod {p}}\$ $b\equiv a^{(p-1)/2}{\pmod {p}}\$

$b\equiv -1{\pmod {p}}\$ , är då primtal enligt Proth-satsen. $sid$
$b\not \equiv \pm 1{\pmod {p}}\$ och , då är sammansatt, eftersom är icke-triviala delare av . $b^{2}\equiv 1{\pmod {p}}\$ $sid$ $gcd(b\pm 1,p)$ $sid$
$b^{2}\not \equiv 1{\pmod {p}}\$ , då är p sammansatt av Fermats lilla teorem .
$b\equiv 1{\pmod {p}}\$ , då är testresultatet okänt.

Utfall (4) är anledningen till att testet är probabilistiskt. I fall (1) är det en kvadratisk icke-rester modulo . Proceduren upprepas tills enkelheten är etablerad. Om är primtal, kommer testet att bekräfta detta med en sannolikhet i en iteration, eftersom antalet kvadratiska icke-rester modulo är exakt . [2] $a$ $sid$ $sid$ $sid$ $1/2$ $sid$ $(p-1)/2$

Exempel

för p = 3 är 2 1 + 1 = 3 en multipel av 3, så 3 är primtal.
för p = 5 är 3 2 + 1 = 10 en multipel av 5, så 5 är primtal.
p = 13, 5 6 + 1 = 15626 är delbart med 13, 13 är primtal.
för p = 9, som inte är primtal, finns det inga b så att a 4 + 1 är delbart med 9.

Prota primtal

Prot-primtalen bildar en sekvens:

3 , 5 , 13 , 17 , 41 , 97 , 113 , 193 , 241 , 257 , 353 , 449 , 577 , 641 , 673 , 769 , 929 , 1153 , 1153 A0 ... ( 8 00IS sekvens 6 )

I maj 2017 har Proths största kända prime, 10223 2 31172165 + 1, hittats av Primegrid- projektet . Den har 9383761 decimalsiffror och är den största kända icke- Mersenne primtal . [3]

Generaliserade Proths teorem

Lemma. Låt för några prime l och . Låta vara makten av ett primtal, där . Om och , då är n primtal . ${\displaystyle n=l^{k))$ $k\geqslant 1$ $r^{e}$ $r\neq l$ $r^{e}{\mathcal {j}}\phi (n)$ $r^{e}>{\sqrt {n))$

Bevis. är en divisor , så . Om , då är en motsägelse. Därför och är enkel.

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

Sats (generaliserad Proths sats). Låt för några primtal och heltal . Låt . Om och för något heltal , då är primtal. $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$

Beviset för den generaliserade satsen finns i Sze [4] .

Historik

François Prot (1852-1879) publicerade satsen omkring 1878.

Se även

Sierpinski nummer

Anteckningar

↑ Public Key Cryptography: Applikationer och attacker arkiverade 18 december 2013 på Wayback Machine
↑ Bevisande av deterministisk primat på prothnummer arkiverad 7 maj 2021 på Wayback Machine
↑ De tjugo största kända primerna arkiverade 16 juli 2012 på Wayback Machine
↑ Sze, 2007 .

Länkar

Weisstein, Eric W. Proth's Theorem (engelska) på Wolfram MathWorld- webbplatsen .
"Review of primality checks" , Kuchin, 2005
Sze, T. W. Om att lösa univariata polynomekvationer över ändliga fält och några relaterade problem . - University of Maryland, College Park, 2007. - ISBN 9780549451037 .