1.3.3 The Chinese Remainder Theorem

1.3.3 The Chinese Remainder Theorem
1
• 今回の内容
– 合同式の性質
– Chinese Remainder Theorem(CRT)
– CRTに付随する命題
– CRTを用いた計算のアルゴリズム
• 本題に入る前に合同式の性質について
触れておく.
2
• 合同式についての性質をいくつか挙げておく.
a, b, c, d , m, n  
(1)a  a modm 
(2)b  a (modm)  a  b(modm)
(3)a  b(modm), b  c(modm)  a  c (modm)
(4)a  b(modm), c  d (modm)
 a  c  b  d (modm), ac  bd (modm)
(5)a  b(modm)
 all for divisor d m,
a  b(modd )
(6)a  b(modm), a  b(modn), gcd( m, n)  1
 a  b(modm n)
3
Theorem1.3.9
(Chinese Remainder Theorem).
m1 ,, mk , x1 ,, xk  
assume : every pair (i, j ),
x i  x j (mod gcd( mi , m j ))

x  Ζ s.t. x  xi (modmi ) for 1  i  k
( x は lcm(m1 ,, mk ) を法として合同
)
4
proof
claim1
gcd( m, n)  d , lcm(m, n)  lとすると ,
x  a(modm), x  b(modn)
(1)
が解を持つための必要十分条件は,
a  b(modd )
である , 解は, l　を法としてただ一つである .
proof of claim1
()
(1)が解 x を持つとき , d  gcd( m, n) より ,
x  a (modd ), x  b(modd ).
よって a  b(modd ) となる .
5
proof
proof of claim1 つづき
( )
a  b(modd ) が成り立っているとき
,
(1)が解を持つことを示す .
x は t  Z によって ,
x  a  mt
(2) と書ける .
この xが二番目の合同式の解になるのは ,
a  m t  b(modn) すなわち ,
m t  b  a (modn)
(3) の時である .
6
proof
proof of claim1 つづき
a  b(modd )より ,
m
ba
n
t
(mod )
と , 表せる.
d
d
d
よって (3)の解 tは, t0 , s  Z によって ,
n
s と表すことができる
d
これを (2)に代入すると ,
x  a  m t0  ls (dl  m n )
t  t0 
.
この x は(1)の解である .
また , x と l を法として合同な整数は,
全て(1)の解である . 従って ,
x  a  m t0 (modl )
を満たす整数 x は全て (1)の解である . ■
7
proof
claim1より、 2つの合同式
x  a1 (modm1 ), x  a2 (modm2 )
の解を ,
x  b(mod lcm(m1, m2 ))
の形で表すことが出来る .
これと x  a3 (modm3 )が,
lcm(m1 , m2 ,m 3 )を法として ,
ただ一つの解を持つことを示す .
仮定より , b  a1 (modm1 )
故に, b  a3  a1  a3 (modm1 )
従って , b  a3  a1  a3  0(mod gcd( m1 , m3 ))
即ち, (b  a3 ) gcd( m1 , m3 ) (同様にして , gcd( m2 , m3 ))
従って , lcm(gcd(m1 , m3 ), gcd( m2 , m3 )) で割り切れる .
8
proof
claim2
a , b, c  Z
gcd( lcm(a, b), c)  lcm(gcd(a, c), gcd(b, c))
proof
略. ■
上記のclaim2より ,
gcd(lcm(m1 , m2 ), m3 )  lcm(gcd(m1 , m3 ), gcd( m2 , m3 ))
即ち, b  a3 gcd(lcm(m1 , m2 ), m3 ) である .
従って , claim1より , lcm(m1 , m2 , m3 )を法として ,
唯一つの解を持つ.
後は, r についての帰納法で示す事が出来る. ■
9
Corollary 1.3.10.
m1 ,, mk  Z s.t. gcd( mi , m j )  1
(for i  j )


xi  Z , x  Z
s.t. x  xi (mod mi )
(for 1  i  k )
k
( x は  mi を法として合同 )
i 1
10
proof
k
M   mi , M i  M / mi とおく .
i 1
ai Mi  bmi  1 (b  Z )
(gcd(M i , mi )  1 となる . ）
このとき ,

ai s.t . ai M i  1(modmi ) (by ext endedgcd)
k
さらに , x   ai M i xi (1) と定めると , これが解になる .
i 1
実際に, (1)の右辺第一項に注目すると ,
x  x1 (modm1 )
a1M 1 x1  x1 (modm1 ) であり ,
x  x2 (modm2 )
第二項以下は, M 2 , M 3,  M k が m1 で割り切れるから ,
a2 M 2 x2    ak M k xk  0(modm1 ) となる .
以下, m2 , , mk について同様に考えればよい .
一意性は
x, x' を解とすると

x  xk (modmk )
となる .
, x  x' (modmi ) (i  1, , k )
であるから , ( x  x' ) mi (i  1,  , k )
よって , M についても同様 . (合同式の性質(6))■
11
Algorithm 1.3.11(Chinese).その１
Input:
mi , xi  Z (1  i  k )
Output:
x  Z ( x  xi (modmi ) for all xi )
Step1:
j  2, C1  1
Step2:
p  m1  m j 1 (modm j )
負担にならなければ ,
mi , ( xi )
を昇順に並べ替える .
compute(u, v, d ) s.t. up  vm j  d  gcd( p, m j ) (by extgcd)
if d  1 then
output an errormesage (themi are not pairwise coprime)
else
C j  u, j  j  1
if j  k then
go to step2
m1  mk
を固定する場合は ,
step1, 2を事前に計算するほうがよい .
12
Algorithm 1.3.11(Chinese). その２
y2  ( x2  y1 )C2 (modm2 )
Step3:
y1  x1 (modm1 )
for j  2,, k
y3  ( x3  ( y1  m1 y2 ))C3 (modm3 )
y4  ( x4  ( y1  m1 ( y2  m3 y3 )))C4 (modm4 )

y j  ( x j  ( y1  m1 ( y2  m2 ( y3    m j  2 y j 1 ) ))C j
(modm j )
Step4:
x  y1  m1 ( y2  m2 ( y3    mk 1 yk )))
return x
13
Algorithm1.3.12(Inductive Chinese).
Input:
mi , xi  Z (1  i  k )
Output:
x  Z ( x  xi (modmi ) for all xi )
Step1:
Step2:
i  1, m  m1 , x  x1
if i  k then
return x
else
i  i 1
comput eu , v s.t. um  vmi  1(by ext gcd)
Step3:
x  um xi  vmi x
m  m mi
x  x(modm)
go to step 2
14
Pythonでの実装(Algorithm1,3,12)
import nzmath.gcd
x1,xk , m1,mkをリスト型で入力
def crt(xl,ml):
#step1
k = len(xl)
m = ml[0]
x = xl[0]
NZMAT Hのmoduleを利用
#step2,step3
for i in range(1,k):
u,v,d = gcd.extgcd(m,ml[i])
If d > 1:
raise Error
x = u＊m＊xl[i] + v＊l[i]＊x
m = m＊ml[i]
x = x%m
return x
15
example
x1  5, x2  3, x3  13, m1＝7, m2  11, m3  2 の場合
i 1
u , v  3,2
i2
u , v  1,38
( s.t. u * 7  v *11  1)
x  3 * 7 * 3  2 *11* 5  47
( s.t. u * 77  v * 2  1)
x  1* 77 *13  (38) * 2 * 47  2571
m  7 *11  77
x  47(mod77)
m  77 * 2  154
x  47(mod154)
47 (mod154)
16
課題
• Algorithm1.3.11の実装
• Ｅｘｅｒｃｉｓｅ８，９の取り組み
17

Download Report