剰余環を用いた冪根の高速計算

ゆうき

平成 15 年 12 月 13 日

概要

剰余環 ℤ/rℤ に於けるニュートン法などを用いて、 perfect powers の冪根を高速に求める方法を考える。

目次

1 平方根 1

2 奇数乗根 4

3 一般の冪根 7

1 平方根

今、 2 の冪を法としたニュートン法を用いようとしているので、平方根は他の素数乗根とは別に考える必要がある。

Lemma 1.1. 1 以上の自然数 b について、 2i ≡ 2j (mod 2^{b+1}) ならば i^{2} ≡ j^{2} (mod 2^{b+1})

Proof. 仮定より 2(i − j) が (mod 2^{b+1}) の倍数だから i − j は 2^{b} の倍数。

特に、 i, j の偶奇は一致するので、 i + j は 2 の倍数。

したがって、 i^{2} − j^{2} = (i + j)(i − j) は 2 · 2^{b} = 2^{b+1} の倍数。

Algorithm 1.2 (剰余環上の平方根の逆数).nsqrt 2exp(y, b)

入力 y ∈ ℕ_{odd}, b ∈ ℕ

出力 yr^{2} ≡ 1 (mod 2^{b+1}) なる r ∈ ℕ。もしそのような r が存在しなければ 0 を返す。

1. y mod 4 ≠ 1 ならば 0 を返して終了

2. b = 1 のとき、 1 を返して終了

3. b_{0} := 2, r_{0} := y mod 8

4. r_{0} ≠ 1 ならば 0 を返して終了

5. b = 2 のとき、 1 を返して終了

6. for i = 1, 2, ...

b_{i} := 2b_{i−1} − 1

b_{i} ≥ b ならば、ループを終了 r_{i} := (3r_{i−1} − yr_{i−1}^{3})/2 mod 2^{b_{i}} 7. b_{i} ≥ b となった最大の i、すなわちループを終了したときの i を、 i_{∗}

とする。

8. r := (3r_{i_{∗}−1} − yr_{i_{∗}−1}^{3})/2 mod 2^{b} を返してアルゴリズムを終了

Lemma 1.3. Algorithm 1.2 は正しく動作する。

Proof. b = 1, 2 の場合は自明。以下、 b > 2 について考える。

Step 1 によって 0 が返った場合、 yr^{2} ≡ 1 (mod 4) を満たす r は存在しない。 4 | 2^{b+1} なので、 mod2^{b+1} においても存在しない。従って、返り値 0 は正しい。

Step 3 においても同様。以下、 Step 8 における返り値を吟味する。

r_{i_{∗}} := (3r_{i_{∗}−1} − yr_{i_{∗}−1}^{3})/2 mod 2^{b_{i∗}}

と定義する。 b_{i_{∗}} ≥ b より、 0 ≤ i ≤ i_{∗} の各 i について、 yr_{i}^{2} ≡ 1 (mod 2^{b_{i}+1}) を証明すれば十分。 i についての帰納法によってこれを証明する。

i = 0 については、 step 1 により自明。今、ある i_{0} について成立したものと仮定して、 i = i_{0} + 1 について証明する。

帰納法の仮定より yr_{i−1}^{2} ≡ 1 (mod 2^{b_{i−1}+1}) である。従って r_{i−1} は奇であり、 r_{i} は well-defined.

また前式より、次のような j ∈ ℕ が存在する。

yr_{i−1}^{2} = 1 + 2^{b_{i−1}+1}j  (1)

ここで r_{i} の定義より

2r_{i} ≡ 3r_{i−1} − yr_{i−1}^{3} (mod 2^{b_{i}+1})
= r_{i−1} (3 − yr_{i−1}^{2})
= r_{i−1} (3 − 1 − 2^{b_{i−1}+1}j) (∵ (1))
= 2r_{i−1} (1 − 2^{b_{i−1}}j)

すると、 Lemma 1.1 より

r_{i}^{2} ≡ r_{i−1}^{2} (1 − 2^{b_{i−1}}j)^{2} (mod 2^{b_{i}+1})

従って、

yr_{i}^{2} ≡ yr_{i−1}^{2} (1 − 2^{b_{i−1}}j)^{2} (mod 2^{b_{i}+1})
= (1 + 2^{b_{i−1}+1}j) (1 − 2^{b_{i−1}+1}j + 2^{2b_{i−1}}j^{2})
≡ (1 + 2^{b_{i−1}+1}j) (1 − 2^{b_{i−1}+1}j) (mod 2^{b_{i}+1})  (∵ 2b_{i−1} = b_{i} + 1)
= (1 − 2^{2b_{i−1}+2}j^{2})
≡ 1 (mod 2^{b_{i}+1})  (∵ 2b_{i−1} + 2 > b_{i} + 1)

Corollary 1.4. n ∈ ℕ_{odd}, b ∈ ℕ に対し、

                   r = n · nsqrt 2exp(n, b)

とすると、 r ≠ 0 ⇔ r^{2} ≡ n (mod 2^{b+1}) である。 Proof. n mod 2^{b+1} ≠ 0 より ⇐ は明らか。

⇒ は、 s = nsqrt 2exp(n, b) とおけば、 Lemma より

r^{2} = (ns)^{2} = n(ns^{2}) ≡ n (mod 2^{b+1})

となって成立する。

Algorithm 1.5 (奇数の平方根). odd sqrt(n)

入力 n ∈ ℕ_{odd}

出力 n = r^{2} なる自然数 r。もしそのような r が存在しなければ 0 を返す。

1. 2^{2b} ≥ n なる最小の b をとる

2. r := n · nsqrt(n, b) mod 2^{b}

3. r = 0 ならば 0 を返して終了

4. r^{2} = n ならば r を返して終了

5. (2^{b} − r)^{2} = n ならば 2^{b} − r を返して終了

6. 0 を返して終了

Theorem 1.6. Algorithm 1.5 は正しく動作する。

Proof. Step 3 により 0 が返ったとき、 Corollary 1.4 より ℤ/2^{b+1}ℤ においては n の平方根は存在しない。従って、 ℤ においても存在せず、返り値 0 は正しい。 Step 4,5 により値が返ったとき、その値が正当であることは自明。

以下では残る step 6 においての返り値 0 が正しいことを示す。そのためには、 ℤ における n の平方根 s ∈ ℕ が存在したとき s = r または s = 2^{b} − r が成立して、 step4,5 において必ずその値が返ることを言えば十分である。

Corollary 1.4 より r^{2} ≡ n = s^{2} (mod 2^{b+1}) なので、

2^{b+1} | (s^{2} − r^{2}) = (s + r)(s − r)

今、 r, s はともに奇だから mod4 において s ≡ r または s ≡ −r が成立する。

• s ≡ r のとき、 s+r ≡ 2 (mod 4) だから 2||(s+r)。従って 2^{b}|(s−r)、すなわち s ≡ r (mod 2^{b})。ここで 0 ≤ r, s < 2^{b} より s = r

• s ≡ −r のとき、同様にして s ≡ −r (mod 2^{b})。 0 ≤ r, s < 2^{b} より s = 2^{b} − r

2 奇数乗根

ここでは、 2 の冪を法とした Newton 法により、奇数 n の奇数乗根を求めることを考える。

なお、今回の目的には ℤ の上で考えれば十分であるが、 [1] の記述に合わせてまずは一般の単位的可換環における Newton 法を考えた。

Algorithm 2.1 (p 進逆数). inv_{p}(f, g_{0}, k)

R を単位的可換環とする。

入力 k ∈ ℕ, p ∈ R, および fg_{0} ≡ 1 (mod p) なる f, g_{0} ∈ R

出力 fg ≡ 1 (mod p^{k}) なる g ∈ R 1. r := ⌈log k⌉

2. for i = 1, ..., r, g_{i} := (2g_{i−1} − fg_{i−1}^{2}) mod p^{2^{i}}

3. g_{r} を返して終了。

Lemma 2.2. Algorithm 2.1 は正しく動作する。

Proof. r についての帰納法により示す。 r = 0 のときは入力の仮定より明らか。

今、ある r_{0} について成立していると仮定する。以下、 r = r_{0} + 1 の場合について示す。

仮定より p^{2^{r−1}} | (fg_{r−1} − 1)。従って p^{2^{r}} | (fg_{r−1} − 1)^{2}。つまり、

(fg_{r−1} − 1)^{2} = f^{2}g_{r−1^{2}} − 2fg_{r−1} + 1 ≡ 0 (mod p^{2^{r}})

従って、

fg_{r} = f(2g_{r−1} − fg_{r−1}^{2}) = 2fg_{r−1} − f^{2}g_{r−1}^{2} ≡ 1 (mod p^{2^{r}})

Corollary 2.3. R を単位的可換環、 k ∈ ℕ とする。このとき以下は同値である。

• f ∈ R が mod p^{k} で可逆

• f ∈ R が mod p で可逆

Proof. ⇒ は p | p^{k} より明らか。

⇐ は、 Algorithm 2.1 により mod p^{k} での逆元を作ることができるので成立する。

Lemma 2.4 (Netwon 法の 2 次収束性). R を単位的可換環とし、 m ∈ R, ϕ ∈ R[y] とする。 g ∈ R が

• ϕ(g) ≡ 0 (mod m)

• ϕ′(g) は mod m で可逆 (ただし ϕ′ は ϕ の形式的微分)。

を満たすとき、次の mod m^{2} における Netwon 法の漸化式によって h ∈ R を定義する。

h ≡ g − ϕ(g) ϕ′(g)^{−1} (mod m^{2})  (2)

このとき、次が成立する。

• h ≡ g (mod m)

• ϕ(h) ≡ 0 (mod m^{2})

• ϕ′(h) は mod m^{2} で可逆

Note 1. この Lemma を、最終的な目的である ℤ の上での mod2^{k} 上の Newton 法に当てはめて考えると、 Newton 法による近似を 1 回行うごとに近似値 p 進距離の意味で収束し、その収束の仕方は 2 次であるということを表している。

これは ℝ 上の Newton 法が絶対値距離の意味で 2 次収束することに丁度対応する。 Proof. Corollary 2.3 より ϕ′(g) は modm^{2} でも可逆である。従って h は well-defined.

m | m^{2} より (2) は mod m においても成立し、また ϕ(g) ≡ 0 (mod m) だから

h ≡ g − ϕ(g) ϕ′(g)^{−1} ≡ g (mod m)

これより主張の第 1 は示された。なお、これにより (h−g)^{2} = 0 (mod m^{2}) が言える。

次に、 ϕ(y) を g を中心に Taylor 展開して y = h を代入すると、ある ψ ∈ R[y] が存在して

ϕ(h) = ϕ(g) + ϕ′(g)(h − g) + ψ(h − g) · (h − g)^{2}
≡ ϕ(g) + ϕ′(g)(h − g) (mod m^{2}) (∵ m^{2} | (h − g)^{2})
≡ ϕ(g) + ϕ′(g) · (−ϕ(g) ϕ′(g)^{−1}) (mod m^{2}) (∵ h の定義)
≡ 0

以上で主張の第 2 が示された。

さて、仮定より ϕ′(g) は mod m で可逆。 g ≡ h (mod m) より ϕ′(h) も mod m で可逆。従って Corollary 2.3 により ϕ′(h) は mod m^{2} でも可逆。主張の第 3 も示された。

Algorithm 2.5 (p 進 Newton 法). poly root_{p}(ϕ, k, g_{0}, s_{0})

R を単位的可換環、 p ∈ R とする。

入力 • ϕ ∈ R[y] • k ∈ ℕ_{>0}

• ϕ(g_{0}) ≡ 0 (mod p)、かつ ϕ′(g_{0}) が mod p で可逆であるよ

うな g_{0} ∈ R
• ϕ′(g_{0}) の mod p における逆元 s_{0}

出力 ϕ(g) ≡ 0 (mod p^{k}) かつ g ≡ g_{0} (mod p) なる g ∈ R

1. r := ⌈log k⌉

2. for i = 1, ..., r − 1,

g_{i} := (g_{i−1} − ϕ(g_{i−1})s_{i−1}) mod p^{2^{i}}
s_{i} := (2s_{i−1} − ϕ′(g_{i})s_{i−1}^{2}) mod p^{2^{i}}

3. g := (g_{r−1} − ϕ(g_{r−1})s_{r−1}) mod p^{k} を返して終了。

Lemma 2.6. Algorithm 2.5 は正しく動作する。

Proof. g_{r} := (g_{r−1} − ϕ(g_{r−1})s_{r−1}) mod p^{2^{r}} とすると

g ≡ g_{r} (∵ 2^{r} ≥ k)

だから、

ϕ(g_{r}) ≡ 0 (mod p^{2^{r}})
g_{r} ≡ g (mod p)
s_{r} ≡ ϕ′(g_{r})^{−1} (mod p^{2^{r}})

を示せば十分。

r についての帰納法を用いる。 r = 0 のときには、入力についての仮定から明らか。ある i − 1 について成立しているとき、 i についても成立することを示す。帰納法の仮定より p^{2^{i−1}} は ϕ(g_{i−1}) および s_{i−1} − ϕ′(g_{i−1})^{−1} を割る。従って、 p^{2^{i}} はこれらの積 ϕ(g_{i−1}) (s_{i−1} − ϕ′(g_{i−1})^{−1}) を割る。これより、

g_{i} ≡ g_{i−1} − ϕ(g_{i−1})s_{i−1} ≡ g_{i−1} − ϕ(g_{i−1}) ϕ′(g_{i−1})^{−1} (mod p^{2^{i}})

今、 Lemma 2.4 において g = g_{i−1}, h = g_{i}, m = p^{2^{i−1}} とおけば、最初の 2 つの式は従う。

また、 ϕ(g_{i−1}) ≡ 0 (mod p^{2^{i−1}}) より g_{i} ≡ g_{i−1} (mod p^{2^{i−1}})。これより

ϕ′(g_{i})^{−1} ≡ ϕ′(g_{i−1})^{−1} ≡ s_{i−1} (mod p^{2^{i−1}})

すると、 s_{i} の漸化式は Algorithm 2.1 において l = 2, f = ϕ′(g_{i}), g_{0} = s_{i−1}, p = p^{2^{i−1}} とおいたものに等しい。従ってその出力 s_{i} は mod p^{2^{i}} での ϕ′(g_{i}) の逆数である。

以上で最後の式が示された。

Algorithm 2.7 (奇数の奇数乗根). odd root(a, n)

入力 a, n ∈ ℕ。但し、ふたつとも奇数。

出力 a = b^{n} なる b ∈ ℕ が存在すれば b を返す。存在しないときには 0 を返す。

1. f(y) := y^{n} − a ∈ ℕ[y] とする。

2. k を 2^{nk} > a なる最小の自然数とする。

3. b := poly root_{2}(f, k, 1, 1) とする。

4. b^{n} = a ならば b を、そうでなければ 0 を返す。

Theorem 2.8. Algorithm 2.7 は正しく動作する。

Proof. a は奇数なので f(1) = 1^{n} − a ≡ 0 (mod 2)。また、 n も奇数なので f′(1) = n · 1^{n−1} = 1 (mod 2)。従って、 f(1) は mod 2 において可逆で逆元は 1。

以上から、 (f, k, 1, 1) はpoly root_{2}(ϕ, k, g_{0}, s_{0}) の入力の条件を満たす。従って、 f(b) = b^{n} − a ≡ 0 (mod 2^{k})。

ここで、もし b_{0}^{n} = a なる b_{0} ∈ ℕ が存在したなら、 k の取り方より b_{0} < 2^{k}。 b_{0} が存在するなら b_{0} = b である。

従って b^{n} = a のとき b が求める根であり、そうでないとき根は存在しない。

3 一般の冪根

Algorithm 3.1. root(a, n)

入力 a, n ∈ ℕ。

出力 a = b^{n} なる b ∈ ℕ が存在すれば b を返す。存在しないときには 0 を返す。

1. 2^{k}||a なる k ∈ ℕ を求める。

2. n |̸ k ならば 0 を返して終了。そうでなければ a′ := a/2^{k} とする。 3. 2^{l}||n なる l ∈ ℕ および n′ := n/2^{l} を求める。

4. b_{0} := odd root(a′, n′)

5. b_{0} が 0 なら 0 を返して終了。 6. for i = 1, ..., l

b_{i} := b_{i−1}odd sqrt(b_{i−1}) を求め、 b_{i} が 0 なら 0 を返して終了。 7. b := 2^{k/n}b_{l} を返して終了。

Theorem 3.2. Algorithm 3.1 は正しく動作する。

Proof. 構成より明らか。

参考文献

[1] Joachim von zur Gathen and Jügen Gerhard, Modern Computer Algebra 2nd ed., 2003

[2] Daniel J. Bernstein, “DETECTING PERFECT POWERS IN ESSENTIALLY LINEAR TIME”, Mathematics of computation, volume 67, Number 223, 1998, http://cr.yp.to/papers/powersams.pdf