アルゴリズム論特論（塩田）　2020年度教材 第9回

  • 出席代わりに、塩田 ( shiota＠is.kochi-u.ac.jp ) 宛てにメールを出してください。
  • 件名は「アルゴリズム論特論第９回出席」としてください。 $\newcommand{\ol}[1]{\overline{#1}}$ $\newcommand{\znz}[1]{\mathbb{Z}/#1 \mathbb{Z}}$ $\newcommand{\znzc}[1]{(\mathbb{Z}/#1 \mathbb{Z})^{\times}}$ $\newcommand{\inv}[1]{\displaystyle{\frac{1}{#1}}}$

今日のテーマ

  • 素数判定
  • 素数生成
　RSA暗号では1000ビット強の大きな素数を必要としますが、 試し割り算で素数判定できる範囲を遥かに、遥かに超えています。 どうやって素数を作っているのでしょうか、というお話です。

1. フェルマ・テスト

　まずは復習から。
Th.1（フェルマの小定理）　$p$ が素数、$b$ が $p$ で割り切れない整数ならば
$b^{\,p-1} \equiv 1 \pmod{p}$
　この対偶を取ると
Cor.2（合成数判定）　$n$ で割り切れない整数 $b$ が
$b^{\,n-1} \not\equiv 1 \pmod{n}$
を満たすならば $n$ は素数ではない。
Ex.3　$n=1357$, $b=3$ とします。もちろん $3$ は $1357$ では割り切れず、
$b^{\,n-1} = 3^{1356} \equiv 487 \not\equiv 1 \pmod{1357}$
となるので $n=1357$ は素数ではない ことがわかります。
　間違えていけないのは
「$b^{\,n-1} \equiv 1 \pmod{n}$ ならば $n$ は素数である」
とは必ずしも言えない、ということです。ここ大事！
Ex.4　$n=341$, $b=2$ とします。$2$ は $341$ では割り切れず、
$b^{\,n-1} = 2^{340} \equiv 1 \pmod{341}$
が成り立ちます。しかし $341 = 11 \times 31$ ですから $341$ は素数ではありません。

（このように、合成数 $n$ と、$n$ で割り切れない整数 $b$ が
$b^{\,n-1} \equiv 1 \pmod{n}$
を満たすとき、「$n$ は $b$ を底とする擬素数である」と言います。）
　とは言え、Cor.2 は合成数をはじくことには使えますので、 不完全ながら次のような素数判定法が考えられます。
Algorithm 5 (フェルマ・テスト)
  • 入力：大きな自然数 $n$
  • 出力：False ⇒ $n$ は確実に合成数, True ⇒ $n$ は素数かもしれない
def FermatTest($n$):
  for $b$ in [2, 3, 5, 7, 11]:
    if $b^{n-1}\, \% \, n \neq 1$ :
      return False
  return True
　$b=2,3,5,7,11$ の 5 つの底に対して
$b^{\,n-1} \equiv 1 \pmod{n}$
が成り立てばさすがに $n$ は素数なんじゃないの、というアイデアです。
　実際、Alg.5 で True となる合成数は 100万以下で 15 個、1 億以下で 143 個しかありません。 用いる底を $b=2,3,5,7,11,13,17,19,23,29$ の 10 個に増やすと、1 億以下で誤判定される合成数は 75 個に減ります。
  • $b$ をランダムに選ぶ version もあります。
  • 実装の際には $b^{\,n-1}\,\%\,n$ の計算には前回勉強した高速べき乗法を用います。

2. 素数生成

　不完全ながら素数判定が高速にできるようになりましたので、 RSA 暗号に使う大きな素数を作りましょう。
Algorithm 6 (素数生成)
  • 入力：ビット長 $k$
  • 出力：$k$-ビットの素数 $n$
def kBitPrime(k):
  while True:
    $n$ = $k$-ビットの乱数
    if FermatTest($n$) :
      return $n$
　Python で $k$-ビットの乱数を得るには、random module を import して次のように書きます。
random.randint(1 << (k-1), (1 << k) - 1)
1 << (k-1) は $2^{k-1}$ のことで、$k$-ビットで最小の自然数です。 宜しいですね。 ちなみに numpy.random.randint では仕様が違って右端を入れないので
numpy.random.randint(1 << (k-1), (1 << k))
になります。

　Alg.6 の計算量を見積もるためは、 素数が見つかるまでに幾つ位の乱数をテストしなければならないかを知る必要があります。
Th.7（素数定理）　$x$ 以下の素数の個数を $\pi(x)$ と表すと、
$\pi(x) \sim \displaystyle{\frac{x}{\log x}}$
　$\sim$ は「おおよそ」という意味です。 （ 正確に言うと、$x \rightarrow +\infty$ のとき比の極限が 1 になる、ということです。） 証明はとても難しいので、結果だけ使わしてもらいましょう。
Cor.8　$x$ 程度のランダムな整数が素数である確率はおおよそ $\displaystyle{\frac{1}{\log x}}$ である。
証明　
(個数) $=\displaystyle{\int_0^x}$(確率) $dx$
ですから
(確率) $=$ (個数) $'$ $\displaystyle{\sim\frac{d}{dx}\left(\frac{x}{\log x}\right)} =\displaystyle{\frac{1}{\log x}-\frac{1}{\log^2 x}}$ ≒ $\displaystyle{\frac{1}{\log x}}$.
(証明終)
Th.9　Alg.6 の計算量は $O(\log^4 n)$.
証明　フェルマ・テストの計算量は反復2乗法と同じ $O(\log^3 n)$ です。 Cor.8 より素数が見つかるまでに平均でおおよそ $\frac{1}{2}\log n$ 個の乱数をテストしなければならないので、 Alg.6 全体の計算量は
$O(\log^3 n) \times \frac{1}{2}\log n = O(\log^4 n)$
になります。(証明終)
Rem.10　RSA 暗号の正規ユーザが用いる計算の計算量をまとめておきましょう。
  • 素数 $p$, $q$ の生成：$O(\log^4 n)$
  • $n= p \times q$ の計算：$O(\log^2 n)$
  • $m = (p-1) \times (q-1)$ の計算：$O(\log^2 n)$
  • 暗号化指数・復号指数 $e$, $d$ の生成（拡張ユークリッド）：$O(\log^2 n)$
  • 平文の暗号化・暗号文の復号（高速べき乗）：$O(\log^3 n)$
いずれも $\log$ で書ける高速な計算であることがわかります。

3. カーマイケル数

　フェルマ・テストを不完全たらしめている最大の原因はカーマイケル数の存在です。
Def.11　$\gcd(b,n)=1$ を満たす全ての整数 $b$ に対して
$b^{\,n-1} \equiv 1 \pmod{n}$
が成り立つ合成数 $n$ をカーマイケル数と呼ぶ。
Ex.12　$n=561=3 \times 11 \times 17$ はカーマイケル数である。
証明　$\gcd(b,561)=1$ であれば、フェルマの小定理より \begin{align} b^{2} &\equiv 1 \pmod 3, \\ b^{10} &\equiv 1 \pmod{11}, \\ b^{16} &\equiv 1 \pmod{17} \\ \end{align} となります。それぞれ、$280$ 乗、$56$ 乗、$35$ 乗すると \begin{align} b^{560} &\equiv 1 \pmod 3, \\ b^{560} &\equiv 1 \pmod{11}, \\ b^{560} &\equiv 1 \pmod{17} \\ \end{align} となり、 $b^{560}-1$ は $3$, $11$, $17$ の公倍数ですから
$b^{\,560} \equiv 1 \pmod{561}$.
(証明終)

　次の定理を使うと大きなカーマイケル数を作ることができます。
Th.13　$p=6k+1$, $q=12k+1$, $r=18k+1$ が全て素数であれば $n=p\,q\,r$ はカーマイケル数である。
　証明は Ex.12 と全く同じです。
Ex.14　
k = 2239744742177804210557442280568444278121645497234649534899989100963791871180160945380877493271609318291
のとき
p = 6k + 1 = 13438468453066825263344653683410665668729872983407897209399934605782751227080965672285264959629655909747
q = 12k + 1 = 26876936906133650526689307366821331337459745966815794418799869211565502454161931344570529919259311819493
r = 18k + 1 = 40315405359200475790033961050231997006189618950223691628199803817348253681242897016855794878888967729239
は全て素数で
n = pqr = 14561314392384758852607372045391100342305613529432683239147836573776346740245578013749386663115053375527637666588629193151550389687696379599004671655261602333117349735165428436344922950761580622183044886774735262914257003709862150465768021078578761491289686266731268838123191809245649371909369818627048924845769
は 1031 ビットのカーマイケル数。
Rem.15　$b^{n-1} \,\%\, n$ は $\gcd(b,n)$ の倍数です。 ですから、$n$ がカーマイケル数のときは、
  • $\gcd(b,n)=1$ $\Leftrightarrow$ $b^{n-1} \,\%\, n = 1$
  • $\gcd(b,n)\neq 1$ $\Leftrightarrow$ $b^{n-1} \,\%\, n \neq 1$
ということになります。
　カーマイケル数 $n$ が小さな素因子を持てば、 底 $b$ をランダムにとる version のフェルマ・テストで $n$ を合成数だと見破ることができますが、 Ex.14 のように素因子が巨大なカーマイケル数では絶望的です。
Rem.16　厄介者のカーマイケル数は無限個存在することが証明されています。 しかし幸いなことに、そんなにたくさんはありません。
Rem.17　カーマイケル数も合成数だと見破ることのできる確率的素数判定法としては
  • ミラー・ラビン法
  • ソロベイ・ストラッセン法
などがあります。 前者は今迄の本講義の知識で理解できますが、 後者を理解するには「平方剰余」の知識が必要となります。

まとめ

  • RSA 暗号に必要な大きな素数は、たとえばフェルマ・テストで作ることができる。
  • RSA 暗号の正規ユーザが行う計算は高速にできる。
  • カーマイケル数という合成数はフェルマ・テストでは誤判定される可能性があるが、 たくさんは無いのであまり気にしなくて良い。

課題２

  • RSA 暗号の鍵 $p$, $q$, $n$, $e$, $d$ を、$p$ が 510ビット、$q$ が 520ビット程度になるように生成し、 公開鍵 $n$, $e$ を塩田に送信せよ。秘密鍵は各自保管しておくこと。
  • 折り返し塩田から暗号文を返送するので復号せよ。 正しく復号できれば復号文は８桁の数字になり、西暦４桁＋月２桁＋日２桁である著名人の誕生日を表している。 その著名人を答えよ。
  • 提出期限 : 7月6日

戻る