1.4 The Legendre Symbol
今回の内容
• Algorithm 1.4.10(Kronecker)
• Algorithm 1.4.12(Kronecker-Binary)
Algorithm1.4.10 (Kronecker) step1,2
②
a ,b  Z
b0
T:True
F:False
T
F
a,b : even
T
a 1
v : even
T
k 1
F
実際にはこの
F 計算はしなくて
よい
k  ( 1)
( a 2 1) / 8
T
ret urn1
F
v0
b : even
ret urn 0
F
T
b  b
F
a0
T
v  v  1, b  b / 2
b0
F
T
②
k  k
③
Algorithm1.4.10 (Kronecker)step3,4
③
a0
④
T
T
b 1
return 0
T
F
F
v0
a : even
b 1
F
T
v  v  1, a  a / 2
v : odd
F
T
return k
④
実際にはこの計算
はしなくてよい
k  (1)
(b2 1) / 8
k
k  (1)( a1)(b1) / 4 k
r  a , a  b (mod r ),b  r
③
Lemma 1.4.11
a, b : odd integer(b  0) then
 
a
( a 1)( b 1) / 4 b
 
   (1)


b
a
 
 
(＊)
 a  b 
( a 1)( b 1) / 4

(

1
)
  
 b  a 
(ヤコビ記号に対する相 互法則)
を変形したもの
Pythonでの実装
def kronecker(a,b):
if b==0:
if abs(a)==1:
return 1
else:
return 0
if ((a%2==0)and(b%2==0)):
return 0
v=0
while b%2==0:
v=v+1
b=b/2
if v%2==0:
k=1
k=(-1)**(((a**2)-1)/8)
if b<0:
b=-b
if a<0:
k=-k
while a!=0:
v=0
while a%2==0:
v=v+1
a=a/2
if v%2==1:
k=((-1)**(((b**2)-1)/8))*k
k=((-1)**(((a-1)*(b-1))/4))*k
r=abs(a)
a=b%r
b=r
if b>1:
return 0
else:
return k
Algorithm1.4.12 (Kronecker-Binary) step1,2
②
a ,b  Z
b0
T:True
F:False
T
F
a,b : even
T
a 1
F
v : even
T
k 1
F
k  ( 1)
( a 2 1) / 8
T
ret urn1
F
v0
b : even
ret urn 0
F
T
b  b
F
a0
T
v  v  1, b  b / 2
b0
F
③
T
②
k  k
a  a(modb
③ )
Algorithm1.4.12 (Kronecker-Binary)
step3～6
④
③
a0
b 1
F
T
v  v  1, a  a / 2
return 0
F
v0
a : even
F
T
T
b 1
F
T
k  (1)
T
return k
④
v : odd
(b2 1) / 8
k
r ba
r0
T
F
a  r
k  (1)( a1)(b1) / 4 k , b  a, a  r
③
Pythonでの実装
def kronecker_b(a,b):
if b==0:
if abs(a)==1:
return 1
else:
return 0
if ((a%2==0)and(b%2==0)):
return 0
v=0
while b%2==0:
v=v+1
b=b/2
if v%2==0:
k=1
k=(-1)**(((a**2)-1)/8)
if b<0:
b=-b
if a<0:
k=-k
a=a%b
while a!=0:
v=0
while a%2==0:
v=v+1
a=a/2
if v%2==1:
k=((-1)**(((b**2)-1)/8))*k
r=b-a
if r>0:
k=((-1)**(((a-1)*(b-1))/4))*k
b=a
a=r
else:
a=-r
if b>1:
return 0
else:
return k