Posted By: Xofon (Xof) on 'Czech'
Title:     Re: algoritmus na generovani prvocisel
Date:      Thu Oct 24 16:52:09 2002


    Ahoj

> V nejakem casaku jsem se docetl, ze tri indicti matematici objevili
> algoritmus 
> na generovani prvocisel ... Odkaz za clankem byl na New Scientist, ale u
> nich 
> na webu jsem k tomu nic nenasel. Byla tam zminka i o tom, ze bude zajimave,
> co 
> to udela s sifrovacim "prumyslem". Nikde o tom ani zminka, takze to zatim 
> povazuju za lez/dezinformaci; nebo jste o tom nekdo neco slysel ?

    Ti novinari toho nakecaji. Tri indicti matematici (Agrawal, Kayal, 
Saxena) objevili deterministicky polynomialni algoritmus, ktery zjisti, 
_jestli_ zadane cislo je prvocislo (pritom algoritmus je polynomialni 
vzhledem k poctu cislic, tj. je logaritmicky vzhledem k hodnote toho 
cisla).

    Vzhledem k tomu, ze drive byly znamy randomizovane polynomialni
algoritmy, ktere to same zjisti s libovolne malou danou pravdepodobnosti
chyby, mam za to, ze na sifrovaci prumysl to zadny valny vliv mit nebude
(pokud nevymysli algoritmus, jak dane slozene cislo _rozlozit_ na soucin
prvocisel).

    Clanek je na http://www.cse.iitk.ac.in/news/primality.html (ke stazeni
v pdf a postskriptu) a je to normalni matematicky clanek - takze pomerne
hutne cteni. Ale ten algoritmus tam je napsany.

> BigFoot

    Xof
:wq