Prot tétele

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2017. február 28-án felülvizsgált verziótól ; az ellenőrzések 6 szerkesztést igényelnek .

A számelméletben a Proth-tétel a Proth - számok elsődlegességi tesztje .

Megfogalmazás

Proth tétele ezt mondja:

Ha p egy formájú Prota-szám , ahol k páratlan és , akkor p prím (úgynevezett Prota prím ) akkor és csak akkor, ha valamilyen a másodfokú nem-maradékra az összehasonlítást elvégezzük: $k\cdot 2^{n}+1$ ${\displaystyle k<2^{n))$

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

Bizonyítás

(a) Legyen p prím. Ezután bármely a másodfokú nem-maradékra : az Euler-kritérium szerint . $a^{(p-1)/2}\equiv -1{\pmod {p))$

(b) Legyen valamely másodfokú nem-maradékra a . A Pocklington-kritériumot használjuk , ahol . Ekkor az egyetlen prímosztó . Ellenőrizzük a kritérium feltételeinek teljesülését: $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))$ - előadták.
n számok és koprím — kész. $a^{(n-1)/q}-1$

Mivel a feltétel teljesül, n prím. [egy] $2^{k}>{\sqrt {n}}-1$

Proth-számok tesztelése elsődlegesség szempontjából

A Proth-tétel felhasználható a Proth-számok elsődlegességének tesztelésére. A tételen alapuló valószínűségi vizsgálati algoritmus a következő: Egy egész számot véletlenszerűen választunk ki úgy, hogy és kiszámítja . A következő eredmények lehetségesek: $a$ $a\not \equiv 1{\pmod {p}}\$ $b\equiv a^{(p-1)/2}{\pmod {p}}\$

$b\equiv -1{\pmod {p}}\$ , akkor prím a Proth-tétel szerint. $p$
$b\not \equiv \pm 1{\pmod {p}}\$ és , akkor összetett, mivel nem triviális osztói . $b^{2}\equiv 1{\pmod {p}}\$ $p$ $gcd(b\pm 1,p)$ $p$
$b^{2}\not \equiv 1{\pmod {p}}\$ , akkor p a Fermat-féle kis tétel szerint összetett .
$b\equiv 1{\pmod {p}}\$ , akkor a teszt eredménye ismeretlen.

Az eredmény (4) az oka annak, hogy a teszt valószínűségi. Az (1) esetben ez egy másodfokú nem maradék modulo . Az eljárást addig ismételjük, amíg az egyszerűség létre nem jön. Ha prím, akkor a teszt ezt egy iterációval valószí- nűséggel megerősíti, mivel a másodfokú nem maradékok száma modulo pontosan . [2] $a$ $p$ $p$ $p$ $1/2$ $p$ $(p-1)/2$

Példák

p = 3 esetén 2 1 + 1 = 3 3 többszöröse, tehát 3 prím.
p = 5 esetén 3 2 + 1 = 10 5 többszöröse, tehát 5 prím.
p = 13, 5 6 + 1 = 15626 osztható 13-mal, 13 prím.
p = 9 esetén , ami nem prím, nincs olyan b , amelyre a 4 + 1 osztható lenne 9-cel.

Prota prímszámok

A Prot prímek sorozatot alkotnak:

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

2017 májusában a Proth legnagyobb ismert prímszámát, a 10223 2 31172165 + 1-et a Primegrid projekt találta meg . 9383761 tizedesjegyből áll, és a legnagyobb ismert nem Mersenne-prím . [3]

Általánosított Proth-tétel

Lemma. Legyen néhány prím l és . Legyen egy prímszám hatványa, ahol . Ha és , akkor n prím . ${\displaystyle n=l^{k))$ $k\geqslant 1$ ${\displaystyle r^{e))$ $r\neq l$ $r^{e}{\mathcal {j}}\phi (n)$ $r^{e}>{\sqrt {n))$

Bizonyíték. egy osztó , tehát . Ha , akkor ez ellentmondás. Ezért , és egyszerű.

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

Tétel (általánosított Proth-tétel). Legyen néhány prím és egész szám . Hadd . Ha és valamilyen egész számra , akkor a prím. $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$

Az általánosított tétel bizonyítása Sze [4]-ben található .

Történelem

François Prot (1852-1879) 1878 körül publikálta a tételt.

Lásd még

Sierpinski szám

Jegyzetek

↑ Nyilvános kulcsú titkosítás: alkalmazások és támadások archiválva 2013. december 18-án a Wayback Machine -nél
↑ Determinisztikus elsődlegesség-bizonyítás Proth-számokon archiválva 2021. május 7-én a Wayback Machine -nél
↑ A húsz legnagyobb ismert elsőszám archiválva 2012. július 16-án a Wayback Machine -nél
↑ Sze, 2007 .

Linkek

Weisstein, Eric W. Proth tétele (angolul) a Wolfram MathWorld weboldalán .
"Az elsődlegességi ellenőrzések áttekintése" , Kuchin, 2005
Sze, T. W. Az egyváltozós polinomegyenletek megoldásáról véges mezőkön és néhány kapcsolódó problémáról . - Marylandi Egyetem, College Park, 2007. - ISBN 9780549451037 .