Josef Pojsl (josef.pojsl@skynet.cz)
Wed, 7 Jul 1999 14:29:56 +0200 (CEST)
> Zdravim,
>
> Neznate nekdo algoritmus na vypocet velmi velkych prvocisel? Jde mi o neco podobneho jako PGP voli prvocisla:
> 1. Generovani nahodneho cisla, nejvyssi dva bity maji nastaveno 1
> 2. Spusteni FASTTESTu
> 3. Dalsi provereni pomoci Fernatova maleho teoremu (SLOWTEST)
> .... atd.
Konecne jsem se k tomu dostal. Cerpam z Applied Cryptography
od Bruce Schneiera, strany 258-261. Jsou tam 3 algoritmy, nejpouzivanejsi je
zrejme Rabin-Miller:
Testuje, zda p je prvocislo. Spocita se b, coz je maximalni cislo takove,
ze 2^b deli p-1. Pak se spocita m takove, ze p-1=m*2^b.
(1) Vybere se nahodne cislo a mensi nez p.
(2) Nastavi se j=0 a z=a^m mod p.
(3) Pokud z==1 nebo z==p-1, p proslo testem a "muze byt prvocislo".
(4) Pokud j>0 a z==1, pak p neni prvocislo.
(5) Nastavi se j=j+1. Pokud j<b a z!=p-1, nastavi se z=z^2 mod p a vrati
se ke kroku (4). Pokud z==p-1, p proslo testem a "muze byt prvocislo".
(6) Pokud j==b a z!=p-1, pak p neni prvocislo.
Vyraz "p muze byt prvocislo" prakticky znamena, ze p je prvocislo
s pravdepodobnosti zhruba 99.9%.
Cely algoritmus:
(1) Vygeneruje se nahodne cislo p.
(2) Horni i spodni bit se nastavi na 1.
(3) Test, zda p je delitelne nekterymi malymi prvocisly (3,5,7,11 atd.)
(4) Provede se Rabin-Milleruv test s nahodnym a. Pokud p projde,
vybere se nove a a test se opakuje. Obvykle se pouziva pet po sobe
jdoucich testu. Pokud p projde vsemi testy, povazuje se za prvocislo.
Cisla a mohou byt pomerne nizka.
S pozdravem,
Josef Pojsl mailto:josef.pojsl@pgp.cz
SkyNet, a.s. http://www.pgp.cz
PGP fingerprint: 23CB DE28 51A9 53F1 0C1F 67EF B3ED 8435 9D1B C7C8
This archive was generated by hypermail 2.0b3 on Wed Jul 07 1999 - 14:30:19 CEST