A számelmélet , az algoritmus p - 1 Pollard egy algoritmus számára prímfelbontás által tervezett John Pollard az 1974 . Ez egy specifikus algoritmus (szemben a generalistával), mert csak olyan egész számokkal működik, amelyek tényezőinek meghatározott formája van; ez a legegyszerűbb példa a moduláris aritmetikai faktorizációs algoritmusra .
Azokat a tényezőket találja meg, amelyek precedense, p - 1, rendkívül sima (vagy rendkívül megbízható ).
Legyen n egész szám, amely osztható p prímszámmal , n ≠ p-vel . Szerint a kis Fermat-tétel , van
A egy prím p . Itt (mod) az egész számokkal való egybevágást jelöljük .Ez azt jelenti, hogy a p - 1 bármely többszörös M esetén megvan mert .
Ha p - 1 B szuperlisse egy B küszöbre , akkor p - 1 elosztja az egész szám legkevésbé gyakori többszörösét 1-től B-ig . Tehát, ha M = ppcm (1,…, B ) értéket adunk meg, akkor megvan
mindenre egy prima p-vel .Más szóval, p osztója egy M - 1, és ezért a GCD az N és egy M - 1 nagyobb, vagy egyenlő, mint p . Másrészt lehetséges, hogy ez a gcd egyenlő önmagával n , ebben az esetben nem kapunk nem triviális tényezőt.
Legyen n = pqr , ahol p és q elkülönülõ prímszámok, és r egész szám, úgy, hogy p - 1 jelentése B- szuperliss és q - 1 nem B- szupervonal. Ezután a GCD ( egy M - 1, n ) nyújt Eigenfaktoré a n .
Megjegyezzük, hogy abban az esetben, ha q - 1 B- szuperlissze, a gcd triviális tényezőt produkálhat, mert q elosztja az M - 1-et.
Észrevehetjük, hogy ez a tulajdonság teszi egyedivé az algoritmust. Például 172189 = 421 × 409. Vagy 421 - 1 = 2 2 × 3 × 5 × 7 és 409 - 1 = 2 3 × 3 × 17. Így a B megfelelő értéke 7 és 16 között lenne. Ha B-t kevesebb mint 7 értékre választottuk volna, akkor a gcd értéke 1 lett volna, és ha B- t választottuk nagyobbnak, mint 16, akkor a pgcd értéke n lett volna . Természetesen nem lehet előre tudni, hogy a B melyik értéke lesz megfelelő, ezért ez egy olyan tényező, amelyet figyelembe kell venni az algoritmusban.
Ahhoz, hogy gyorsítsák fel a számítások azt is tudjuk, hogy ez lehetséges, kiszámítani a gcd, hogy csökkentsék a M - 1 modulo n : pgcd ( egy M - 1, n ) = pgcd ( egy M - 1 mod n , n ). Hatékonyan kiszámítható moduláris hatványozással és Euclid algoritmusával .
Az alapvető algoritmus a következőképpen írható fel:
Bejegyzések : n : összetett egész szám Kilépés : n nem triviális tényező n vagy hibaHa a 6. lépésben g = 1-t kapunk , az azt jelenti, hogy az összes p - 1 között nem volt B- szuperlisse. Ha a 7. lépésben g = n- t kapunk , akkor ez általában azt jelzi, hogy az összes tényező B- szuperlin volt, de ritka esetekben azt jelezheti, hogy az a- nak kicsi a modulo p sorrendje .
Néha az alapalgoritmus variációját használják. Statisztikailag, gyakran van faktor p az n olyan, hogy p - 1 = fq , ahol f jelentése a B -superlisse és B < q ≤ B 'ahol q egy prím szám, és B ' nevezik félig sima kötött.
Ez a variáns az alapalgoritmus 6. lépésétől alkalmazható, ha azt találjuk, hogy gcd = 1, de ez nem kívánatos a B növelésére . Az összes B < q 1 ,…, q L ≤ B ' prímszám esetében ellenőrizzük, hogy
hogy megkapjuk az n nem triviális tényezőt . Ez gyorsan megvalósul, mert ha van c = a M , d 1 = q 1 és d i = q i - q i - 1 , akkor kiszámíthatjuk
Az algoritmus végrehajtási ideje ezzel a változattal O -vá válik ( B '× log B ' × log 2 n ).
Ennek az algoritmusnak a hatékonysága az egész számot alkotó prímszámok formájához kapcsolódik, pontosabban a p prímtényező létezéséhez , hogy p - 1 B- szuperlisse. Következésképpen a faktorizálás nehézségén alapuló nyilvános kulcsú titkosítási rendszerek , például az RSA , olyan prímszámok használatát követelik meg, amelyek nem rendelkeznek ezzel a tulajdonsággal egy túl kicsi B küszöbhöz .