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