特集記事(高校)

高校

2026.11.19

【来年】2027は安全素数?【暗号理論】

 年末が近づいてくると,つい西暦が気になってしまいます。来年は2027年ですが,”2027”とはどんな数でしょうか?

特徴的な素数である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\) が大きければ安全というわけではありません。

 アルゴリズムのなかでフェルマーの小定理を利用するので,確認しておきましょう。

\(p\) を素数,\(a\) を \(p\) と互いに素な整数とするとき,次が成り立つ。
\(a^{p-1}\equiv1\pmod 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\) にたどり着く前に計算量が限界となり,素因数分解に失敗します。このような性質が,安全素数の安全たる所以です。

 通信の暗号技術における素数の利用について,安全素数を通して具体的な仕組みを垣間見ることができます。(様々な解析手法に対して暗号の作成方法も様々あり,安全素数はその手法のひとつです。)
 合同式の性質の知識が必要ですが,年越しの話題として,関心のある生徒にご紹介してみるのはいかがでしょうか。

その他のコンテンツ