Zdenek Marsik (zmarsik@iol.cz)
Tue, 13 Jul 1999 12:43:39 +0200
Zdravim,
predevsim chci podekovat za ten algoritmus. Bohuzel se mi zda, ze je tam
maly preklep (nebo jsem to spatne pochopil). V bode 2 (Horni i spodni bit se
nastavi na 1)
Pokud si zvolim napr. cislo 19, nastavim bit s nejvetsi vahou a bit s
nejmensi vahou na 1, dostanu cislo 147. To neni prvocislo (3*7*7) . Aby to
bylo zrejmejsi jak si to ja predstavuji, prikladam prilohu.
Zdenek Marsik
-----P∙vodnφ zprßva-----
Od: Josef Pojsl <josef.pojsl@skynet.cz>
Komu: zmarsik@iol.cz <zmarsik@iol.cz>
Kopie: pgp-uzivatele@pgp.cz <pgp-uzivatele@pgp.cz>
Datum: 7. Φervence 1999 14:31
P°edm∞t: Re: velka prvocisla
>> 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 Tue Jul 13 1999 - 12:47:26 CEST
