元祖ワシ的日記

数学

8N+1の素数について、もう一つ別の考え方を解説します。多分Tonelli–Shanksのアルゴリズムと同じ考えに基づくものと思われます。

$p - 1 = 2^{s} t$ (ただし $t$ は奇数)とおきます。すると任意の $x$ に対して
$(x^{t})^{2^{s}} = 1$
ですから $x^{t}$ は1の $2^{t}$ 乗根です。

例えば97を考えると
$96 = 2^{5} \cdot 3$
ですから $x^{3}$ は1の32乗根です。一般的に1の32乗根は32個あり、そのうち16個が32乗してはじめて1になる数です。ある数 $ω$ が32乗して初めて1になる数とすれば
$ω^{3}, ω^{5}, \dots, ω^{3} 1$ もまた32乗根してはじめて1になる数です。よって1つそのような数を見つければ他の数は自然と見つかることになります。

（余談ながらその逆数 $ω^{- 1}, ω^{- 3}, \dots, ω^{- 31}$ も然りです）

$ω$ を32乗して初めて1になる数（例えば42）としてその数を2乗、4乗としてこれを木の形にしてみます。（下図参照）

空白になっているところにも $2$ の冪乗根があるはずですがそれは何かわからないので空欄にしておきます。また平方根についてはaが平方根の1つなら-aもまた平方根ですので剰余を0から95ではなく-48から47までの間になるように書いています。木の葉のほうから辿れば

42 → 18 → 33 → 22 → -1

です。この中に $a^{3}$ があれば答えは簡単です。例えば $a$ が $47$ とすれば、 $a^{3} = 33$ ですから、1つ下の $18$ を使って
$a^{3} = 33 = 18^{2}$
これより両辺に $a$ をかけて
$a^{4} = 18^{2} a$
を得て
$(a^{2} 18^{- 1})^{2} = a$

が答えになります。 $18$ の逆数 ( $18 x = 1$ なる数)が出てきますがこれは普通に求めてもいいし、そもそも $18^{16 - 1} = 27$ が逆数なのでそれを利用しても簡単に求まります。
答えとしては $- 12$ が得られます。実際 $- 12^{2} = 47$ です。

そうではない場合（例えば $11$ ）を探す場合は次のようにします。 $11^{3} = - 27$ です。 $- 27$ を冪冪で累乗していくと

$\begin{array}{r} (- 27)^{2} = - 47 \\ (- 47)^{2} = - 22 \end{array}$
となり、ここで $- 22$ が出ます。 $- 22$ はツリーのルートのすぐ右側にあるので、この数はツリーの右側にあることがわかります。ところで $ω$ ですが次のような性質を持っています。

$ω^{2}$ を乗ずると2段目のノードに対して左右に移動する
$ω^{4}$ を乗ずると3段目のノードに対して左右に移動する
$\dots$

この性質を利用して

ω^{2} (= 18)

を42に乗じて(-20になる)そのノードを右側のツリーの同じ場所におきます。そしてそこからまた冪冪でルートに戻っていきます。
このルートの中に求めるノードがあればそれが答えです。残念ながら今回もみつからないので

ω^{4}

を乗じます。そうすると-27が無事見つかりました。これから答えが求まります。

最後に32乗してはじめて1になる数の見つけかたですが、これは平方非剰余な数を3乗すれば求めるものになります。平方非剰余な数は全体の半数ですからランダムに選んで

(p - 1) / 2

乗して判定することができます。

この方法は運が悪いと沢山計算をする必要がありますが木の高さは

s

ですから最悪でも

s^{2}

くらいのオーダーの計算量になります。
一方葉は

2^{s}

のオーダでこれを全部計算するのはsが大きくなるととんでもない数になります。

s

が小さいときは非効率ですが大きくなるにつれて優位性が増すと思われます。

mod Pにおける平方根その2

2023年10月25日(水)

一つ前のエントリで8N+1型以外の素数についての平方根の計算方法を解説しました。8N+1については同じような考えで求めようとしてもなかなかうまくいきません。

a^{n} = \pm a （ た だ し n は 偶 数 ）

の形になかなか持ち込めないのがその要因です。今まで考えきた演算は

p

での剰余をもって演算するもので代数学的には

F_{p}

で演算と呼ばれるものです。

F_{p}

は

p

個の元からなる有限の集合で、その元同士に加減乗除が定義されているものです。この空間で演算をしている限りこの問題をクリアすのはどうも不可能なようです。そこで発想をちょっと変えて

F_{p}

ではなく

F_{q}

で考えることにします。

F_{q}

とは

F_{p}

の世界で既約な方程式の根を追加した体（加減乗除がうまく定義された集合）です。

F_{p}

は

p

個の元からなる体ですが、

F_{q}

は

q

個の元からなるので

F_{q}

と表現します。今回はちなみに

q = p^{2}

なので、

F_{p^{2}}

と記述するのが正確なのかもしれませんが、とりあえず

F_{q}

と表現しておきます。なんか難しいこと言ってますが発想としては簡単で

F_{p}

での平方根が存在しない数の平方根があると仮定してそれを追加したもの・・とゆるく考えておけばよいかと思います。

例えば有理数においても

2

の平方根は存在しませんが、仮にそれを

\sqrt{2}

と書くとすれば

x + y \sqrt{2}

という数の集合を考えることができてその集合に対して加減乗除が定義できます。例えば上記の数は二乗することが可能で二乗した結果は

(x^{2} + 2 y^{2}) + (2 x y) \sqrt{2}

であってその結果もまた

x + y \sqrt{2}

の形に書けることがわかります。詳細は書きませんが割る場合も同様です。つまり

x + y \sqrt{2}

の形の集合を考えれば全ての加減乗除はその内部で閉じておりまた完結していることになります。

F_{q}

もそれと同じ原理を用います。

F_{p}

から平方非剰余の数を

T

1つ選びその平方根があると仮定してそれを

\sqrt{T}

と表すことにし、この数を

F_{p}

に追加します。この集合に対して加減乗除が成立するためには

x + y \sqrt{T}

と表すことができる数全てに対して加減乗除が閉じていることを示す必要がありますが証明は割愛します。xの選び方はp通りyの選び方はp通りですからこの体は

p^{2}

個の元からなることになります。

q = p^{2}

とします。するとこの

F_{q}

に対してもフェルマーの小定理が成立して

x^{q} = x

が成立することが知られています。つまり

F_{q}

では

q

乗すると元に戻ります。ところで

F_{p}

では

x^{p} = x

が成立しました。

F_{p}

は

F_{q}

に含まれていると考えられますから、

F_{q}

においても

F_{p}

に属する元ははその位置を変えません（固定される）。しかし

F_{p}

に含まれない数はそうではなく、別な数に移動します。

この移動先は共役元になることが知られています。つまり

(x + y \sqrt{T})^{p} = (x - y \sqrt{T})

です。となれば

F_{q}

では任意の元を

p + 1

乗すると

(x + y \sqrt{T})^{p + 1} = (x + y \sqrt{T}) (x - y \sqrt{T}) = x^{2} - y^{2} T

となりその数がなんであり

F_{p}

に属することになります。よって

x^{2} - y^{2} T = a

となるようにうまく

x, y

を選ぶことができれば

p + 1

は偶数ですから

(x + y \sqrt{T})^{\frac{p + 1}{2}}

がその平方根になります。

仮に

y

を1として探してみます。このとき

T = x^{2} - a

が成立するので

x

を適当に変えてみてその値から

a

を引いたもとのが非平方剰余である数を

T

として選べば良いことになります。

例)

p = 41

とし

8

の平方根を考えます。

x

を色々変えて見ると、

5^{2} - 8 = 17

は非平方剰余であることがわかります。よって

F_{1681}

で考えることにより

(5 + \sqrt{17})^{21}

が答えになります。

実際計算をしてみると

\begin{array}{r} (5 + \sqrt{17})^{2} = (1 + 10 \sqrt{17}) \\ (5 + \sqrt{17})^{4} = (20 + 20 \sqrt{17}) \\ (5 + \sqrt{17})^{8} = (25 + 21 \sqrt{17}) \\ (5 + \sqrt{17})^{16} = (4 + 25 \sqrt{17}) \end{array}

ですので

(5 + \sqrt{17})^{16} (5 + \sqrt{17})^{4} (5 + \sqrt{17})^{1} = 34

となります。実際

34^2=8\pmod{41}

です。

余談）

F_{p}

のような体を有限体（要素の数が有限なので）と言いますがその要素の数（位数とよぶ）は必ず

p

の冪であり、また

p

の冪の有限体は必ず存在することがわかっています。

mod Pにおける平方根

2023年10月23日(月)

x^{2} = a (\mod p)

を求めるアルゴリズムとその原理の紹介です。アルゴリズムについては
mod pでの平方根
に書いてあるものと基本的に同じです。
任意の素数

p

に対して

a^{\frac{p - 1}{2}} = \pm 1 (\mod p)

が成立しその符号は

a

が平方剰余かどうかで決まります。今回二乗して

a

になる数を探すので

a

は必ず平方剰余です。つまり上式の値は1です。この式の両辺にさらに

a

を乗ずると

a^{\frac{p + 1}{2}} = a (\mod p)

よって

\frac{p + 1}{2}

が偶数なら

(a^{\frac{p + 1}{4}})^{2} = a (\mod p)

よって

a^{\frac{p + 1}{4}}

が解になります。これは

p

が

4 N + 3

型の素数のときに使えます。簡単ですね。

例)

p = 31

として、2の平方根を求めてみる。

2^{15} = 1 (\mod p)

だから両辺に2を乗じて

2^{16} = 2 (\mod p)

を得る。よって

2^{8}

が平方根になる。実際に計算してみると

2^{8} = 8 (\mod p)

であるから8が2の平方根である。実際

8^{2} = 2 (\mod p)

である。

そうではないとき（つまり

p

が

4 N + 1

型の素数のとき）は次のように考えます。

a^{\frac{p - 1}{4}} = \pm 1 (\mod p)

です。ここから両辺に

a

を乗ずると

a^{\frac{p + 3}{4}} = \pm a (\mod p)

よって

p

が

8 N + 5

型の素数ならば

\pm (a^{\frac{p + 3}{8}})^{2} = a (\mod p)

符号が正の場合は

a^{\frac{p + 3}{8}}

が解になります。

負の場合は

4 N + 1

型の素数は-1が平方剰余であるのであらかじめ

- 1

の根号(

x^{2}

=-1となる数。仮に

i

と記述する）を求めておけば

i a^{\frac{p + 3}{8}}

が解になります。

i

は平方非剰余の数を

(p - 1) / 4

すれば見つかります。

1 \dots p - 1

なる数のうち半数が平方剰余で半数が平方非剰余ですから2から順番に探索していけば高確率ですぐ見つかりますが

8 N + 5

型については2が常に平方非剰余ですので

2^{(p - 1) / 4}

をあらかじめ計算しておけば良いことになります。

例)

p = 101

として

5

の平方根を求める。

5^{(101 + 3) / 8} = 56 (\mod p)

である。よって56が平方根の可能性がある。実際計算をしてみると

56^{2} = 5 (\mod p)

であるから56が5の平方根である。

同じく

p = 101

として

6

の平方根を求める。

6^{(101 + 3) / 8} = 14 (\mod p)

である。よって14が平方根の可能性がある。実際計算をしてみると

14^{2} = 95 = - 6 (\mod p)

である。そこで二乗して-1になる数を探す。2からチェックをしていくと

2^{25} = 10 (\mod p)

である。実際

10^{2} = - 1 (\mod p)

だから

10

は-1の平方根。これより

14 \times 10 = 39 (\mod p)

を得、39が6の平方根であることがわかる。

最後に残ったケース、

p

が

8 N + 1

型の素数についてはちょっとややこしいので次のエントリーに書きます。

ピタゴラスの定理の証明

2021年10月09日(土)

いろいろあるけれどこの証明が一番秀逸だと思います（それぞれの破片が合同であることは簡単にわかる）。
任意の正方形は5つの破片に切って分けて新しい二つの任意の正方形を作ることができるんですよね。その逆も然り。

有限体の既約多項式の個数を求める

2018年10月25日(木)

有限体の各次数における既約多項式の総数というのをここ暫く考えていました。まぁいろいろあるんですが、結論から言うと次の補題を証明した瞬間ほぼ終わりです。

$p$ を素数とし、 $q = p^{n}$ とする。有限体 $F_{p}$ 上の多項式 $X^{q} - X$ は $d$ を $n$ の約数とすると $d$ 次の約数既約多項式全てを因子に持つ。

証明はそんなに難しくないのでまたの機会にでもここに書きます。とりあえず、例を上げます（例が多いブログなもので・・・）

例1)
$F_{2}$ 上の $X^{4} - X$ の因数分解を考えます。 $n = 2$ です。よって1次式と2次式の分解できます。実際計算してみると

$\begin{array}{r} X^{4} - X = X (X + 1) (X^{2} + X + 1) \end{array}$

となります。この式はこれ以上分解するのは不可能です。

例2)
$F_{2}$ 上の $X^{8} - X$ の因数分解を考えます。 $n = 3$ です。
この式は3の約数である1次と3次の既約多項式を因子に持ちます。実際計算してみると

$\begin{array}{rcl} X^{8} - X & = & X (X - 1) (X^{6} + X^{5} + \dots + 1) \\ = & X (X - 1) (X^{3} + X + 1) (X^{3} + X^{2} + 1) \end{array}$

例3)
$F_{2}$ における $X^{16} - X$ の因数分解を考えます。 $n = 4$ です。
よって $n$ の約数である既約4次式、2次式、1次式を因子にもちます。実際計算してみると、

$\begin{array}{rcl} X^{16} - X & = & X (X - 1) (X^{2} + X + 1) (X^{12} + X^{11} + \dots + 1) \\ = & X (X - 1) (X^{2} + X + 1) (X^{4} + X + 1) (X^{4} + X^{3} + 1) (X^{4} + X^{3} + X^{2} + X + 1) \end{array}$

以上なんとなく感覚がつかめていただいたでしょうか？２の冪以外の例はまた別の機会にここに書きます。

さて、ここから $F_{q}$ における $n$ 次の既約多項式の個数を求めます。

$X^{q} - X$ において $n$ 次の既約多項式の根を全て掛け合わせたものの次数を $ν (n)$ とします。先ほどの例で言えば

$\begin{array}{rcl} ν (1) & = & 2 \\ ν (2) & = & 2 \\ ν (3) & = & 6 \\ ν (4) & = & 12 \end{array}$
です。この先ですが

$\begin{array}{rcl} ν (5) & = & 30 \\ ν (6) & = & 54 \end{array}$

と続きます。

さて、 $F_{q}$ には $n$ の約数である $d$ 次の既約多項式がすべて存在します。それらの次数を足し合わせれば当然 $q$ になります。よって、

$\begin{array}{r} \sum_{d | n} ν (d) = q = p^{n} \end{array}$

が成立します。ここからメビウスの反転公式を使って

$\begin{array}{r} ν (d) = \sum_{d | n} μ (\frac{n}{d}) p^{d} \end{array}$

となります。 $ν (d) / n$ が $n$ 次式の個数になるので

$\begin{array}{r} \frac{1}{n} \sum_{d | n} μ (\frac{n}{d}) p^{d} \end{array}$

が求める個数になります。

オイラーのφ関数

2018年10月03日(水)

wikipediaより

オイラーのトーシェント関数（オイラーのトーシェントかんすう、英: Euler's totient function）は各正の整数 n に対して、1 から n までの自然数のうち n と互いに素なものの個数を φ(n) として与えることによって定まる数論的関数 φ である。慣例的に φ(n) と表記されるため、オイラーの φ 関数（ファイかんすう、phi function）とも呼ばれる。また、簡略的にオイラーの関数と呼ぶこともある。

計算方法概略

簡単にするためまず $n$ の素因数分解を $p_{1} p_{2} p_{3} \dots p_{n}$ とし因子に平方数を含まないとします。 (つまり素数 $p_{1}, p_{2}, p_{3}, \dots$ の羃は1)

$1$ から $n$ のうち $p_{1}$ の倍数の数が $n / p_{1}$ 個あり、 $p_{2}$ の倍数が $n / p_{2}$ あり……ということでこれらの数を $n$ から引きます。しかし、これでは $p_{1} p_{2}$ など2つの素数の積の数を2回引いてしまうのでそれらを足します。しかし、これでは $p_{1} p_{2} p_{3}$ のような3つの素数の積になってる数を足しすぎてしまうのでそれらをまた引きます……と考えていけば……

\begin{array}{rcl} ϕ (n) = n & - & (n / p_{1} + n / p_{2} + \dots + n / p_{n}) \\ + & (n / p_{1} p_{2} + n / p_{1} p_{3} + \dots + n / p_{n - 1} p_{n}) \\ - & (n / p_{1} p_{2} p_{3} + n / p_{1} p_{2} p_{4} + \dots + n / p_{n - 2} p_{n - 1} p_{n}) \\ + & \dots \end{array}

この式の分母の素数の積は

n

の全ての約数を渡ることは明かです。

n

の約数

d

を素因数分解したとき、それが偶数個なら

n / d

を足し、奇数個なら

n / d

を引いていくという流れになります。なお、上記の式は以下のように書けます。

\begin{array}{r} ϕ (n) = n (1 - 1 / p_{1}) (1 - 1 / p_{2}) (1 - 1 / p_{3}) \dots (1 - 1 / p_{n}) \end{array}

例

\begin{array}{rc} ϕ (30) & = 30 - (30 / 2 + 30 / 3 + 30 / 5) + (30 / 6) + (30 / 10) + (30 / 15) - 30 / 30 = 8 \end{array}

平方数を含む場合ですが例えば $12$ のときを考えれば $2$ の倍数を除去したときに12の因数である $4$ の倍数は既に除去されています。つまり、平方因子をもつ約数は考慮しなくてもよいのです。（つまり、素因数が何種類あるか？が重要）これはそのまま一般に拡張出来ます。実際上記の式は $n$ の素因数分解を $p_{1}^{e_{1}} p_{2}^{e_{2}} p_{3}^{e_{3}} \dots p_{n}^{e_{n}}$ と分解される場合でも成立します。

$n = p_{1}^{e_{1}} p_{2}^{e_{2}} p_{3}^{e_{3}} \dots p_{n}^{e_{n}}$ の素因数をそれぞれの項に配分していけば

\begin{array}{rcl} ϕ (n) & = & p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{n}^{e_{n}} (1 - 1 / p_{1}) (1 - 1 / p_{2}) (1 - 1 / p_{3}) \dots (1 - 1 / p_{n}) \\ = & (p_{1}^{e_{1}} - p_{1}^{e_{1} - 1}) (p_{2}^{e_{2}} - p_{2}^{e_{2} - 1}) \dots (p_{n}^{e_{n}} - p_{n}^{e_{n} - 1}) \end{array}

なお、上記の式はメビウス関数を使えば $\begin{array}{r} ϕ (n) = \sum_{d | n} μ (d) \frac{n}{d} \end{array}$ とも表わすことができます。メビウス関数 $μ (n)$ は

$n$ が平方因数を含む場合は $μ (n) = 0$
$n$ が因数を偶数個含む場合は $μ (n) = 1$
$n$ が因数を奇数個含む場合は $μ (n) = - 1$

という関数です。

ここからメビウスの反転公式を使って

\begin{array}{r} \sum_{d | n} ϕ (d) = n \end{array}

とか即座に得られるのがまた味わい深いですの。

以上Mathjaxのリハビリでした

4n+1の素数を平方の和にする（その2）

2016年06月02日(木)

相当前にエントリに書いた $4 n + 1$ の素数を平方の和にするアルゴリズムですがガウス整数を使ったもっとスマートな解法を紹介します。

まず前回同様 $p$ を $4 n + 1$ の素数として $A^{2} + 1 = 0 (\mod p)$ なる $A$ を求めます。

$A^{2} + 1 = k p$ です。

左辺はガウス整数を使うとさらに因数分解できて $(A + i) (A - i) = k p$ となります。

ここでガウス整数は通常の整数と同様、素因数分解等素数の性質があることを踏まえて等式を見てみます。

$p$ はあきらかに $A + i$ および $A - i$ を割きりません。ということは $p$ はガウス整数の世界ではさらなる素数に分解できることを意味します。すなわち最大公約数 $(A + i, p)$ は1ではなく、 $x + i y$ の形をしたガウス整数となります。

$(A + i, p) = x + i y$ ならば共役の関係から $(A - i, p) = x - i y$ がまた成立します。一方 $(x + i y) (x - i y)$ を考えるとこれは有理整数 $x^{2} + y^{2}$ となりこれは $p$ を割り切らないといけませんが、 $p$ は素数ですから結局これは $p$ に等しく $p = x^{2} + y^{2}$ となります。

つまり $p$ と $A + i$ の最大公約数を求めればそこから解は自動的に求まることになります。

最大公約数はガウス整数の世界でもユークリッドの互除法で簡単に求めることができます。

例として、素数 $p = 120710677$ を二つの和にしてみます

$46505545^{2} + 1^{2} = 17916938 \times 120710677$

ですから最初は $46505545 + i$ と $120710677$ の最大公約数を求めればよいことになります。

$A_{0} = 46505545 + i B_{0} = 120710677$ とします。

ノルムを比較すると $| A_{0} | < | B_{0} |$ で $A_{0} = 3 * | B_{0} | + . . .$ ですから最初の計算では $A_{1} = A_{0}, B_{1} = B_{0} - 3 A_{0}$ とすればよいことがわかります。実際計算してみると $A_{1} = 46505545 + i B_{1} = - 18805958 - 3 i$ となります。以下同様にして計算していくと

$\begin{aligned} A_{2} & = & 8893629 - 5 i, B_{2} & = & - 18805958 - 3 i \\ A_{3} & = & 8893629 - 5 i, B_{3} & = & - 1018700 - 13 i \\ A_{4} & = & - 274671 - 122 i, B_{4} & = & - 1018700 - 13 i \\ A_{5} & = & - 274671 - 122 i, B_{5} & = & 79984 + 475 i \\ A_{6} & = & - 34719 + 1303 i, B_{6} & = & 79984 + 475 i \\ A_{7} & = & - 34719 + 1303 i, B_{7} & = & 10546 + 3081 i \end{aligned}$ ここで $B_{7}$ が求める答えになります。実際 $10546^{2} + 3081^{2} = 120710677$ です

注意

ユークリッドの互除法ではノルムの大きいほうをノルムの小さいほうで割ってその余りに置き換えるという手順を踏むのですが、それは以下のようにして求めます。

$a + i b$ を $c + i d$ で割る場合は $\frac{a + i b}{c + i d} = \frac{(a + i b) (c - i d)}{c^{2} + d^{2}} = \frac{a c + b d}{c^{2} + d^{2}} + \frac{b c - a d}{c^{2} + d^{2}} i$ ここで、有理数 $\frac{a c + b d}{c^{2} + d^{2}}, \frac{b c - a d}{c^{2} + d^{2}}$ に最も近い整数を $n$ , $m$ とすれば $(a + i b) = (n + i m) (c + i d) + (r + i s)$ と書いたときに、 $r + i s$ のノルムは $c + i d$ より小さくなります。よって $r + i s$ を余りとみなして計算を進めていくことができます。

別の考察

この例では $(A + i, p)$ を考えましたが、 $(A + i, k)$ を考えても同様に計算をすることができることがわかります。

この場合最大公約数を求めなくても以下のように計算をすることができます。

$a^{2} + b^{2} = 0 (\mod k)$ であることを考えると $a^{'} = a (\mod k), b^{'} = b (\mod k)$ とおけば $a^{' 2} + b^{' 2} = 0 (\mod k)$ もまた成立します。つまり $a^{' 2} + b^{' 2}$ は $k$ を割りきります。つまり $\frac{(a + i b) (a - i b)}{(a^{'} + i b^{'}) (a^{'} - i b^{'})} = \frac{k}{a^{' 2} + b^{' 2}} p = k^{'} p$ が成立します。右辺は整数ですから左辺は共役なガウス整数の積にならなければなりません。よって $\frac{a + i b}{a^{'} + i b^{'}} または \frac{a + i b}{a^{'} - i b^{'}}$ のどちらかがガウス整数になります。ここで $\begin{aligned} - k / 2 & < & a^{'} & < & k / 2 \\ - k / 2 & < & b^{'} & < & k / 2 \end{aligned}$ なるように a', b'を選べば kより小さい k'が見つかることになります。この手順を繰替えせば kより始めていつかは1になるので求める解を見付けることができます。

これが前回解説したアルゴリズムと同じものになります。

さらりと流した部分の補足

有理整数がガウス整数の積で表わされる必要条件は共役の因子を含むことである。

ガウス整数をそれぞれ $a + i b$ と $c + i d$ とする。 $c \neq 0$ , $d \neq 0$ , $(a, b) = 1, (c, d) = 1$ と仮定して問題ない。なぜならもし $(a, b) = k > 1$ ならば $a^{'} = a / k, b^{'} = b / k$ として $k (a^{'} + i b^{'}) (c + i d)$ を考えればよいからである。 $(a + i b) (c + i d) = (a c - b d) + i (a d + b c)$ が有理整数なのだから $a d + b c = 0$ すなわち $a d = - b c$ が成立する。よって、 $a$ と $b$ と互いに素だから $c$ が $d$ を割り切りかつ $d$ が $c$ を割きらなければならないが、これは $c = d$ または $c = - d$ を意味する。 $c = d$ とすれば $a = - b$ であり $c = - d$ とすれば $a = b$ である。いずれにしても共役の因子を含まなくてはならない。

有理整数が共役の数の積で表わされているのなら、その数はガウス整数でなければならない。

$a / b$ および $c / d$ を考える。 $(a, b) = 1, (c, d) = 1$ と仮定して問題ない $(\frac{a}{b} + i \frac{c}{d}) (\frac{a}{b} - i \frac{c}{d}) = \frac{a^{2} c^{2}}{b^{2} d^{2}}$ から $b^{2} d^{2} = 1$ これは $b = \pm 1, d = \pm 1$ を意味する。

x^2 = a (mod P)を効率よく解く

2014年11月14日(金)

有限体Fp上で

x^2 = a

を解くことを考えます。根があるかないかは平方剰余の相互法則

x^2 = aが Fp根を持つ
<=>
(a/p) = 1 (ルジャンドルの記号)
<=>
a^(p-1)/2 = 1

で簡単に分かるのですが具体的にxが何であるかを求めるにはどうしたらよいのでしょうか？

Fpは有限群なので全ての元について根かどうかを解けばよいのですが、この手法はpが大きくなると破綻するのは自明です。そこで、ここでは別のアプローチを紹介します。

以下 aはFpで平方剰余であると仮定しておきます。また実数の世界にあやかって、x^2=aなるxを√aと表すことにします。（このようなxは2つ存在しもう一方は-√aです）。

pが4n+3型の素数のとき

pが4n+3ならば話は簡単です。

aは平方剰余なので

a^(p-1)/2 = 1

です。この両辺にaをさらに掛ければ

a^(p+1)/2 = a

となります。しかし、(p+1)/2は偶数ですから

a^(p+1)/4 = √a

ゆえに a^(p+1)/4が根(のうちの1つ)です。

pが4n+1型の素数のとき

この場合(p-1)/2が偶数のため(p+1)/2が奇数となり上の手法は使うことができません。ならば(p-1)が奇数になるまで 2で割るのはどうでしょうか？すなわち

p-1 = 2^k * s

とし、a^s乗を考えるのです。このa^s はあと2^k乗すれば 1になるのですから1の2^k乗根です。このa^sは原始的かどうか（すなわち 2^k乗根して始めて1になるかどうか）はわかりません。しかし仮に１つ原始2^k乗根を知っているとすれば全ての2^k乗根は

1, r, r^2, r^3, ..., r^(2^k-1)

とかけます。このようなrはこちらの手法で試行錯誤的に（だが簡単に）見つけることができます。さらに aは平方剰余だということがわかっているので実際は偶数番目だけのどれかであり、

a^s  = r^2n

と書けます。このnが何かは今はわかりません。（この手法では最後までこのnが何かはわかりません）。しかし、nが何であるかわからなくても r^2n * r^2m=1となるようなmを見つけることができます。それには次の性質を利用します。

x, y が原始N乗根ならば x * y は原始N/2乗根である。

つまり原始128乗根どうしを掛け合わせると原始64乗根になるということです。ある数が原始何乗根かどうかはその数を自乗していき-1になる冪を調べればわかります。以下例で説明したほうがわかりやすいと思いますので例で解説します。

例

p=769 , a=8として x^2 = a を解くとします。p-1=768 = 3 * 2^8 ですからF769には原始256乗根が存在し、試行錯誤法で計算するとr=7であることがわかります。

a^3 = 8^3 = 512

です。512は

512^64 = -1

ですから、原始128乗根の1つ、すなわち

1, 7^2, 7^4, ... 7^254

のうちのどれかです。

そこで原始128乗根である 7^2 = 49 をかけることにより原始64乗根（もしくはそれ以上）にすることができます。実際かけてみると

8^3 * 7^2 = 480

となり480は

480^32 = -1

ですから、原始64乗根です。そこで原始64乗根である 7^4 を両辺にかけます

8^3 * 7^2 * 7^4 = 518

518は同様の計算で原始32乗根ですから 7^8を両辺にかけます。

8^3 * 7^2 * 7^4 * 7^8 = 729

729は原始8乗根です（原始１６乗根をすっとばして2段階あがった）ので、両辺に7^32をかけます

8^3 * 7^2 * 7^4 * 7^8 * 7^32 = 707

707は原始4乗根ですから両辺に7^64をかけます。

8^3 * 7^2 * 7^4 * 7^8 * 7^32 * 7^64 = 1

ここで始めて1となりました。両辺に8をかけると

8 * 8^3 * 7^2 * 7^4 * 7^8 * 7^32 * 7^64 = 8

となり左辺の指数はすべて偶数です。故に

8^2 * 7 * 7^2 * 7^4 * 7^16 * 7^32 = √8

となります。左辺を計算してみると503になります。たしかに

503^2 = 8

です。