特徴的な素数である2027
まず,2027は素数です。そして,素数の中でも以下のような特徴的な性質を持っています。
- 2027は素数の数列における307番目の素数であり,この“307”も素数です。このような素数番目の素数をスーパー素数(超素数)といいます。
- 2027とともに2029も素数です。このような差が2である素数の組を双子素数といいます。
- \(2\cdot 1013+1=2027\) であり,1013も素数です。このように \(r\) と \(2r+1\) がともに素数であるとき,後者を安全素数(Safe Prime)といいます。
安全素数は,例えばRSA暗号(巨大素数 \(p, q\) の合成数は素因数分解が困難であることを利用した暗号)などの通信の暗号技術において,特定の素因数分解アルゴリズムに対して強い=素因数分解されにくい安全な合成数をつくる際に利用されます。
素因数分解のアルゴリズム
安全素数がなぜ安全なのかについて,暗号解析に用いられる「ポラードの \(p-1\) 法」と呼ばれる素因数分解アルゴリズムを例に,具体的に考えてみます。
このアルゴリズムは,素因数分解したい合成数 \(N\) の素因数 \(p\) に対し,\(p-1\) が小さな素数の積で表されるときに効果を発揮します。つまり,単に素因数 \(p\) が大きければ安全というわけではありません。
アルゴリズムのなかでフェルマーの小定理を利用するので,確認しておきましょう。
すなわち,\(a^{p-1}-1\) は \(p\) の倍数です。よって,素因数 \(p\) は \(a^{p-1}-1\) と \(N\) との公約数です。
ここからは,具体数で考えてみましょう。\(N=1261\) とします。
【Step1】
まず,\(p-1\) が小さな素数の積で表されると仮定し,\(p-1\) の倍数になりそうな数 \(M\) をつくります。
ここでは,4の階乗を \(M\) としてみましょう。すなわち \(M=4!=24=2^3\cdot3\)
【Step2】
適当な底として \(a=2\)( \(p\) と互いに素)とします。
仮に \(M=24\) が \(p-1\) の倍数であれば,\(2^{24}\) は \(2^{p-1}\) の整数乗なので,フェルマーの小定理により
\(2^{24}=(2^{p-1})^k\equiv1^k\equiv1\pmod p\)
となり,\(2^{24}-1\) も \(p\) の倍数となるはずです。( \(k\) は整数)
そこで,\(2^{24}-1\) と \(N\) の公約数を探してみましょう。\(2^{24}\) を1261で割った余りを考えます。
\(2^{12}=4096\) より \(4096=1261\cdot 3+313\)
よって \(2^{12}\equiv313\pmod{1261}\)
\((2^{12})^2\equiv313^2=97969\equiv872\pmod{1261}\)
したがって \(2^{24}\equiv872\pmod{1261}\) …①
【Step3】
①より \(2^{24}-1\equiv871\pmod{1261}\)
互除法の原理により,\(2^{24}-1\) と \(N\) の最大公約数は871と1261の最大公約数と一致するので,これを求めます。ユークリッドの互除法を用いて
\(1261=871\cdot1+390\)
\(871=390\cdot2+91\)
\(390=91\cdot4+26\)
\(91=26\cdot3+13\)
\(26=13\cdot2\)
最大公約数は13より,1261は13を素因数に持ちます。
すなわち \(1261=13\cdot97\)
もし \(p\) が見つけられないときは,順次 \(M\) を大きくして再度アルゴリズムを走らせます。
安全素数はなぜ安全なのか?
安全素数を \(p\) とすると,\(p=2r+1\) より \(p-1=2r\)
上の方法で安全素数 \(p\) を因数に持つ合成数 \(N\) から \(p\) を見つけるには,\(M\) が \(r\) を因数に持つよう設定したいのですが,実際に用いられる \(p\) は数百桁の巨大素数ですから,\(r\) も巨大素数です。
結果,\(r\) を因数に持つ \(M\) にたどり着く前に計算量が限界となり,素因数分解に失敗します。このような性質が,安全素数の安全たる所以です。
通信の暗号技術における素数の利用について,安全素数を通して具体的な仕組みを垣間見ることができます。(様々な解析手法に対して暗号の作成方法も様々あり,安全素数はその手法のひとつです。)
合同式の性質の知識が必要ですが,年越しの話題として,関心のある生徒にご紹介してみるのはいかがでしょうか。
その他のコンテンツ