トネリ・シャンクスのアルゴリズム

整数全体 ${\displaystyle \mathbb {Z} }$ は代数的には環(有理整数環)を成しており、素数 ${\displaystyle p}$ の倍数の集合 ${\displaystyle p\mathbb {Z} }$ は ${\displaystyle \mathbb {Z} }$ の極大イデアルを成している。

${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ は 0 から ${\displaystyle p-1}$ の整数で構成される集合であるが、これは有限体を成しており、${\displaystyle \mathbf {F} _{p}}$ と表記される。ただし、${\displaystyle \mathbf {F} _{p}}$ における加法と乗法は、${\displaystyle \mathbb {Z} }$ における${\displaystyle p}$を法とする剰余算(モジュラー算法、mod算)と同じものになる。以降、${\displaystyle \mathbf {F} _{p}}$ における演算は mod算の形式で表記することにする(${\displaystyle r^{2}=n{\pmod {p}}}$ など)。${\displaystyle \mathbf {F} _{p}}$ においては ${\displaystyle -1=p-1{\pmod {p}}}$ である。

${\displaystyle \mathbf {F} _{p}}$ から 0 を除いた集合を ${\displaystyle {\mathbf {F} _{p}}^{\times }}$ と表記することにすれば、${\displaystyle {\mathbf {F} _{p}}^{\times }}$ は ${\displaystyle \mathbf {F} _{p}}$ の乗法について位数が ${\displaystyle p-1}$ の巡回群(pを法とする整数の乗法群)を成す。従って、${\displaystyle {\mathbf {F} _{p}}^{\times }}$ の任意の元 ${\displaystyle n}$ について、

${\displaystyle n^{p-1}=1{\pmod {p}}}$

が成り立つ。これをフェルマーの小定理と呼ぶ。

以降、${\displaystyle p}$ は奇素数(2ではない素数)とする。${\displaystyle p-1}$ は0でない偶数であるから ${\displaystyle {\frac {p-1}{2}}}$ は 0 でない整数となる。${\displaystyle {\mathbf {F} _{p}}^{\times }}$ の任意の元 ${\displaystyle n}$ について、${\displaystyle (n^{\frac {p-1}{2}})^{2}=n^{p-1}=1{\pmod {p}}}$ である。${\displaystyle \mathbf {F} _{p}}$ は体であるから、${\displaystyle x^{2}=1{\pmod {p}}}$ の解は ${\displaystyle x=\pm 1{\pmod {p}}}$ のみである。従って、${\displaystyle n^{\frac {p-1}{2}}=\pm 1{\pmod {p}}}$ である。

オイラーの規準によれば、${\displaystyle n}$ が ${\displaystyle {\mathbf {F} _{p}}^{\times }}$ で平方根を持つ(つまり、${\displaystyle n}$ が平方剰余である)のは、次の場合のみである。

${\displaystyle n^{\frac {p-1}{2}}=1{\pmod {p}}}$

一方、${\displaystyle {\mathbf {F} _{p}}^{\times }}$ の元 ${\displaystyle z}$ が ${\displaystyle {\mathbf {F} _{p}}^{\times }}$ で平方根を持たない場合(つまり、${\displaystyle z}$ が平方非剰余である)、オイラーの規準によれば、次のようになる。

${\displaystyle z^{\frac {p-1}{2}}=-1{\pmod {p}}}$

${\displaystyle {\mathbf {F} _{p}}^{\times }}$ は位数 ${\displaystyle p-1}$ の巡回群であり、その正確に半数が平方非剰余であるので、このような ${\displaystyle z}$ を見つけるのは難しくない。したがって、以降、このような平方非剰余に常にアクセスできると仮定する。群論的には、全ての平方非剰余は巡回群 ${\displaystyle {\mathbf {F} _{p}}^{\times }}$ の生成元である。

Summarize Timeline Top Qs Fact Check

以降、${\displaystyle n^{\frac {p-1}{2}}=1{\pmod {p}}}$ を満たす(つまり平方剰余である) ${\displaystyle {\mathbf {F} _{p}}^{\times }}$ の元 ${\displaystyle n}$ の ${\displaystyle {\mathbf {F} _{p}}^{\times }}$ における平方根を求めるものとする。

${\displaystyle p=3{\pmod {4}}}$ となる素数に対しては、トネリ・シャンクスのアルゴリズムを用いなくても、${\displaystyle r=\pm n^{\frac {p+1}{4}}{\pmod {p}}}$ と置けば、

${\displaystyle r^{2}=(n^{\frac {p+1}{4}})^{2}=n^{{\frac {p-1}{2}}+1}=n^{\frac {p-1}{2}}\cdot n=n{\pmod {p}}}$

であるから、${\displaystyle r}$ が求める ${\displaystyle n}$ の平方根である。

以降は、${\displaystyle p=1{\pmod {4}}}$ となる素数 ${\displaystyle p}$ について考える。

${\displaystyle p-1}$ は、2 で繰り返し割ることで、${\displaystyle Q2^{S}}$と表すことができる。ここで ${\displaystyle Q}$ は奇数、 ${\displaystyle S}$ は非負整数とする。${\displaystyle p=1{\pmod {4}}}$ であるから ${\displaystyle p-1}$ は 4 の倍数である。従って、${\displaystyle S}$ の最小値は 2 となる。

${\displaystyle R=n^{\frac {Q+1}{2}}{\pmod {p}}}$

とすると、${\displaystyle R^{2}=n^{Q+1}=(n)(n^{Q}){\pmod {p}}}$ となる。${\displaystyle t=n^{Q}{\pmod {p}}}$ と置く。${\displaystyle t=1{\pmod {p}}}$ であれば、${\displaystyle R}$ は ${\displaystyle n}$ の平方根となる。それ以外の場合、${\displaystyle R}$ と ${\displaystyle t}$ は次式を満たす。

• ${\displaystyle R^{2}=nt{\pmod {p}}}$；かつ
• ${\displaystyle t^{2^{S-1}}=n^{Q2^{S-1}}=n^{\frac {p-1}{2}}=1{\pmod {p}}}$

これを群論的に考えると、${\displaystyle t}$ は巡回群 ${\displaystyle {\mathbf {F} _{p}}^{\times }}$ の元であり、その位数は ${\displaystyle 2^{S-1}}$ の約数ということである。この位数を ${\displaystyle 2^{M}}$ (${\displaystyle M}$ は整数)と置けば、${\displaystyle 1\leq M\leq S-1}$ である(${\displaystyle M}$ が 0 の場合、${\displaystyle t}$ の位数は 1 となるが ${\displaystyle t\neq 1}$ を仮定しているので、これはあり得ないことになる)。${\displaystyle M}$ の値は ${\displaystyle t}$ を順次2乗することで得られる(最初に1になるまでに2乗した回数が ${\displaystyle M}$ となる)。

${\displaystyle (t^{2^{(M-1)}})^{2}=t^{2^{M}}=1{\pmod {p}}}$ であるから、前節で説明したように、${\displaystyle t^{2^{(M-1)}}=\pm 1{\pmod {p}}}$ である。${\displaystyle t^{2^{(M-1)}}=1{\pmod {p}}}$ であれば、${\displaystyle t}$ の位数は ${\displaystyle 2^{(M-1)}}$ となるので仮定に反する。従って ${\displaystyle t^{2^{(M-1)}}=-1{\pmod {p}}}$ でなければならない。

ここでもし、-1 の ${\displaystyle 2^{M}}$ 乗根となるような ${\displaystyle {\mathbf {F} _{p}}^{\times }}$ の元${\displaystyle b}$ が存在するとしよう。${\displaystyle b^{2^{M}}=(b^{2})^{2^{(M-1)}}=-1{\pmod {p}}}$ であるから ${\displaystyle t^{2^{(M-1)}}(b^{2})^{2^{(M-1)}}=1{\pmod {p}}}$ である。${\displaystyle R}$、${\displaystyle t}$ と ${\displaystyle b}$ の関係は次のようになる。

• ${\displaystyle (Rb)^{2}=nt\cdot b^{2}=n(t\cdot b^{2}){\pmod {p}}}$；かつ
• ${\displaystyle (t\cdot b^{2})^{2^{(M-1)}}=1{\pmod {p}}}$。従って、${\displaystyle t\cdot b^{2}}$ の位数は ${\displaystyle 2^{(M-1)}}$ の約数である。

${\displaystyle t\cdot b^{2}}$ の位数を ${\displaystyle 2^{M'}}$ と置く。${\displaystyle M'}$ は明らかに${\displaystyle M}$ より小さい整数である。${\displaystyle M'}$ の値は ${\displaystyle tb^{2}}$ を順次2乗することで得られる(最初に1になるまでに2乗した回数が ${\displaystyle M'}$ となる)。

${\displaystyle Rb}$、${\displaystyle t\cdot b^{2}}$、${\displaystyle M'}$ を新たに ${\displaystyle R}$、 ${\displaystyle t}$、${\displaystyle M}$ と書き換えて、以降同じ手順を ${\displaystyle M}$ が 0 となるまで繰り返せば、${\displaystyle t=1{\pmod {p}}}$ となり、${\displaystyle R^{2}=nt=n{\pmod {p}}}$ となるので、このときの ${\displaystyle R}$ が求めていた ${\displaystyle n}$ の平方根となる。

以上のアルゴリズムを群論的に要約すれば、各ステップでは、${\displaystyle t}$ の正確な位数を測定し、同じ位数の要素を乗算することで、${\displaystyle t}$ をより小さな位数の部分群の生成元に書き換えるということである。

では、-1 の ${\displaystyle 2^{M}}$ 乗根となるような都合の良い ${\displaystyle b}$ をどのように見つけるかが次の問題になるが、これを解決するためのトリックは、既知の平方非剰余である ${\displaystyle z}$ を利用することである。上に示した ${\displaystyle z}$ にオイラーの規準を適用すると、${\displaystyle z^{Q}}$ は -1 の ${\displaystyle 2^{S-1}}$ 乗根であることが示される。したがって、${\displaystyle (z^{Q})^{2^{S-1}}=z^{Q\cdot 2^{S-1}}=-1=b^{2^{M}}{\pmod {p}}}$ であるから ${\displaystyle b=(z^{Q})^{2^{S-1-M}}{\pmod {p}}}$ と置けば良いことが分かる。

以上がこのアルゴリズムのアウトラインである。

Summarize Timeline Top Qs Fact Check

入力

• ${\displaystyle p}$:   ${\displaystyle p=1{\pmod {4}}}$ を満たす素数
• ${\displaystyle n}$:   ${\displaystyle {\mathbf {F} _{p}}^{\times }}$ の平方剰余

出力

• ${\displaystyle r}$:   ${\displaystyle r^{2}=n{\pmod {p}}}$ を満たす ${\displaystyle \mathbf {F} _{p}}$ の元

入力チェック

1. ${\displaystyle n=0{\pmod {p}}}$ の場合、${\displaystyle r=0}$ を返して終了。
2. ${\displaystyle n}$ が平方剰余でない場合(オイラー規準でチェック)、エラーを返して終了。
3. ${\displaystyle p}$ が奇素数でない場合、エラーを返して終了。
4. ${\displaystyle p=3{\pmod {4}}}$ の場合、${\displaystyle r=n^{\frac {p+1}{4}}{\pmod {p}}}$ を返して終了。

初期設定

1. ${\displaystyle p-1}$ を 2 で繰り返し割って、${\displaystyle p-1=Q2^{S}}$ となる 奇数 ${\displaystyle Q}$ と 整数 ${\displaystyle S}$ を求める。
2. ${\displaystyle {\mathbf {F} _{p}}^{\times }}$ の平方非剰余を1つ探し ${\displaystyle z}$ と置く。(${\displaystyle z^{\frac {p-1}{2}}=-1{\pmod {p}}}$)
3. ループ変数 ${\displaystyle t,\,M,\,R,\,c\,}$ 初期値設定
   • ${\displaystyle M=S{\pmod {p}}}$
   • ${\displaystyle t=n^{Q}{\pmod {p}}}$
     • ${\displaystyle n}$ は平方剰余であるので、${\displaystyle t^{2^{(M-1)}}=(n^{Q})^{2^{(S-1)}}=n^{Q2^{(S-1)}}=n^{\frac {p-1}{2}}=1{\pmod {p}}}$ である。
   • ${\displaystyle R=n^{\frac {Q+1}{2}}{\pmod {p}}}$      (${\displaystyle R^{2}=tn{\pmod {p}}}$)
   • ${\displaystyle c=(z^{Q})^{2^{S-1}}{\pmod {p}}}$     
     • ${\displaystyle z}$ は平方非剰余であるので、${\displaystyle c^{2^{(M-1)}}=(z^{Q})^{2^{(S-1)}}=z^{Q2^{(S-1)}}=z^{\frac {p-1}{2}}=-1{\pmod {p}}}$ である。

ループ不変条件
ループの各反復処理の開始時には、ループ変数間で以下の関係式(ループ不変条件)が成立する。

• ${\displaystyle t^{2^{(M-1)}}=1{\pmod {p}}}$
• ${\displaystyle R^{2}=tn{\pmod {p}}}$
• ${\displaystyle c^{2^{(M-1)}}=-1{\pmod {p}}}$

ループ

1. ${\displaystyle t=1}$ の場合、${\displaystyle r=R}$ を返して終了(ループ終了条件)。
   • ループ不変条件の ${\displaystyle R^{2}=tn{\pmod {p}}}$ から ${\displaystyle R^{2}=n{\pmod {p}}}$
2. ${\displaystyle t}$ を繰り返して2乗し、${\displaystyle t^{2^{M'}}=1{\pmod {p}}}$ となる最小の非負整数 ${\displaystyle M'}$ を求める。
   • ${\displaystyle t^{2^{(M'-1)}}=-1{\pmod {p}}}$
3. ${\displaystyle b=c^{2^{(M-1-M')}}{\pmod {p}}}$ とする。
   • ループ不変条件の ${\displaystyle c^{2^{(M-1)}}=-1{\pmod {p}}}$ から ${\displaystyle (b^{2})=c^{2^{(M-M')}}{\pmod {p}}}$、
     従って ${\displaystyle (b^{2})^{2^{M'-1}}=c^{2^{(M-1)}}=-1{\pmod {p}}}$
   • ${\displaystyle t^{2^{(M'-1)}}(b^{2})^{2^{(M'-1)}}=(-1)(-1)=1{\pmod {p}}}$、従って ${\displaystyle (tb^{2})^{2^{(M'-1)}}=1{\pmod {p}}}$。
     ループ不変条件の ${\displaystyle R^{2}=tn{\pmod {p}}}$ から ${\displaystyle (Rb)^{2}=tb^{2}n{\pmod {p}}}$。
4. ループ変数を更新。
   • ${\displaystyle M\leftarrow M'}$
   • ${\displaystyle t\leftarrow tb^{2}}$
   • ${\displaystyle R\leftarrow Rb}$
   • ${\displaystyle c\leftarrow b^{2}}$

更新されたループ変数はループ不変条件を満たしている。ループ不変条件の ${\displaystyle t^{2^{(M-1)}}=1{\pmod {p}}}$ から ${\displaystyle M'}$ は更新前の ${\displaystyle M-1}$ 以下であり、${\displaystyle M}$ は各反復で厳密に小さくなるため、アルゴリズムは停止することが保証される。

Summarize Timeline Top Qs Fact Check

合同式 r² ≡ 5 (mod 41) を解く。41 は要求どおり素数であり、41 ≡ 1 (mod 4) を満たす。5 はオイラーの基準により平方剰余である: ${\displaystyle 5^{\frac {41-1}{2}}=5^{20}=1}$ (前述と同様に、${\displaystyle (\mathbb {Z} /41\mathbb {Z} )^{\times }}$ 内の演算は暗黙的に mod 41 である)。

1. ${\displaystyle p-1=40=5\cdot 2^{3}}$ なので、 ${\displaystyle Q\leftarrow 5}$、 ${\displaystyle S\leftarrow 3}$
2. z の値を求める。
   • ${\displaystyle 2^{\frac {41-1}{2}}=1}$ なので、2 はオイラーの定理により平方剰余である。
   • ${\displaystyle 3^{\frac {41-1}{2}}=40=-1}$ なので、3 は平方剰余ではない。set ${\displaystyle z\leftarrow 3}$
3. Set
   • ${\displaystyle M\leftarrow S=3}$
   • ${\displaystyle c\leftarrow z^{Q}=3^{5}=38}$
   • ${\displaystyle t\leftarrow n^{Q}=5^{5}=9}$
   • ${\displaystyle R\leftarrow n^{\frac {Q+1}{2}}=5^{\frac {5+1}{2}}=2}$
4. Loop:
   • 最初の反復:
     • ${\displaystyle t\neq 1}$ なので、まだ終了していない
     • ${\displaystyle t^{2^{1}}=40}$、${\displaystyle t^{2^{2}}=1}$ なので、${\displaystyle i\leftarrow 2}$
     • ${\displaystyle b\leftarrow c^{2^{M-i-1}}=38^{2^{3-2-1}}=38}$
     • ${\displaystyle M\leftarrow i=2}$
     • ${\displaystyle c\leftarrow b^{2}=38^{2}=9}$
     • ${\displaystyle t\leftarrow tb^{2}=9\cdot 9=40}$
     • ${\displaystyle R\leftarrow Rb=2\cdot 38=35}$
   • 2回目の反復:
     • ${\displaystyle t\neq 1}$ なので、まだ完了していない
     • ${\displaystyle t^{2^{1}}=1}$ なので ${\displaystyle i\leftarrow 1}$
     • ${\displaystyle b\leftarrow c^{2^{M-i-1}}=9^{2^{2-1-1}}=9}$
     • ${\displaystyle M\leftarrow i=1}$
     • ${\displaystyle c\leftarrow b^{2}=9^{2}=40}$
     • ${\displaystyle t\leftarrow tb^{2}=40\cdot 40=1}$
     • ${\displaystyle R\leftarrow Rb=35\cdot 9=28}$
   • 3回目の反復:
     • ${\displaystyle t=1}$ となり、終了。 ${\displaystyle r=R=28}$ を返す。

確かに、28² ≡ 5 (mod 41) であり、(-28)² ≡ 13² ≡ 5 (mod 41) である。したがって、このアルゴリズムは、合同式の2つの解を正しく導出している。

Summarize Timeline Top Qs Fact Check

トネリ・シャンクスのアルゴリズムは、(すべての可能な入力(平方剰余と平方非剰余)にわたって平均すると)

${\displaystyle 2m+2k+{\frac {S(S-1)}{4}}+{\frac {1}{2^{S-1}}}-9}$

回の剰余乗算を必要とする。ここで、${\displaystyle m}$ は ${\displaystyle p}$ の2進表現の桁数、${\displaystyle k}$ は ${\displaystyle p}$ の2進表現における1の数である。必要な平方非剰余 ${\displaystyle z}$ を、ランダムに取った数 ${\displaystyle y}$ が平方非剰余かどうかを調べることによって求める場合、(平均して) 2回のルジャンドル記号の計算が必要である ^[6]。 ルジャンドル記号の2 回の計算の平均は次のように説明される。${\displaystyle y}$ は、確率 ${\displaystyle {\tfrac {\tfrac {p+1}{2}}{p}}={\tfrac {1+{\tfrac {1}{p}}}{2}}}$ で平方剰余になる。これは ${\displaystyle 1}$ より小さいが、${\displaystyle \geq {\tfrac {1}{2}}}$ である。したがって、平均すると ${\displaystyle y}$ が平方剰余であるかどうかを 2 回確認する必要がある。

これは本質的に、法 ${\displaystyle p}$ がランダムである場合、つまり ${\displaystyle S}$ が ${\displaystyle p}$ の2進表現の桁数に対してそれほど大きくない場合、トネリ・シャンクスのアルゴリズムが非常にうまく機能することを示している。前述のように、Cipollaのアルゴリズム は、${\displaystyle S(S-1)>8m+20}$ の場合(そしてその場合のみ)、トネリ・シャンクスのアルゴリズムよりもうまく機能しする。 しかし、代わりにサザーランドのアルゴリズムを使用して ${\displaystyle \mathbb {F} _{p}^{\ast }}$ の 2-シロー部分群における離散対数計算を実行する場合、${\displaystyle S(S-1)}$ を ${\displaystyle O(S\log S/\log \log S)}$ によって漸近的に制限される式に置き換えることができる ^[7]。 明示的には、${\displaystyle c^{e}\equiv n^{Q}}$ となるような ${\displaystyle e}$ を計算し、${\displaystyle R\equiv c^{-e/2}n^{(Q+1)/2}}$ が ${\displaystyle R^{2}\equiv n}$ を満たすようにする(${\displaystyle n}$ は平方剰余なので、${\displaystyle e}$ は2の倍数であることに注意)。

このアルゴリズムでは、平方剰余でない数 ${\displaystyle z}$ を求める必要がある。このような ${\displaystyle z}$ を多項式時間で求める決定論的アルゴリズムは知られていない。しかし、一般化されたリーマン予想が正しい場合、平方非剰余 ${\displaystyle z<2\ln ^{2}{p}}$、 ^[8] が存在し、上記の限度まですべての ${\displaystyle z}$ をチェックし、多項式時間 内で適切な ${\displaystyle z}$ を見つけることができる。ただし、これは最悪のシナリオであることに留意してしてもらいたい。一般に、${\displaystyle z}$ は上記のように平均 2 回の試行(つまり確率1/2)で見つかる。

トネリ・シャンクスのアルゴリズムは(当然のことながら)素数を法とする平方根が必要となるあらゆる処理に使用できる。例えば、楕円曲線上の点を求めるのに使用できる。また、デジタル署名におけるラビン署名アルゴリズムや、素因数分解における二次ふるい法のふるい分けステップの計算においても有用である。