スライド 1

ユークリッド虚２次体における
最大公約数の計算
(1 - ω)-ary GCD Algorithm in Z[ω]
Fujikula Yohei (2007/02/09)
内容
> 虚２次体 R(√－３) の整数 Z[ω] にお
ける最大公約数の計算
> ユークリッド互除法の適用と結果
整数 Z[ω]
> Z[ω] = { x + yω｜x,y∈Z } , ω = (-1+√ ) /-32
3ω
2ω
ω
O
１
２
３
ノルム
―
> N( x + yω) = ( x + yω)(x + yω)
= x ２ + y２ - xy
α = x+yω
ｙω
O
Oα 2= N(α)
ｘ
約数・倍数
>約数・倍数
α＝β・γ
( α, β, γ∈Z[ω] ）
>最大公約数（GCD）
公約数の中でノルムが最大のもの
単数・同伴数
>単数
すべての整数の約数となるもの
２
Z[ω] では, ±1, ±ω, ±ω
>同伴数
整数 αに対して ±α, ±αω, ±αω
２
同伴数
>整数αは同伴な数をすべて約数にもつ
ω
-αω
２
αω
α
-α
-αω
αω
２
ユークリッドの互除法
GCD algorithm
> a = bq + r のとき（すべて整数）
a, b の公約数と b, r の公約数は等しい.
>gcd(a, b) = gcd(b, r1) = gcd(r1 , r2)
= ・・・ = gcd(rn , 0) = r n
Z[ω] で使うには・・・
>α, β∈Z[ω]
α = βγ + δ N(β) > N(δ)
となる γ, δ∈Z[ω] が必ず存在する．
証明
α = βγ + δ
N(β) > N(δ)
>N((α/β) - γ) < 1
N((α- βγ) / β) < 1
N(α- βγ) < N(β)
δ = α- βγ
α/β
γ
ユークリッドの互除法
binary GCD algorithm
>binary GCD algorithm in Z
input: a, b
a ← a / 2 k(a),b ← b / 2 k(b)
k = min{ k(a), k(b) }
while a ≠ b
k(a-b)
exchange larger of a,b with (a – b) / 2
output 2 k a
k(x): x を 2 で割ることができる回数
実験(有理整数 Z のcase)
秒
0.06
0.05
0.04
0.03
0.02
0.01
0
original
binary
100
500
1000
1500
2000
桁数
>大きな桁数の計算で有意な結果が得られる.
Z[ω] での適用のポイント
>binary GCD algorithm in Z
① 2 に対応するもの
input: a, b
②α – βを確実
a ← a / 2 k(a),b ← b / 2 k(b)
k = min{ k(a), k(b) }
に小さくできるか
while a ≠ b
exchange larger of a,b with (a – b) / 2 k(a-b)
output 2k a
Z[ω] での適用のポイント
>① 2 に対応するもの
→ (1 – ω) を選ぶ
α = a + bω
α / (1 - ω)
= {(2a - b) / 3} + {(a + b) / 3}ω
Z[ω] での適用のポイント
>②α-βを確実に小さくできるか
gcd(1 - ω, α) = 1
２
２
3 = (1 – ω) (- ω ) から
gcd( 3, α) = 1
α ≡ 1 (mod 3)
実験（整数 Z[ω] のcase）
秒
6
5
4
3
2
1
0
original
binary
100
500
1000
1500
2000
桁数
まとめ
>Z[ω] においてもユークリッドの互除
法, binary GCD algorithm が適用
することができる.

Download Report