Názor k článku Kryptografické anekdoty aneb politika je všude od s - existuje poly. algoritmus na overeni prvociselnosti, nevi se...

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.