強RSA仮定

次の問題を flexible RSA 問題（フレキシブル アールエスエイもんだい, flexible RSA problem）という：

n をRSAモジュラスとし、a を ${\displaystyle Z_{n}^{*}}$ の元とする。 組 ${\displaystyle (b,e)\in Z_{n}^{*}\times Z}$ で、${\displaystyle a=b^{e}{\pmod {n}}}$ となるものを求めよ。

文献によっては flexible RSA 問題の事を強 RSA 問題（きょうアールエスエイもんだい, strong RSA problem）と呼んでいるものもある（注：この問題は RSA 問題よりも簡単な（難しくない）ので強 RSA 問題と呼ぶのはおかしい）。

「flexible RSA 問題は難しい」という仮定を強RSA仮定（きょうアールエスエイかてい, strong RSA assumption）という。より正確には、以下の通り。

素数生成機 ${\displaystyle G}$ で次を満たすものが存在する： 任意の多項式時間アルゴリズム A に対し、

${\displaystyle \mathrm {Pr} (p\gets G(1^{k}),q\gets G(1^{k}),n\gets pq,a\gets _{R}Z_{n}^{*},(b,e)\gets A(n):{a=b^{e}{\bmod {n}}\wedge e\neq 1})}$

はnegligible。

• RSA暗号
• RSAモジュラス
• RSA仮定
• 暗号理論