Deterministic Polynomial-Time Equivalence of Computing the RSA Secret Key and Factoring

.@hyuki 暗号技術入門3版p142の「Dを求めること」と「Nの素因数分解を求めること」が確率的多項式時間帰着で等価なことは、昔から知られています。また、決定性多項式時間帰着で等価なこともMayが2004年に示しています。参考:https://t.co/lhj8Z4pdvT