整数論と代数の初歩

整数論と代数の初歩
廣瀬勝一
廣瀬
整数論と代数の初歩
1 / 34
準備
def
整数の集合 Z = {. . . , −2, −1, 0, 1, 2, . . .}
最大公約数と最小公倍数
gcd(a, b) は a, b ∈ Z − {0} の最大公約数を表す．
gcd(a, b) = 1 のとき，a, b は互いに素であるという．
lcm(a, b) は a, b ∈ Z − {0} の最小公倍数を表す．
合同
a, b を整数とし，n を正整数とする．n が a − b を割り切るとき，a は n
を法として b と合同であると言う．これは以下のように表記される．
a ≡ b (mod n)
注意 a mod n は a を n で割ったときの剰余を表す二項演算
• 13 ≡ 4 (mod 9)
• 13 mod 9 = 4
廣瀬
整数論と代数の初歩
2 / 34
ユークリッドの互除法
与えられた二つの正整数 a0 , a1 の最大公約数を計算するアルゴリズム
以下の一連の除算を行う（a0 > a1 が仮定されている）
a0 = a1 q1 + a2
a1 = a2 q2 + a3
..
.
ak−2 = ak−1 qk−1 + ak
ak−1 = ak qk
a0 , a1 , . . . , ak について
gcd(a0 , a1 ) = · · · = gcd(ak−1 , ak ) = ak
廣瀬
整数論と代数の初歩
3 / 34
拡張されたユークリッドの互除法
α0 , α1 , . . . , αk と β0 , β1 , . . . , βk を以下のように定義する
α0 = 1
β0 = 0
α1 = 0
β1 = 1
αj = αj−2 − qj−1 αj−1
βj = βj−2 − qj−1 βj−1
このとき，αj a0 + βj a1 = aj が成立するので，
αk a0 + βk a1 = ak = gcd(a0 , a1 )
廣瀬
整数論と代数の初歩
4 / 34
例
a0 = 770, a1 = 336
α0 = 1
β0 = 0
α1 = 0
β1 = 1
770 = 336 × 2 + 98
α2 = 1
β2 = −2
336 = 98 × 3 + 42
α3 = −3
β3 = 7
α4 = 7
β4 = −16
98 = 42 × 2 + 14
42 = 14 × 3
7 × 770 + (−16) × 336 = 14
廣瀬
整数論と代数の初歩
5 / 34
孫子定理 (Chinese Remainder Theorem) (1/2)
正整数 n1 , n2 , . . . , nk はどの二つも互いに素であるとし，N =
する．このとき，整数 c1 , c2 , . . . , ck について


 x ≡ c1 (mod n1 )

x ≡ c2 (mod n2 )
···



x ≡ ck (mod nk )
∏k
i=1 ni
と
は {0, 1, . . . , N − 1} に唯一の解
x=
k
∑
ci Ni yi mod N
i=1
を持つ．ここで，1 ≤ i ≤ k について
Ni = N/ni ,
yi = Ni −1 mod ni
である．
廣瀬
整数論と代数の初歩
6 / 34
例

 x ≡ 2 (mod 7)
x ≡ 6 (mod 8)

x ≡ 7 (mod 11)
について
N = 7 × 8 × 11 = 616
であり
N1 = 88 ,
y1 = 88−1 mod 7 = 4−1 mod 7 = 2
N2 = 77 ,
y2 = 77−1 mod 8 = 5−1 mod 8 = 5
N3 = 56 ,
y3 = 56−1 mod 11 = 1−1 mod 11 = 1
したがって
x=
3
∑
ci Ni yi mod N = 590
i=1
廣瀬
整数論と代数の初歩
7 / 34
オイラー関数 (Euler Totient Function)
整数 n ≥ 1 に対し，オイラー関数は以下のように定義される．
def
ϕ(n) = |{x | x ∈ Z ∧ 1 ≤ x ≤ n ∧ gcd(x, n) = 1}|
Theorem 1
n の素因数分解を n = pe11 p2e2 · · · pekk とすると
)(
)
(
)
(
1
1
1
ϕ(n) = n 1 −
1−
··· 1 −
p1
p2
pk
表記法
• Zn = {0, 1, . . . , n − 1}
• Z∗n = {x | x ∈ Zn ∧ gcd(x, n) = 1}
注意 n ≥ 2 について，ϕ(n) = |Z∗n |
廣瀬
整数論と代数の初歩
8 / 34
例
n = 60 = 22 × 3 × 5
)(
)(
)
(
1
1
1
ϕ(60) = 60 1 −
1−
1−
2
3
5
(
(
) (
)
)
1 1 1
1
1
1
1
= 60 1 −
+ +
+
+
+
−
2 3 5
2×3 2×5 3×5
2×3×5
2’s multiple
3’s multiple
廣瀬
5’s multiple
整数論と代数の初歩
9 / 34
オイラーの定理
Theorem 2
a, n を正整数とする．
gcd(a, n) = 1 ⇒ aϕ(n) ≡ 1
(mod n)
証明関数 f : Z∗n → Z∗n を f (x) = ax mod n と定義する．gcd(a, n) = 1
ならば，a は Z∗n に逆元を持つので，f は 1 対 1 関数である．
Z∗n = {b1 , b2 , . . . , bϕ(n) } と表記すると，
∏
ϕ(n)
i=1
∏
bi ≡
i=1
∏
ϕ(n)
ϕ(n)
(abi ) ≡ a
ϕ(n)
bi
(mod n)
i=1
であり，これより aϕ(n) ≡ 1 (mod n) であることが導かれる．
廣瀬
整数論と代数の初歩
10 / 34
フェルマーの小定理 (Fermat’s Little Theorem)
Corollary 3
a, p を正整数とする．p が素数でありかつ gcd(a, p) = 1 ならば，
ap−1 ≡ 1
(mod p)
証明 ϕ(p) = p − 1 だから，オイラーの定理より明らか．
廣瀬
整数論と代数の初歩
11 / 34
群 (Group)
以下の条件が満たされるとき，G は演算 ◦ に関して群をなすと言う．
• ◦ は閉じている．即ち，すべての a, b ∈ G について a ◦ b ∈ G
• ◦ は結合則を満たす．即ち，すべての a, b, c ∈ G について
(a ◦ b) ◦ c = a ◦ (b ◦ c)
• すべての a ∈ G について a ◦ I = I ◦ a = a を満たす I ∈ G が存在す
る．I は単位元 (identity) と呼ばれる．
• すべての a ∈ G について，a ◦ a−1 = a−1 ◦ a = I を満たす a−1 ∈ G
が存在する．a−1 は a の逆元 (inverse) と呼ばれる．
演算 ◦ が加法のとき，G は加法群 (additive group) と呼ばれる．
演算 ◦ が乗法のとき，G は乗法群 (multiplicative group) と呼ばれる．
廣瀬
整数論と代数の初歩
12 / 34
例1
Zn は n を法とする加法に関して群をなす．
• 演算は閉じている．
• 結合則を満たす．
• 単位元は 0 である．
• すべての a ∈ Zn について，a の逆元は −a(= n − a) である．
廣瀬
整数論と代数の初歩
13 / 34
例2
Z∗n は n を法とする乗法に関して群をなす．
• 演算は閉じている．
• 結合則を満たす．
• 単位元は 1 である．
• すべての a ∈ Z∗n について，逆元 a−1 ∈ Z∗n が存在する．
拡張ユークリッドの互除法より α a + β n = 1 を満たす整数 α, β が存在し
αa ≡ 1
(mod n)
である．したがって，a−1 = α mod n である．
例 Z∗21 = {1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20}
−10 × 2 + 1 × 21 = 1
したがって
廣瀬
2−1 ≡ −10 ≡ 11 (mod 21)
整数論と代数の初歩
14 / 34
Z∗21 の乗算表
1
2
4
5
8
10
11
13
16
17
19
20
1
1
2
4
5
8
10
11
13
16
17
19
20
廣瀬
2
2
4
8
10
16
20
1
5
11
13
17
19
4
4
8
16
20
11
19
2
10
1
5
13
17
5
5
10
20
4
19
8
13
2
17
1
11
16
8
8
16
11
19
1
17
4
20
2
10
5
13
10
10
20
19
8
17
16
5
4
13
2
1
11
11
11
1
2
13
4
5
16
17
8
19
20
10
整数論と代数の初歩
13
13
5
10
2
20
4
17
1
19
11
16
8
16
16
11
1
17
2
13
8
19
4
20
10
5
17
17
13
5
1
10
2
19
11
20
16
8
4
19
19
17
13
11
5
1
20
16
10
8
4
2
20
20
19
17
16
13
11
10
8
5
4
2
1
15 / 34
幾つかの性質
G を有限の (乗法) 群とする．
定義 G の要素の個数を G の位数 (order) と言う．
定義 a ∈ G について，am = 1 を満たす最小の正整数 m を a の位数
(order) と言う．
Theorem 4
G の位数を n とする．すべての a ∈ G について a の位数は n の約数で
ある．
Corollary 5
G の位数を n とする．すべての a ∈ G について an = 1 である．
オイラーの定理は Cor. 5 より導かれる．
廣瀬
整数論と代数の初歩
16 / 34
Th. 4 の証明
a ∈ G の位数を k とする．A = {a1 , a2 , . . . , ak } は G の部分群である．
bi ̸∈ A ∪ b1 A ∪ · · · ∪ bi−1 A である G の要素が存在する限り，以下の集合
を構成する．
b1 A = {b1 a1 , b1 a2 , . . . , b1 ak }
b2 A = {b2 a1 , b2 a2 , . . . , b2 ak }
..
.
bℓ A = {bℓ a1 , bℓ a2 , . . . , bℓ ak }
このとき，
• A ∪ b1 A ∪ · · · ∪ bℓ A = G
• 相異なる i, j ∈ {1, . . . , ℓ} について，A ∩ bi A = ϕ, bi A ∩ bj A = ϕ
が成立する．したがって (ℓ + 1)k = n であり，k は n の約数である．
廣瀬
整数論と代数の初歩
17 / 34
巡回群 (cyclic group)
定義群 G にその位数と等しい位数をもつ元が存在するとき，G は巡回
群と呼ばれる．
定義 G を巡回群とする．a ∈ G の位数が G の位数と等しいとき，a は
生成元 (generator) あるいは原始元 (primitive element) と呼ばれる．
Theorem 6
p が素数ならば，乗法群 Z∗p の位数 d の元の個数は 0 または ϕ(d) である．
Theorem 7
p が素数ならば，乗法群 Z∗p は巡回群である．
廣瀬
整数論と代数の初歩
18 / 34
Th. 6 の証明
Lemma 8
任意の正整数 m について，c1 , c2 , . . . , cm を整数とし，
f (x) = xm + c1 xm−1 + · · · + cm−1 x + cm ,
とする．このとき，p が素数ならば，f (x) ≡ 0 (mod p) は Zp に属する
高々m 個の解を持つ．
Z∗p に位数 d の元 a が存在すると仮定する．このとき Lem. 8 より，
xd − 1 ≡ 0 (mod p) の Z∗p に属するすべての解の集合は
A = {a1 , a2 , . . . , ad } である．したがって，Z∗p の位数 d の元はすべて A
の元である．
ak の位数を dk とする．(ak )dk = ak dk = 1 なので，d | k dk である．した
がって，dk = lcm(d, k)/k = d/ gcd(d, k) である．したがって，dk = d の
とき，かつそのときに限り gcd(d, k) = 1 である．
廣瀬
整数論と代数の初歩
19 / 34
Th. 7 の証明
Lemma 9
任意の正整数 n について，以下の式が成り立つ．
∑
ϕ(d) = n
d|n
Th. 4，Th. 6，Lem. 9 より，Z∗p は原始元を持つ．
廣瀬
整数論と代数の初歩
20 / 34
素数 p についての Z∗p の例
Z∗11 について，原始元の個数は ϕ(10) = 4 である．
1
2
3
4
5
6
7
8
9
10
廣瀬
1
1
2
3
4
5
6
7
8
9
10
2
1
4
9
5
3
3
5
9
4
1
3
1
8
5
9
4
7
2
6
3
10
4
1
5
4
3
9
9
3
4
5
1
5
1
10
1
1
1
10
10
10
1
10
6
1
9
3
4
5
5
4
3
9
1
7
1
7
9
5
3
8
6
2
4
10
整数論と代数の初歩
8
1
3
5
9
4
4
9
5
3
1
9
1
6
4
3
9
2
8
7
5
10
10
1
1
1
1
1
1
1
1
1
1
ord.
1
10
5
5
5
10
10
10
5
2
21 / 34
平方剰余と平方非剰余
n, a を互いに素な正整数とする．
x2 ≡ a (mod n) が Zn に属する解を持つとき，a は n を法とする平方剰
余と呼ばれる．
x2 ≡ a (mod n) が Zn に属する解を持たないとき，a は n を法とする平
方非剰余と呼ばれる．
平方剰余 (quadratic residues, QR)
平方非剰余 (quadratic non-residues, QNR)
廣瀬
整数論と代数の初歩
22 / 34
平方剰余と平方非剰余
Theorem 10
p を奇素数（3 以上の素数）とする．
a は p を法とする QR である ⇔ a(p−1)/2 ≡ 1 (mod p)
証明 (⇒) a が p を法とする QR ならば，ある x ∈ Z∗p について x2 ≡ a
(mod p) が成り立つ．したがって，a(p−1)/2 ≡ xp−1 ≡ 1 (mod p)．
(⇐) a(p−1)/2 ≡ 1 (mod p) と仮定する．g を Z∗p の原始元とする．このと
き，ある k ∈ Zp−1 について a ≡ g k (mod p) が成り立つ．
a(p−1)/2 ≡ g (p−1)k/2 ≡ 1 (mod p) で g は原始元なので k は偶数でなけれ
ばならない（仮に k が奇数であるとすると，g (p−1)/2 ≡ 1 (mod p) となり
g が原始元であることと矛盾する）．したがって a は p を法とする QR で
ある．
廣瀬
整数論と代数の初歩
23 / 34
ルジャンドル (Legendre) 記号 (1/2)
p を奇素数とし，a を正整数とする．
ルジャンドル記号は以下のように定義される．

a ≡ 0 (mod p) のとき
( ) 
0
a
= 1
a が p を法とする QR であるとき

p

−1 a が p を法とする QNR であるとき
廣瀬
整数論と代数の初歩
24 / 34
ルジャンドル記号 (2/2)
Theorem 11
p を奇素数とする．このとき
( )
a
= a(p−1)/2 mod p
p
証明 a ≡ 0 (mod p) のときは明らか．
a ̸≡ 0 (mod p) ならば，gcd(a, p) = 1 で ap−1 ≡ 1 (mod p)．
(
)(
)
a(p−1)/2 + 1 a(p−1)/2 − 1 ≡ 0 (mod p)
a(p−1)/2 ≡ ±1 (mod p).
したがって，Th. 10 より
a(p−1)/2 ≡ 1 (mod p) ⇔ a は p を法とする QR
a(p−1)/2 ≡ −1 (mod p) ⇔ a は p を法とする QNR
廣瀬
整数論と代数の初歩
25 / 34
ヤコビ (Jacobi) 記号
n, a を正整数とする．
さらに，n は奇数とし，その素因数分解を n = pe11 · · · pekk とする．
ヤコビ記号は以下のように定義される．
(a)
n
=
k ( )ei
∏
a
i=1
pi
ヤコビ記号は n を素因数分解しなくても計算できる．
計算時間は O((log n)2 ) である．
廣瀬
整数論と代数の初歩
26 / 34
ヤコビ記号の計算に有用な性質
(m )
• m1 ≡ m2 (mod n) ならば，
1
=
(m )
2
n
n
( ) {
2
1 n ≡ ±1 (mod 8) のとき
•
=
−1 n ≡ ±3 (mod 8) のとき
n
(m m ) (m ) (m )
1 2
1
2
•
=
である．
n
n
n
である．
( )k ( )
2
t
=
特に，奇数 t について m =
n
n
n
(n)
(m)
• m が奇数ならば，
= (−1)(m−1)(n−1)/4
である．
n
m
2k t とすると，
廣瀬
整数論と代数の初歩
(m)
27 / 34
素数判定
RSA などのように現在広く利用されている公開鍵暗号のセットアップで
は，非常に大きな素数をランダムに生成する必要がある．
これは通常以下のようにして行われる．
1
非常に大きな整数を無作為に選択する．
2
それが素数かどうかを判定する．
この方法を何度繰り返せば素数が見つかるか？
廣瀬
整数論と代数の初歩
28 / 34
素数判定
Theorem 12 (素数定理)
N 以下の素数の個数はおよそ N/ ln N である．
この定理より，k ビットの素数の個数はおよそ以下の通りである．
2k
2k−1
2k−1
2k−1
−
≈
≈
ln 2k
ln 2k−1
ln 2k−1
(k − 1) ln 2
したがって k が大きければ
Pr[無作為に選ばれた k ビットの整数が素数である] ≈
廣瀬
整数論と代数の初歩
1
0.693 k
29 / 34
素数判定
素数判定の決定性多項式時間アルゴリズムが存在するかどうかは，長い
間未解決問題であった．
決定性多項式時間アルゴリズム
すべての入力に対して入力長の多項式時間で停止して正答を出力する
2002 年，Agrawal, Kayal, Saxena が決定性多項式時間アルゴリズムを公表
した．
しかしこのアルゴリズムは実用的ではない．
廣瀬
整数論と代数の初歩
30 / 34
素数判定
実用的な確率的多項式時間アルゴリズム
• Solovay-Strassen アルゴリズム
• Miller-Rabin アルゴリズム
上の二つのアルゴリズムは，与えられた整数が
• 素数であれば，常に正しく「素数である」と判定する．
• 合成数であれば，誤って「素数である」と判定する可能性がある．
したがって，
• 答が「合成数である」ならば，与えられた整数は必ず合成数
• 答が「素数である」ならば，与えられた整数は素数でない可能性が
ある．
廣瀬
整数論と代数の初歩
31 / 34
Solovay-Strassen 素数判定法
n を判定対象の整数とする．
1
2
3
1 ≤ a ≤ n − 1 を満たす整数 a を無作為に選ぶ．
(a)
= 0 ならば「n は合成数である」と判定して停止する．
n
以下のように判定して停止する．
(a)
≡ a(n−1)/2 (mod n) のとき，
「n は素数である」
n
上記以外のとき，
「n は合成数である」
このアルゴリズムで，n が合成数であるとき「n は素数である」と判定さ
れる確率は高々1/2 である．
廣瀬
整数論と代数の初歩
32 / 34
Miller-Rabin 素数判定法
n を判定対象の整数とする．
1
n − 1 = 2k m となる k, m を計算する．ただし m は奇数である．
2
1 ≤ a ≤ n − 1 を満たす整数 a を無作為に選ぶ．
3
b = am mod n を計算する．
4
b ≡ 1 (mod n) ならば「n は素数である」と判定して停止する．
5
6
i = 0 から k − 1 について，以下の計算を行う．
b ≡ −1 (mod n) なら「n は素数である」と判定して停止する．
上記以外のとき b = b2 mod n を計算する．
「n は合成数である」と判定して停止する．
このアルゴリズムで，n が合成数であるとき「n は素数である」と判定さ
れる確率は高々1/4 である．
廣瀬
整数論と代数の初歩
33 / 34
演習問題
1
孫子定理を証明せよ．
2
Th. 1 を証明せよ．
3
Th. 4 の証明で，A ∪ b1 A ∪ · · · ∪ bℓ A = G であることを証明せよ．
4
Lem. 9 を証明せよ．
5
与えられた整数 n が素数ならば，Miller-Rabin アルゴリズムが常に
「n は素数である」と判定することを証明せよ．
廣瀬
整数論と代数の初歩
34 / 34

Download Report