Primalitás teszt - Primality test

Az elsődlegességi teszt egy algoritmus annak meghatározására, hogy egy bemeneti szám prím . A matematika egyéb területei között kriptográfiaként használják . Az egész szám faktorizációval ellentétben a primalitási tesztek általában nem adnak prímtényezőket , csak azt, hogy a bemeneti szám prím vagy sem. Faktorizációja Úgy gondolják, hogy a számítási nehéz feladat, mivel Prímtesztelés viszonylag könnyű (a futási idő van polinomiális a bemenet mérete). Néhány primitív teszt azt bizonyítja, hogy egy szám prímszám, míg mások, mint Miller – Rabin, azt bizonyítják, hogy egy szám összetett . Ezért az utóbbit pontosabban összetettségi tesztnek lehet nevezni az elsődlegességi tesztek helyett.

Egyszerű módszerek

A legegyszerűbb prímteszt van tárgyalás osztály : adott egy input szám, n , ellenőrzi, hogy egyenletesen osztható bármely prímszám 2 és √ n (azaz, hogy a szétválás nem hagy maradék ). Ha igen, akkor n jelentése kompozit . Ellenkező esetben príma .

Vegyük például a 100 -as számot, amely egyenletesen osztható ezekkel a számokkal:

2, 4, 5, 10, 20, 25, 50

Vegye figyelembe, hogy a legnagyobb tényező, 50, a fele a 100 -nak. Ez minden n -re érvényes : minden osztó kisebb vagy egyenlő .

Valójában, amikor minden lehetséges osztót tesztelünk , kétszer felfedezünk néhány tényezőt . Ennek megfigyelése érdekében írja át az osztók listáját terméklistaként, egyenként 100 -at:

2 × 50, 4 × 25, 5 × 20, 10 × 10, 20 × 5, 25 × 4, 50 × 2

Figyelje meg, hogy a 10  ×  10 -nél korábbi termékek csupán a korábbi termékekben szereplő számokat ismételgetik. Például az 5  ×  20 és a 20  ×  5 azonos számokból áll. Ez igaz minden n : minden egyedi osztója n számok kisebb vagy egyenlő, mint √ n , így nem kell keresni, hogy a múlt. (Ebben a példában √ n = √ 100 = 10.)

Minden 2 -nél nagyobb páros szám is kiküszöbölhető, mivel ha páros szám oszthatja az n -t , akkor a 2 is.

Használjuk a próbaosztást a 17 primalitásának tesztelésére. Csak √ n -ig terjedő osztókra kell tesztelnünk , azaz egész vagy kisebb számokra , nevezetesen 2, 3 és 4 -re . A 4 -et kihagyhatjuk, mert ez páros szám: A 4 egyenletesen oszthatja a 17 -et, a 2 is, és 2 már szerepel a listában. Ebből 2 és 3 marad. A 17 -et elosztjuk mindegyik számmal, és azt tapasztaljuk, hogy egyik sem osztja egyenletesen a 17 -et - mindkét osztás maradékot hagy. Tehát a 17 az elsődleges.

Ezt a módszert tovább fejleszthetjük. Figyeljük meg, hogy minden 3 -nál nagyobb prímszám 6 k ± 1 alakú , ahol k bármely 0 -nál nagyobb egész szám. Ez azért van, mert minden egész szám kifejezhető (6 k + i ) formában , ahol i = -1, 0, 1 , 2, 3 vagy 4. Vegye figyelembe, hogy 2 oszt (6 k + 0), (6 k + 2) és (6 k + 4) és 3 oszt (6 k + 3) . Tehát hatékonyabb módszer annak tesztelése, hogy n osztható -e 2 -vel vagy 3 -mal, majd ellenőrizze az űrlap összes számát . Ez háromszor gyorsabb, mint az összes szám tesztelése √ n -ig .

Továbbá általánosítva, minden c # -nél nagyobb prímszám ( c primorális ) c # · k + i alakú , mert i < c #, ahol c és k egész számok, és i azokat a számokat jelöli, amelyek a c # -ig coprime . Például legyen c = 6 . Ekkor c # = 2,3,5 = 30 . Minden egész szám 30 k + i , i = 0, 1, 2, ..., 29 és k egész szám. Azonban 2 osztja a 0, 2, 4, ..., 28; 3 osztja a 0, 3, 6, ..., 27; és 5 osztja a 0, 5, 10, ..., 25. Tehát minden 30 -nál nagyobb prímszám 30 k + i alakú , i = 1, 7, 11, 13, 17, 19, 23, 29 (azaz az i <30 olyan, hogy GCD ( i , 30) = 1 ). Vegye figyelembe, hogy ha i és 30 nem lenne coprime, akkor 30 k + i osztható lenne egy 30 -as prímosztóval, nevezetesen 2 -vel, 3 -mal vagy 5 -el, és ezért nem lenne prím. (Megjegyzés: Nem minden szám felel meg a fenti feltételeknek. Például: 437 c#k+i formában van, ha c#(7) = 210, k = 2, i = 17. A 437 azonban összetett szám egyenlő 19*23).

A c → ∞ függvényében csökken azoknak az értékeknek a száma, amelyeket a c # k + i át tud venni egy bizonyos tartományon, és így csökken az n teszteléséhez szükséges idő . Ehhez a módszerhez azt is ellenőrizni kell, hogy osztható -e minden olyan prímszámmal, amely kisebb, mint c . Az előzőekhez hasonló megfigyelések rekurzívan is alkalmazhatók , így Eratosthenes szitáját kapjuk .

Jó módszer ezeknek a módszereknek (és az alábbiakban felsorolt ​​összes többi) felgyorsításának, ha előre kiszámítjuk és tároljuk az összes prímszám listáját egy bizonyos határértékig, mondjuk az összes prímszámot 200-ig. (Egy ilyen lista kiszámítható a Eratosthenes szitája, vagy egy algoritmus segítségével, amely minden egyes növekményes m -et minden ismert prímszámmal összehasonlít < √ m ). Ezután a vizsgálat előtt n az primality komoly módszer, n először ellenőrizni kell oszthatóság minden elsődleges a listából. Ha a számok bármelyikével osztható, akkor összetett, és további tesztek kihagyhatók.

Egy egyszerű, de nagyon nem hatékony primalitási teszt Wilson -tételt használja , amely szerint p akkor és csak akkor prím, ha:

Bár ez a módszer nagyjából p moduláris szorzást igényel , de nem praktikus, a prímekre és a moduláris maradékokra vonatkozó tételek sokkal több gyakorlati módszer alapját képezik.

Példakód

Piton

A következőkben egy egyszerű primalitási tesztet végeztünk Python -ban , a korábban említett egyszerű 6 k ± 1 optimalizálással. Az alábbiakban ismertetett kifinomultabb módszerek sokkal gyorsabbak nagy n esetén .

def is_prime(n: int) -> bool:
    """Primality test using 6k+-1 optimization."""
    if n <= 3:
        return n > 1
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i ** 2 <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

C#

Az alábbiakban egy C# primalitási teszt látható, a fentiekkel megegyező optimalizálással. 

bool IsPrime(int n)
{
    if (n == 2 || n == 3)
        return true;

    if (n <= 1 || n % 2 == 0 || n % 3 == 0)
        return false;

    for (int i = 5; i * i <= n; i += 6)
    {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }

    return true;
}

JavaScript

Az alábbiakban a JavaScript elsődlegességi tesztjét végezzük el, a fentiekkel megegyező optimalizálással.

function isPrime(num) {
  if (num <= 3) return num > 1;
  
  if ((num % 2 === 0) || (num % 3 === 0)) return false;
  
  let count = 5;
  
  while (Math.pow(count, 2) <= num) {
    if (num % count === 0 || num % (count + 2) === 0) return false;
    
    count += 6;
  }
  
  return true;
}

R

Az alábbiakban egy R (programozási nyelv) primalitási teszt látható, a fentiekkel megegyező optimalizálással. 

is.prime <- function(number) {
  if(number <= 1 || number %% 2 ==0 || number %% 3 == 0) {
    return (FALSE)
  } else if (number == 2 || number == 3 ) {
    return(TRUE)
  }
  i <- 5
  while (i*i <= number) {
    if(number %% i == 0 || number %% (i+2)==0) {
      return(FALSE)
    } else {
      return(TRUE)
    }
    i = i + 6
  }
  return(TRUE)
}

Heurisztikus tesztek

Ezek olyan tesztek, amelyek a gyakorlatban jól működnek, de nem bizonyítottak, ezért technikailag egyáltalán nem algoritmusok. A Fermat -teszt és a Fibonacci -teszt egyszerű példák, és nagyon hatékonyak kombinálva. John Selfridge sejtette, hogy ha p páratlan szám, és p ≡ ± 2 (mod 5), akkor p prím lesz, ha a következők mindegyike érvényes:

  • 2 p −1 ≡ 1 (mod p ),
  • f p +1 ≡ 0 (mod p ),

ahol f k a k -ik Fibonacci -szám . Az első feltétel a Fermat primalitási teszt, amely a 2 -es bázist használja.

Általánosságban elmondható, hogy ha p ≡ a (mod x 2 +4), ahol a másodfokú nem maradék (mod x 2 +4), akkor p legyen prímszám, ha a következő feltételek fennállnak:

  • 2 p −1 ≡ 1 (mod p ),
  • f ( 1 ) p +1 ≡ 0 (mod p ),

f ( x ) k a k -edik Fibonacci polinom x -nél .

Selfridge, Carl Pomerance és Samuel Wagstaff együtt 620 dollárt kínálnak ellenpéldáért. A probléma 2015. szeptember 11 -én még nyitott.

Valószínűségi tesztek

A valószínűségi tesztek szigorúbbak, mint a heurisztikák, mivel bizonyítható határokat biztosítanak az összetett számmal való becsapás valószínűségére. Sok népszerű primalitási teszt valószínűségi teszt. Ezek a tesztek a tesztelt n számon kívül néhány más a számot is használnak, amelyeket véletlenszerűen választanak ki valamely mintatérből ; a szokásos randomizált primalitási tesztek soha nem jelentenek prímszámot összetettként, de lehetséges, hogy egy összetett számot prímként kell jelenteni. A hiba valószínűsége csökkenthető a vizsgálat megismétlésével több egymástól függetlenül választott értékei egy ; A két leggyakrabban használt vizsgálatok, bármilyen összetett n legalább a felét egy „ s kimutatására n ” s összetettség, így k ismétlések csökkentése hiba valószínűsége, hogy legfeljebb 2 - k , amely lehet tetszőlegesen kicsi növelésével k .

A randomizált primalitási tesztek alapstruktúrája a következő:

  1. Válasszon véletlenszerűen egy számot a .
  2. Check egyenlőség (megfelel a választott vizsgálati) bevonásával egy , és a megadott szám n . Ha az egyenlőség nem állja meg a helyét, akkor n összetett szám, a pedig az összetettség tanúja , és a teszt leáll.
  3. Térjen vissza az első lépéshez, amíg el nem éri a szükséges pontosságot.

Ha egy vagy több iteráció után nem találjuk összetett számnak az n -t, akkor valószínűleg prímnek nyilvánítható .

Fermat primitális teszt

A legegyszerűbb valószínűségi primalitási teszt a Fermat -primalitási teszt (valójában összetettségi teszt). A következőképpen működik:

Ha egy n egész számot adunk meg , válasszunk néhány egész számot egy coprime -ból n -be, és számítsunk ki egy n - 1 modulo n -t . Ha az eredmény eltér az 1 -től, akkor n összetett. Ha 1, akkor n lehet prím.

Ha egy n -1 (modulo n ) jelentése 1, de n nem prímszám, akkor n nevezzük pseudoprime a bázis egy . A gyakorlatban megfigyelhetjük, hogy ha egy n −1 (modulo n ) 1, akkor n általában prím. De itt egy ellenpélda: ha n = 341 és a = 2, akkor

annak ellenére, hogy 341 = 11 · 31 összetett. Valójában a 341 a legkisebb pszeudoprime 2 bázis (lásd 1. ábra).

Csak 21853 pszeudoprimes 2. bázis van, amelyek kisebbek, mint 2,5 × 10 10 (lásd: 1005. oldal). Ez azt jelenti, hogy n legfeljebb 2,5 × 10 10 esetén , ha 2 n −1 (modulo n ) 1, akkor n prímszám, kivéve, ha n a 21853 pszeudoprimes egyike.

Egyes összetett számoknak ( Carmichael számok ) az a tulajdonsága, hogy az n - 1 1 (modulo n ) minden olyan a esetén , amely n -nek coprime . A legkisebb példa n = 561 = 3 · 11 · 17, amelyre a 560 1 (modulo 561) minden olyan relatív prím a 561. Mindazonáltal, a Fermat tesztet gyakran használják, ha gyors szűrési számok van szükség, például a az RSA nyilvános kulcsú kriptográfiai algoritmus kulcsgenerálási fázisában .

Miller – Rabin és Solovay – Strassen elsődlegességi teszt

A Miller – Rabin elsődlegességi teszt és a Solovay – Strassen primalitási teszt kifinomultabb változatok, amelyek minden kompozitot észlelnek (ez még egyszer azt jelenti: minden n összetett szám esetén legalább 3/4 (Miller – Rabin) vagy 1/2 (Solovay) -Strassen) számok egy tanúi összetettség az n ). Ezek összetettségi tesztek is.

A Miller – Rabin elsődlegességi próba a következőképpen működik: Ha egy n egész számot adunk , válasszunk pozitív a  <  n egész számot . Legyen 2 s d = n  - 1, ahol d páratlan. Ha

és

mindenkinek

akkor n jelentése kompozit és egy tanú az összetettség. Ellenkező esetben az n lehet prím vagy nem. A Miller – Rabin teszt erős pszeudoprime teszt (lásd PSW 1004. oldal).

A Solovay – Strassen primalitási teszt egy másik egyenlőséget használ: Páratlan n -es szám esetén válasszon a  <  n egész számot , ha

, hol van a Jacobi szimbólum ,

akkor n jelentése kompozit és egy tanú az összetettség. Ellenkező esetben az n lehet prím vagy nem. A Solovay – Strassen teszt Euler pszeudoprime teszt (lásd PSW 1003. oldal).

Minden egyes érték egy , a Solovay-Strassen-teszt gyengébb, mint a Miller-Rabin teszt. Például, ha n = 1905 és a = 2, akkor a Miller-Rabin teszt azt mutatja, hogy n összetett, de a Solovay – Strassen-teszt nem. Ennek oka az, hogy 1905 Euler pszeudoprime 2 bázis, de nem erős pszeudoprime 2 bázis (ezt a PSW 1. ábrája szemlélteti).

Frobenius primalitási teszt

A Miller – Rabin és a Solovay – Strassen elsődlegességi tesztek egyszerűek és sokkal gyorsabbak, mint a többi általános primitív teszt. A hatékonyság további javításának egyik módja bizonyos esetekben a Frobenius pszeudoprimalitási teszt ; ennek a tesztnek a fordulója körülbelül háromszor annyi időt vesz igénybe, mint egy Miller – Rabin forduló, de a hét Miller – Rabin körhöz hasonló valószínűségi kötöttséget ér el.

A Frobenius teszt a Lucas pszeudoprime teszt általánosítása .

Baillie-PSW elsődlegességi teszt

A Baillie – PSW elsődlegességi teszt egy valószínűségi primalitási teszt, amely egy Fermat- vagy Miller -Rabin -tesztet egy Lucas -féle valószínű prímeteszttel kombinál, és így kap egy olyan primalitási tesztet, amelynek nincs ismert ellenpéldája. Vagyis nincs olyan ismert összetett n , amelyre ez a teszt azt jelenti, hogy n valószínűleg prím. Kimutatták, hogy n -re nincs ellenpélda .

Egyéb tesztek

Leonard Adleman és Ming-Deh Huang az elliptikus görbe elsődlegességi tesztjének hibátlan (de várható polinomidős) változatát mutatta be . A többi valószínűségi teszttel ellentétben ez az algoritmus elsődlegességi tanúsítványt állít elő , és így bizonyítható, hogy egy szám prím. Az algoritmus a gyakorlatban rendkívül lassú.

Ha kvantumszámítógépek állnak rendelkezésre, az elsődlegességet aszimptotikusan gyorsabban lehet tesztelni , mint klasszikus számítógépek használatával. Shor algoritmusának , egy egész faktorosítási módszernek a Pocklington -primalitási teszttel való kombinációja megoldhatja a problémát .

Gyors determinisztikus tesztek

A 20. század eleje felé bebizonyosodott, hogy Fermat kis tételének következménye használható az elsődlegesség tesztelésére. Ennek eredményeként létrejött a Pocklington -féle primalitási teszt . Azonban, ahogy ez a vizsgálat szükségessé részleges faktorizációja az n  - 1 a működési idő még elég lassú a legrosszabb esetben. A naiv módszereknél lényegesen gyorsabban végzett első determinisztikus primitális teszt a ciklotómia teszt volt ; annak futásidejű lehet bizonyult O ((log  n ) c  log log log  n ), ahol n az a szám, hogy teszt primality és c jelentése függetlenül állandó n . Sok további fejlesztés történt, de egyik sem bizonyított polinomiális futási idővel. (Vegyük figyelembe, hogy időt mérik a méret a bemeneti, amely ebben az esetben az, ~ log  n , hogy mivel a szükséges bitek száma, hogy képviselje a szám n .) A elliptikus görbe prímteszt bizonyíthatóan futtatni O ((log  n ) 6 ), ha az analitikus számelmélet néhány feltételezése igaz. Hasonlóképpen, az általánosított Riemann -hipotézis alapján bizonyítható , hogy a determinisztikus Miller -teszt , amely a valószínűségi Miller – Rabin -teszt alapját képezi, Õ ((log  n ) 4 ) -ben fut . A gyakorlatban ez az algoritmus lassabb, mint a másik kettő a számméretek esetében, amelyek egyáltalán kezelhetők. Mivel e két módszer megvalósítása meglehetősen nehéz, és programozási hibák kockázatát hordozza magában, gyakran a lassabb, de egyszerűbb teszteket részesítik előnyben.

2002 -ben Manindra Agrawal , Neeraj Kayal és Nitin Saxena találta ki az első bizonyíthatóan feltétel nélküli determinisztikus polinomiális időpróbát . Az AKS elsődlegességi tesztje Õ ((log n ) 12 ) -ben  (javítva Õ -re ((log  n ) 7.5 ) a papírjuk közzétett felülvizsgálatában), amely tovább csökkenthető Õ -re ((log  n ) 6 ), ha Sophie Germain sejtése igaz. Ezt követően a Lenstra és a Pomerance bemutatta a tesztnek azt a változatát, amely időben fut (Õ (log  n ) 6 ) feltétel nélkül.

Agrawal, Kayal és Saxena javaslatot tesz algoritmusuk egy változatára, amely akkor futna Õ ((log  n ) 3 ) -ban, ha Agrawal sejtése igaz; azonban Hendrik Lenstra és Carl Pomerance heurisztikus érvelése azt sugallja, hogy valószínűleg hamis. Az Agrawal sejtésének módosított változata, az Agrawal – Popovych sejtés még mindig igaz lehet.

Bonyolultság

A számítási komplexitás elméletében a prímszámoknak megfelelő formális nyelvet PRIMES jelöli. Könnyű kimutatni, hogy a PRIMES a Co-NP-ben van : a COMPOSITES kiegészítője NP-ben van, mert az összetettséget úgy lehet eldönteni, ha nem determinisztikusan kitalálunk egy tényezőt.

1975 -ben Vaughan Pratt kimutatta, hogy létezik az elsődlegességre vonatkozó tanúsítvány, amely polinomiális időben ellenőrizhető, és így a PRIMES NP -ben , tehát NP ∩ coNP -ben van . A részleteket lásd az elsődlegességi tanúsítványban .

A Solovay – Strassen és Miller – Rabin algoritmusok későbbi felfedezése a PRIMES -t a coRP -be helyezte . 1992 -ben az Adleman – Huang algoritmus ZPP = RP  ∩  coRP -re redukálta a komplexitást , ami felváltotta Pratt eredményét.

Az Adleman – Pomerance – Rumely primalitási teszt 1983-ból a PRIMES-t QP-ben ( kvázi polinomiális idő ) helyezte el , ami nem ismert, hogy összehasonlítható lenne a fent említett osztályokkal.

A gyakorlatban való kezelhetősége, a Riemann-hipotézist feltételező polinomiális idejű algoritmusok és más hasonló bizonyítékok miatt sokáig gyanították, de nem bizonyították, hogy a primitivitás polinomidőben megoldható. Az AKS elsődlegességi teszt végül megoldotta ezt a régóta fennálló kérdést, és a PRIMES-t P-be helyezte . Azonban, PRIMES nem ismert, hogy a P-teljes , és ez nem ismert, hogy abban rejlik osztályok fekvő belül P , mint NC vagy L . Ismeretes, hogy a PRIMES nincs AC 0 -ban .

Számelméleti módszerek

Bizonyos számelméleti módszerek léteznek a szám prímszámának tesztelésére, például a Lucas-teszt és a Proth-teszt . Ezek a tesztek általában n  + 1, n- 1 vagy hasonló mennyiségű faktorizációt igényelnek , ami azt jelenti, hogy nem hasznosak az általános célú elsődlegességi teszteléshez, de gyakran elég erősek, ha a tesztelt n számról ismert, hogy speciális forma.

A Lucas teszt azon a tényen alapul, hogy a multiplikatív érdekében számos olyan modulo n jelentése n - 1 elsődleges n , amikor egy olyan primitív gyök . Ha meg tudjuk mutatni, hogy a primitív n -re , akkor megmutathatjuk, hogy n prím.

Hivatkozások

Források

Külső linkek