Vlákno názorů k článku Kryptografické anekdoty aneb politika je všude od s - RSA je zalozena na matematickem problemu faktorizace o...

RSA je zalozena na matematickem problemu faktorizace o kterem se pouze mysli, ze je tezke ho vyresit. Dukaz nikdy nikdo nepodal. IMO sifra 128bit AES je mnohem bezpecnejsi nez 2048bit RSA i presto, ze je RSA zalozena na tezkem matematickem problemu, kdezto o AES zadny dukaz neexistuje.

Obecný problém faktorizace je těžké vyřešit. Co občas někdo zmíní, je fakt, že některé speciální úlohy faktorizace nemusí být těžké (a některé skutečně nejsou).

Jedna z těch speciálních úloh je "faktorizace součinu dvou prvočísel". A tady je zdroj občasných rozruchů - ačkoliv u obecné faktorizace (rozklad součinu N prvočísel na jednotlivé činitele) o složitosti nejsou žádné reálné pochyby, tak o součinu 2 prvočísel důkaz složitosti opravdu chybí. Laicky řečeno, když v něčem figuruje N, tak si člověk složitost N^N umí představit. Ale když je tam dvojka, tak to budí otázky. Je složitost pak 2^N nebo spíše N^2? Neexistuje iterační algoritmus, který by dokázal ta dvě čísla v cyklech upřesňovat, místo aby se zkoušely všechny kombinace? Neexistuje nějaký vylučovací algoritmus? Zkrátka, vy v důsledku hledáte číslo jediné, to druhé už pak snadno dopočtete. Nesnižuje to náhodou složitost té úlohy?

existuje poly. algoritmus na overeni prvociselnosti, nevi se vsak, jestli existuje poly. alg. pro faktorizaci. Da se to vsak predpokladat. Mame totiz dukaz overitelny v poly case prvociselnosti i neprvociselnosti. Faktorizace tak nemuze byt NP uplna, protoze by se NP=coNP, coz je nepravdepodobne. (mame-li instanci SAT problemu, muze se existence reseni dokazat snadno jeho predlozenim, u neexistence to nejde. faktorizace lze overit polynomialne rychle v obou pripadech)

Tedy, IMO neni vubec jiste, ze je faktorizace tak slozity problem.

Jedna z vlastností nejde ověřit s polynomiální složitostí. Teď nevím jestli to je "A je prvočíslo" nebo "A není prvočíslo", ale jedna z nich nejde. Existuje však algoritmus, který s každou iterací zpřesňuje odhad. Spolehlivosti 100 procent však nedosáhne.

nene, to uz davno neplati - http://en.wikipedia.org/wiki/AKS_primality_test

Složitost triviálního algoritmu faktorizace je sqrt(N) nebo-li musí se zkoušet dělitelnost čísly od 2 do druhé odmocniny z N.
Při součinu dvou prvočísel je v extrémním případě jedno z čísel rovno 2 a tedy nejvyšší složitost je sqrt(N/2).
Zdá se tedy že složitost faktorizace součinu dvou čísel je o něco menší.

U faktorizace se spíše dává N = počtu číslic nebo bitů. Nejvyšší zapsatelné číslo je pak 10^N - 1, respektive 2^N - 1. Což už ani ta odmocnina moc neučeše (respektive vydělí N dvěma).

Jak moc se jedná o kosmetickou věc bude zřejmé, když si pokusíte napsat "vaše N" pro 2048 bitový RSA klíč.

S tím souhlasím, v praxi se to vůbec neprojeví.