強RSA仮定
出典: フリー百科事典『ウィキペディア（Wikipedia）』
強RSA仮定（きょうRSAかてい）とは、暗号技術において、RSA暗号やRSA類似の暗号方式の安全性研究に使用される仮定の一つである。
flexible RSA問題
次の問題を flexible RSA 問題（フレキシブル アールエスエイもんだい, flexible RSA problem）という：
n をRSAモジュラスとし、a を <math>Z_n^*</math> の元とする。 組 <math>(b,e)\in Z^*_n\times Z</math> で、<math>a=b^e \pmod n</math> となるものを求めよ。
文献によっては flexible RSA 問題の事を強 RSA 問題（きょうアールエスエイもんだい, strong RSA problem）と呼んでいるものもある。（注：この問題は RSA 問題よりも簡単な（難しくない）ので強 RSA 問題と呼ぶのはおかしい）。
強RSA仮定
「flexible RSA 問題は難しい」という仮定を強RSA仮定（きょうアールエスエイかてい, strong RSA assumption）という。より正確には、以下の通り。
素数生成機 <math>G</math> で次を満たすものが存在する： 任意の多項式時間アルゴリズム A に対し、
- <math>\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})</math>
