RSAと離散対数問題

RSA 暗号の安全性の根拠についての疑問
google:離散対数問題 素因数分解 帰着で日本語の資料を発見。
素因数分解問題調査研究報告書 2001/12 (pdf)@NICTの3-2辺りを読むと宜しいかと。
「N=pqの素因数分解」から「Z_N^*上の離散対数問題」に平均的多項式時間でTuring帰着できるという話。
L. M. Adleman, "Algorithmic number theory The complexity contribution", Proc. 35th FOCS, pp.88--113, 1994.に網羅的に載っているとか。