RSA暗号
となるが、 a , a ′ ∈ Z n {\displaystyle a,a'\in \mathbb {Z} _{n}} であるから
a ′ = a {\displaystyle a'=a}
となる。
gcd ( n , a ) = p {\displaystyle \gcd(n,a)=p} であり、 a ∈ Z n − { 0 } {\displaystyle a\in \mathbb {Z} _{n}-\{0\}} のときは、a は q − 1 個の整数からなる集合 { 1 ⋅ p , 2 ⋅ p , 3 ⋅ p , ⋯ , ( q − 1 ) ⋅ p } {\displaystyle \{1\cdot p,2\cdot p,3\cdot p,\cdots ,(q-1)\cdot p\}} の元であって、a が p で割り切れるから a ≡ 0 ( mod p ) {\displaystyle a\equiv 0{\pmod {p}}} であり、a, q が素であるからフェルマーの小定理により a q − 1 ≡ 1 ( mod q ) {\displaystyle a^{q-1}\equiv 1{\pmod {q}}} であり
a λ ( n ) = ( a q − 1 ) p − 1 ≡ 1 ( p − 1 ) ( mod q ) = 1 {\displaystyle a^{\lambda (n)}=(a^{q-1})^{p-1}\equiv 1^{(p-1)}{\pmod {q}}=1}
鍵生成、暗号化、復号の3つのアルゴリズムで定義される。
桁数が大きい場合、確実に素数であると保証できる整数を見つけることは容易ではない。このため実際には、素数であるとは断言できないものの、素数である可能性が非常に高い自然数を用いる。こういった自然数の生成はMiller–Rabinテストなどの確率的素数判定法によって高速に行える。確率的素数判定法をパスした自然数を確率的素数 (probable prime) という。確率的素数には、素数の他に擬素数が含まれるが、その確率は判定回数を増やすことで極めて低くすることができる(なお、拡張リーマン予想が正しければ、Miller–Rabinテストは素数かどうかを正しく判定する、という事実が知られている)。
2002年8月、インド工科大学 のアグラワルらが素数判定を多項式時間で行うAKS素数判定法を発表したが、これは多項式の次数が高すぎて遅いので未だRSAの鍵生成に実用するには足らない。
1977年、マーティン・ガードナーがコラムを連載していたサイエンティフィック・アメリカン誌に129桁の法 n と公開指数 e = 9007 を使ったRSA方式で暗号化されたメッセージを掲載した。解読が成功した者にマサチューセッツ工科大学から100米ドルを与えるという懸賞金問題だった。当時、解読には4京年(40×10年)は必要だろうと予測されていた。掲載から16年後に、オックスフォード大学ポール・レイランド(英語版)、アイオワ州立大学マイケル・グラフ、マサチューセッツ工科大学デレク・アトキンス、アリエン・レンストラ(英語版)らが、インターネット上で(南極大陸を除くすべての大陸から20か国以上の)約600名のボランティアの協力を得て、二次ふるい法によってRSA-129に対する大規模攻撃を開始した。8か月で800万以上の下位問題が解かれ、得られた50万行50万列以上の疎行列から188614行188160列の行列による連立方程式を作った。これをスーパーコンピュータMP-1で45時間をかけて構造的ガウスの消去法によって解き、解読に成功した(1994年4月)。答えは“The magic words are squeamish ossifrage”[ossifrage(ヒゲワシ)はラテン語で「骨を折る者」の意。ロナルド・リベストによると暗号の答えはランダムで決められた。]
歴史的見解を正すのであれば、暗号に革命を起こしたこの理論の最初の発案者はジェイムズ・エリス(英語版)である。彼らはイギリス最高機密機関・英国政府通信本部 (GCHQ) の職員であり、その独創的な先見の明は内部文書として長い間公開されなかった。また実用にはコンピュータの性能等から機が熟していなかった。以下はその概要である。
エリスは1969年にこの理論を発見しているが、専門の数学者ではなかったため、具体的な方法を発見できなかった。幾人ものGCHQの優秀な数学者が挑戦したが、具体的な方法を提示することはできなかった。1973年、突拍子もない暗号のアイデアとしてエリスの「一方向関数(非対称性鍵の概念)・公開鍵」を用いた暗号論の話を聞かされ、わずか30分程度でモジュラー算術と素因数を用いた具体的な方法を考案したのは、GCHQ所属の若き数学者クリフォード・コックス(英語版)である(コックスは上記のリベストの計算式と同じものを発見した)。しかしエリスとコックスの業績は機密事項とされたため、1997年までは世に知られることはなかった。