RSA 公開鍵暗号の安全性は主にどの数学的困難性に依存しているか

RSA の安全性は大きな整数を素因数分解することの困難性に依存します。公開鍵は一般に二つの大きな素数の積 n=pq を含み、秘密鍵はこれらの素因数を知ることで導出されます。十分大きな素数を用いると素因数分解は計算困難とされており、これが RSA の根拠です。量子計算が実用化されると Shor のアルゴリズムにより脅かされる点も重要です。