不定方程式

Cubic Residue
and
Cubic Root Modulo p
東京都立大学理学部数学科
藤代武人
1
卒業研究のテーマ
前期のゼミでは
「平方剰余・mod pでの平方根」
について学びました.
そこで・・・
「立方剰余はどう計算する？」
「 mod pでの立方根はどう計算する？」
以上の事を中心に後期では研究をしました.
2
本日の内容


Cubic Residue (立方剰余)
Cubic Root (立方根)
3
Cubic Residue…?

定義 [ (rational) 立方剰余 ]
a  Z , p  P(prime) が与えられたとき ,
x 3  a (mod p )
をみたす x  Z p が
C ubic Residue
 存在する  a は mod p で

存在しない  a は mod p で C ubic non Residue
4
疑問…

平方剰余と同様のことはできるだろうか?




剰余記号
相互法則 (補充法則)
ヤコビ記号
アルゴリズム
5
立方剰余記号

定義 [立方剰余記号]
Z [ ]  {a  b | a, b  Z }
(  (1   3 ) / 2) 上で定義をする .
 
N ( )  3,  |       ( N ( ) 1) / 3 (mod )
  3
( N :norm)
このとき ,
C ubic Residue
   1
  
2

,

C ubic non Residue

 3 
(  Z [ ],  : Z [ ] 上での素元 )
6
立方剰余記号について
平方剰余記号の場合と同様のことが言える.

multiplicity
          

      
  3   3   3

generalize
(ヤコビ記号)
t
    i  Z   のとき ,
mi
i 1

modularity
    (mod  ) のとき ,



  
   
3   3
t
   mi
 
     
とする .
  3 i 1   i 3
(右辺は剰余記号 )
7
立方剰余の相互法則
以下, mod3 で 1 と合同な数を primaryと呼ぶ .
 ,  : primary, N (  )  3,
N ( )  N (  )

    
    
  3   3
これらの法則は,
剰余記号を計算する
上で重要な役割を
果たすことになる.
(補充法則)
  1  3(m  n ), m, n  Z (primary) とする .
π :primaryprime
1  
   m
(1) 
  3
 1 
(3)    1
 
 
(2)     ( m n )
  3
8
Algorithmのポイント

剰余記号は,先程の相互法則・補充法則
を繰り返し用いて計算する.
(互除法のアルゴリズムと似ている.)

今回紹介するものの他にも立方剰余を求める
アルゴリズムはある.

有理数を扱う場合には注意が必要なので,
次で触れることにする.
9
α:有理整数, β:有理素数の場合

β = 2 (mod 3) の有理素数の場合
⇒ Z [ω] 上においても,
β は素元となっているのでそのまま計算できる.

β = 1 (mod 3) の素数の場合
⇒    (  Z [ ], prime) と分解できる .
        
   
      とできるので ,
  3   3   3   3
 
  の方を考える .
  3
10
Algorithm (Cubic Residue)[1/2]
[input]  ,   Z [ ] \ 0 (  : not divisible1   )
 
[output]  
  3
[step1]
α:有理整数,
β:有理素数(mod 3 で1)の場合,β=ππとな
るπを求めβとする.
(これはcornacchiaのアルゴリズム[HP参
照]を利用して計算する.)
 ,   Z [ ] s.t.
  ( )i (1   ) j  ,   ( )i 
1
1
2
[step2]
m, n  Z s.t.   1  (3m  n )
t  m j1  (m  n)i1 (mod3),    ,   
[step3]
~
~
if N ( )  N (  ) then
 ,  を入れ替え
11
Algorithm (Cubic Residue)[2/2]
[step4]
while    do
  Z [ ] s.t     ( )i (1   ) j 
m, n  Z s.t   1  (3m  n )
t  t  m j  (m  n)i (mod3),   
~
~
if N ( )  N (  ) then
 ,  を入れ替え
[step5]
if   1 then
c0
else
c  t
12
Cubic Root…?
mod p で3乗根が存在するかどうかは,
確かめることができた.
実際に,根は何になるのか?
どのように求める?
mod p での平方根を求めるアルゴリズムを
3乗根へ拡張する!!
13
Algorithmのポイント [1/2]

入力に関して
a  Z , p( 3e q  1)  P (prime) の入力に対して，
以下の場合を考える .
・p  2 ,p  3
 xa
・p  2 (mod3)  x  a
解はひとつに定まる
( 2 p 1)
3
(mod p )
・p  1 (mod3)  ・・・
解は３つある
p  1 (mod3) のときの
解を求めるアルゴリズムを示す．
14
Algorithmのポイント [2/2]
a が C ubic Residue ならば ,
p  3e q  1 (q  0 (mod3)) に対し ,
G  g を Z p の 3 - Sylow部分群とすると ,
q  1 (mod3) のとき ,
q  2 (mod3) のとき ,
3
3
a a
( 2 q 1)
a a
3
gk
3
gk
( q 1)
となる k が 0  k  3e の範囲で存在する .
という事を用いる .
具体的にはこの「g」と「k」を求めていくアルゴリズムである.
15
Algorithm (Cubic Root) [1/2]
[input] p( 3e q  1 : (q  0 (mod3))  P (prime), a  Z
[output] x  Z p s.t. x 3  a (mod p ) or "no cubic root"
h
[step1] h  Z p s.t.    1 (mod p)
 p 3
をランダムに選択する
h
[step2] g  h , sym bol   , y  g , r  e
 p 3
q
 a 3 (if q  2 (mod3))
x   ( 2 q 2 )
a 3 (if q  1 (mod3))
b  a 2 x 3 , x  ax
( q 2 )
(全て mod p での計算 )
16
Algorithm (Cubic Root) [2/2]
[step3] if b  1 (mod p ) then
return ( x, x * sym bol, x * sym bol2 )
else

find m  min i

b  1 (mod p )
3i
if m  r then
return " There is no cubic root"
[step4] if sym bol b
3m1
then
t  y 2 , sym bol ( sym bol) 2
else
ty
t t
3r m1
, y  t 3 , r  m, x  xt, b  by
go to step3
(全て mod p での計算 )
17
計算量について

Cubic Residue
 
  を求める際 ,  が mod 3 で 1 の素数の場合 ,
  3
   なる  を求める時間を考慮すると ,
 (log4  ) となる .
cubic residue symbolの計算部分のみを考慮すれば ,
 (log2 N ( )) となる .

Cubic Root
平方根を求めるアルゴリズム(Tonelli-Shanks method)と
同様に, O (log4p) となる.
18
まとめ

相互法則等の証明は今回は省略しました．
詳細に関しては参考文献(*)(**)等を参照してください．
また,pythonで作成したプログラム等は
http://tnt.math.metro-u.ac.jp/labo/grad/2006/taketo/
にあります.

今後の課題


3乗根を求めるアルゴリズムについては
さらに速く (O (log3p)で) 計算できるものがあります．
このalgorithmをもとに, Cardanoの方法を用いて,
Fp上での3次方程式を解くことも可能となります.
19
References(1/2)
Ⅰ) TakingC ubeRoots in Z
m
(C .Padro,G.Saez) 2001
Ⅱ) On the C omputation of C ubeRoots Modulo p
(SigunaMuller) 2004
Ⅲ) A C lassicalIntroduction to
ModernNumber Theory (2nd ed)
(KennethIreland,MichaelRosen)
20
References(2/2)
Ⅳ) Efficient Algorithms for gcd and Cubic Residuosity
in the Ring of Eisenstein Integers
o
(Ivan B. Damgard, Cudmund Skovbjerg Frandsen)
2003
Ⅴ) Reciprocity Laws
(Franz Lemmermeye
r)
21

Download Report