パンの木を植えて

主として数学の話をするブログ

トップ > A Computational Introduction to Number Theory and Algebra > 原始根を見つけるアルゴリズム - Ex11.1

原始根を見つけるアルゴリズム - Ex11.1

A Computational Introduction to Number Theory and Algebra
\[ %%% 黒板太字 %%% \newcommand{\A}{\mathbb{A}} %アフィン空間 \newcommand{\C}{\mathbb{C}} %複素数 \newcommand{\F}{\mathbb{F}} %有限体 \newcommand{\N}{\mathbb{N}} %自然数 \newcommand{\Q}{\mathbb{Q}} %有理数 \newcommand{\R}{\mathbb{R}} %実数 \newcommand{\Z}{\mathbb{Z}} %整数 %%% 2項演算 %%% \newcommand{\f}[2]{ \frac{#1}{#2} } \]

最近，Youtubeでよくゲーム実況動画を見ています．

自分でやっても楽しいですけど，時間もハードも体力もないからね．

GhostWire :Tokyoの実況の続きを楽しみにしています．Playstation5ってすごいなあ．



それはそうと，Shoup『A Computational Introduction to Number Theory and Algebra』の演習問題をやっていきます．

A Computational Introduction to Number Theory and Algebra

A Computational Introduction to Number Theory and Algebra

Amazon

今回やるのは Ex11.1です．

\[ %%% 黒板太字 %%% \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\F}{\mathbb{F}} \newcommand{\N}{\mathbb{N}} %%% カリグラフィー %%% \newcommand{\calf}{\mathcal{F} } \newcommand{\calg}{\mathcal{G} } %%% 引数を取るもの %%% \newcommand{\f}[2]{ \frac{#1}{#2} } \newcommand{\im}{\operatorname{im} } \]

問題文

Suppose we are not given the prime factorization of $p-1$, but rather, just a prime $q$ dividing $p-1$, and we want to find an element of multiplicative order $q$ in $\mathbb{Z}_p^*$. Design and analyze an efficient algorithm to do this.

Ex11.1

一応日本語に訳しておきます．


素数 $p$ と，$p-1$ の素因数 $q$ が与えられていたとします．このとき乗法群 $\mathbb{Z}_p^*$ の位数 $q$ の元をひとつ見つけたいと思っています．これを行う効率的なアルゴリズムを設計し，解析してください．


問題の背景

いきなり位数 $q$ の元を見つけよと言われても意味がわからないと思いますが，この問題の前提には原始根を発見するアルゴリズムがあります．

原始根というのは，単数群 $\mathbb{Z}_p ^*$ の生成元のことです．$\mathbb{Z}_p ^*$ は巡回群なので，生成元が存在します．


さて素数 $p$ に対する原始根の見つけ方ですが．

単純に $1,2 , \cdots p-1 \in \mathbb{Z}_p^*$ を列挙してそれぞれの $1, 2, \cdots , \frac{p-1}{2}$ 乗を計算していると $Ω(p^ 2)$ くらいの時間がかかってしまいます．小さい例の手計算ではアリかもしれませんが，数が大きくなるとそれではてんでダメです．

より高速な方法がありまして，本文で紹介されているのは乱数を使う方法です．（ただし，素因数分解がわかっている必要はあります）


その方法を説明します．まず $p-1$ の素因数分解がわかっているものとし，その異なる素因数を $q_1, \cdots , q_r$ とします．つまり

$$ p-1 = \prod_{i=1}^r q_i^{e_i} $$

とします．

このとき，次の疑似コードで表されるアルゴリズムを考えます．（以下の画像は本文から引用したものです）


手続きの正当性

各 $i$ に対して $γ_i$ を計算しています．

$γ_i$ の位数を $\mathrm{ord}_i$ とします．$\gamma_i^{q_i^{e_i}} = 1$ なので，$\mathrm{ord}_i$ は $q_i^{e_i}$ を割り切ります．$q_i$ は素数なので，$\mathrm{ord}_i$ は $q_i$ のベキです．$β = γ_i^{q_i^{e_i - 1}}$ は仮定より $1$ ではないので，$\mathrm{ord}_i$ は $q_i^{e_i}$ でしかありえません．よって $γ_i$ の位数は $q_i^{e_i}$ です．


これにより $γ$ の位数がわかります．$γ_i$ の位数が $q_i^{e_i}$ で，各 $i$ に対して $γ_i$ の位数が互いに素なので $γ$ の位数は $γ_i$ の位数の積になります．したがって，$γ$ の位数は $p-1$ です．


計算時間の解析

For ループの繰り返し回数は $r$ 回で固定なので，repeat 文が何回実行されるかを考えましょう．

各 $i$ に対して，repeat の実行回数を $L_i$ とします．$L_i$ は確率的に決まる数です．$α$ を最初に一様ランダムに選んでいるため，$β$ は $(p-1)/ q_i$ 乗する群準同型の像 $B_i$ の中に一様に分布します．$|B_i| = q$ なので，$β=1$ となる確率は $1/q$ です．

つまり，$L_i$ とは，「$1-1/q$ の確率で成功する試行を繰り返すときに，最初に成功するまでに試行を繰り返す回数」であるわけです．これは幾何分布に従います．従って幾何分布についての一般論により，

$$ E[L_i] = \frac{1}{1 - 1/q} \leq 2 $$

であることが従います．

さてべき乗の計算は，繰り返し自乗法により $O( (\log p)^ 3)$ 時間でできます．したがって全体の計算時間は

$$ \sum_{1 \leq i \leq r} (L_i + (\log p)^3) = O( r (\log p)^3 ) $$

です．

ところで $r$ は $r \leq \log_2 p$ を満たすので，結局計算時間は $O( (\log p)^ 4 )$ くらいです．


実際には $p-1$ の素因数分解が大変なのですが，ただ単に大きな素数 $p$ と単数群 $\mathbb{Z}_p^{*}$ の生成元が欲しいだけなら

  1. 大きな合成数 $n$ をランダムに作る

  2. $p=n+1$ が素数かどうか素数判定する

  3. 単数群 $\mathbb{Z}_p^{*}$ の生成元を求める

という順に手続きを進めることで高速に計算ができることがわかります．

便利ですね．


問題の回答

$p-1$ の素因数分解がすべてわかっているわけではなく，$p-1$ を割りきる素数 $q$ がわかっているというだけの状態で，位数 $q$ を持つような $\mathbb{Z}_p^*$ の元 $\beta$ を求めるアルゴリズムを作りなさいという問題でした．


これは，先ほど説明した原始根を求めるアルゴリズムの転用でできます．

次の手続きを考えましょう．

  1. While TRUE do

  2.   $α \in \mathbb{Z}_p^*$ をランダムに選ぶ

  3.   $β = α^{ (p-1)/q }$ を繰り返し自乗法で計算する

  4.   If $β \neq 1$ then

  5.     break

  6. return $β$

このときアルゴリズムが停止するなら，返り値の $β$ は先ほどと同様の考察により，位数が $q$ です．

かつ，このアルゴリズムの計算時間の期待値は $O( (\log p)^ 3 )$ になります．

これでおしまいです．


感想

原始根を計算する際，いままでは虱潰しにすべての要素のすべてのべきを計算していたので，目からうろこでした．

そんなに難しい技法は使っていないのですが，これを自力で思いつくのは私には難しそうです．