Názory k článku Prvočísla ano, faktorizace ne

To mi hlava nebere.

Zajímavé, jenom bych poopravil či spíše doplnil pár věcí.

Jestli se nepletu, výsledek je z loňského léta.

Problém z třídy NP může být i velmi jednoduchý, protože NP je nadmnožinou třídy P, tedy polynomiálně rozhodnutelných problémů. Autor článku pravděpodobně myslí spíše NP-úplný problém, který je určitým způsobem nejsložitější pro danou třídu problémů.
Problém rozhodnutí prvočíselnosti ale nebyl považován za NP-úplný, naopak byl kandidátem na problém, který není v P, ale zároveň není NP-úplný.
Ještě bych podotknul, že problém NP=P je stále otevřený a tedy může (i když je to velmi nepravděpodobné) platit i to, že i NP-úplné problémy jsou řešitelné v polynomiálním čase. Ale i v případě nerovnosti ještě může platit, že NP-úplné problémy jsou řešitelné v čase lepším než exponenciálním (avšak horším, než polynomiálním).

A ještě něco. Známé pravděpodobnostní algoritmy pro testování prvočíselnosti jsou (zatím) rychlejší, než je ten nový polynomiální. A protože při jednom běhu dává pravděpodobnost chyby 1/2, jeho opakováním k-krát lze chybu srazit až na 1/2 na k, což třeba pro k=100 je mnohem méně, než pravděpodobnost chyby hardware, na kterém výpočet běží.
Takže pro praxi tento výsledek neznamená příliš velkou revoluci, jeho důležitost je hlavně teoretická.

máte úplnou pravdu
NP jsem myslel NP-úplné
těmi pravděpodobnostními postupy myslíte třeba ARCLP apod.?

mimochodem, je nějak přesněji specifikovaná ta oblast co "není už polynomiální, ale ještě není ani exponenciální"?

Polynomiální znamená omezený polynomem. Tedy existuje k takové, že od určitého n platí f(n)<n^k. Existují funkce, které rostou rychleji, než polynom, ale přitom pomaleji, než exponenciála. Třeba takové n^logn určitě nelze omezit pomocí polynomu (logn přeleze libovolně velkou konstantu), ale přitom je to jistě menší, než 2^n (protože n^logn = 2^((logn)^2)) a logn^2 roste jistě pomaleji, než n.
Nicméně, problémy, které mají složitost mezi polynomem a exponenciálou, nejsou přiliš obvyklé, z hlavy si na žádný přirozený nevzpomenu (diagonalizační technikou lze takový problém snadno vyrobit, ale bude uměle vytvořený bez nějakého zřejmého promítnutí do "skutečného světa").

K těm pravděpodobnostním algoritmům. Nevím, co je to ARCLP, ale třeba algoritmus založený na Fermatově větě má při odpovědi "složené číslo" spolehlivost 100%. Při odpovědi "prvočíslo" se s pstí 50% plete. Takže když budu tento algoritmus opakovat stokrát a budu stále dostávat odpovědi "prvočíslo", na konci budu mít pravděpodobnost 1/2^100, že se jedná o prvočíslo a pst 1-1/2^100, že jsem udělal chybu a je to číslo složené.
Algoritmus pracuje v čase O((logN)^3), kde N je vstupní číslo, tedy v čase kubickém vzhledem k velikosti vstupu.

Existuje cislo 2 takove, ze od urciteho n0 plati n*log(n)

Jestli to nebude tím, že já jsem mluvil o funkci n^logn, slovy "en na log en", ne "en krát log en". :-)

Co je to velikost polynomu 10 exp 12?

Je to nějaká notace, kterou neznám, nebo autor akorát neumí psát <sup>?

A co to je vůbec velikost polynomu? Řád to asi není -- kdyby byl 1e12 (slovy deset na dvanáctou), tak bychom si nijak nepomohli -- a nic jiného mne nenapadá.

to to jsou prvnocisla ? to je neco na linuxu ???? Heee ??? nejakej program pro prikazovou radku

Myslí autor svým zápisem, že u nejvyšší mocniny je 12 nebo 10 na dvanáctou (tj. bilión, to bychom si moc nepomohli)?

Zdravím Yetiho

"velikost" polynomu jsem myslel jako nejvyssi hodnotu exponentu. Je-li ta nejvyssi hodnota 12, da se z toho odvodit, v jakych hodnotach uz polynom poroste vyrazne pomaleji nez exponenciala.

Z toho odvozuji, ze v clanku melo byt "polynom stupne 12", a ne velikost 10 exp 12 (coz bych chapal jako 10^12). Polynom stupne 10^12 by nam opravdu mnoho nepomohl :-)))

Hezky clanek. Jen drobna pripominka: z textu by mohlo plynout, ze NP znamena nepolynomialni. Znamena to ovsem nedeterministicky polynomialni, tj. pocitac "s vestirnou" dokaze nedeterministickym zpusobem vymyslet reseni problemu a pak v polynomialnim case (deterministicky) rozhodnout o jeho spravnosti. Bez tohoto upresneni by se komentare na tema otazky NP=P mohly zdat ponekud zmatene.

Nesporne zajimavy prispevek soucasne ukazuje, jak komplikovany a slozity aparat se v soucasne kryptologii pouziva. Problemy faktorizace, P=NP, kvantove pocitace , šifrování, presne definice... To jsou opravdu slozita temata a vsude zde se ve snaze o zjednoduseni a priblizeni vykladu beznemu ctenari muze udelat chyba. Smutne je, že takovou chybu pak casto prepisuji dalsi a dalsi nasledovnici. V nasi "literatuře" je již klasickou chybou nazor, ze prvocisla tvori sifrovací klíče.

Cituji z článku:
Šifrovací klíče se generují násobením dvojice prvočísel (činitelé jsou tajným klíčem, součin klíčem veřejným).

Bohužel autor nehraje s pojmy (v duchu uvodu) zcela přesně. Pokud popisuje situaci klíčů pro RSA (což plyne z toho, že se zabývá faktorizací),
pak se sice vychází z prvočísel p a q a jejich součinu N=p*q. Není však pravdou, že by p a q byly "tajné klíče" (ovšm je pravda, že se tají) a součin byl veřejným klíčem (je však pravdou, že N se zveřejňuje).
Klíče pro RSA nejsou přímo příslušná prvočísla. Tato chyba jak jsem již psal, se velice často opakuje.

Dovolím si proto zopakovat správný postup při odvození soukromého a veřejného klíče.

Postup při vytváření dvojice veřejný a soukromý klíč pro RSA je následující:
a)Nejprve náhodně (a nepredikovatelně) vygenerujeme dvě dostatečně velká prvočísla

b) Vypočteme
N = p*q a
F(N) = (p-1)*(q-1)

c) Zvolíme náhodné číslo e, kde
1

Myslim, ze v clanku chybala linka:
http://www.cse.iitk.ac.in/primality.pdf
(Evidentne su tu nejaky nadsenci, pre ktorych to moze byt zaujimave ...)

Prikladam jeste jedno URL: http://www.mersenne.org/prime.htm , neni sice primo o prvocislech, ale o specifickych prvocislech, nicmene informace zde zminene jsou znamy odhadem 6 mesicu (aspon od zhruba rijna jsou na uvedem Webu i s komentarem)