2012年5月5日土曜日

Cornacchia-Smithのアルゴリズム:mod 4で1の素数は2平方数の和

$4$で割って$1$余る素数$p$を2つの平方数の和と表す($p=x^2+y^2$)ことの証明をこれまで幾つか見てきた.今回は,$p$が与えられたときに具体的に$x,\,y$を求めるアルゴリズムを紹介する.少し一般化して,奇素数$p$と,$p$で割り切れない正整数$d$が与えられたときに, \[ p = x^2 + dy^2 \] となる$x,\,y$が存在するかを判定し,存在すれば$x,\,y$を与える,Cornacchia-Smithのアルゴリズムを述べる:

入力:奇素数$p$, 正整数$d$で$p$で割り切れないもの.
出力:$p=x^2+dy^2$となる整数$x,\,y$が存在するか否か,存在すれば$x,\,y$を返す.
アルゴリズム:
  1. もし$(-d/p) = -1$なら$x,\,y$は存在しない.終了.
  2. $x_0\equiv \sqrt{-d}\pmod{p}$とし,$2x_0\lt p$なら$x_0 = p-x_0$と取り直す.
  3. $(a, b) = (p, x_0)$, $c = \lfloor\sqrt{p}\rfloor$とする.
  4. while $(b > c)$, $(a,b) = (b, a\pmod{b})$.
  5. $t = p-b^2$とし,もし$t\not\equiv 0\pmod{p}$または$t/d$が平方でないなら,$x,\,y$は存在しない.終了.そうでないなら,$(\pm b, \pm \sqrt{t/d})$が求める解である.

例えば$p=37$, $d=1$で$37=x^2+y^2$を解いてみよう.$x_0 \equiv \sqrt{-1} \equiv \sqrt{36} = 6\pmod{37}$. $2\cdot 6 =12 < p = 37$より, $x_0=37-6=31$と取り直す.$c=\lfloor \sqrt{37}\rfloor = 6$. すると,4の互除法の過程は$(a,\,b) = (37,\,31) \to (31,\, 6)$となり,$b=6 \leq c = 6$よりこれで終わり.5のステップで,$t=p-b^2 = 37 - 6^2 = 1$. $t/d = 1$は平方であるから,$(\pm 6, \pm 1)$が解である.

2番目のステップで,法$p$で平方根を求める計算があり,これについてもスタンダードなアルゴリズムの他に,色々と工夫があるのだが,別の機会に譲る.

上のCornacchia-Smithのアルゴリズムは,例えばH. Cohen, A Course in Computational Algebraic Number Theory (Graduate Texts in Mathematics)のアルゴリズム1.5.2, またCrandall-Pomerance著, 和田秀男監訳, 素数全書―計算からのアプローチのアルゴリズム2.3.12がこれである.虚2次体の,判別式$D$の整環で,$(D/p)=1$なる素数の上にある素イデアルが単項イデアルかを判定し,そうならその生成元を与える,と定式化し直した(H. Lenstraによる)アルゴリズムが,R. Schoof, Counting points on elliptic curves over finite fields, JTNB, 7, 1995の定理4.1として述べられている.pari-gpではqfbsolve()という函数として実装されている.きわめて高速で,500桁の素数でも一瞬で答えが求まる.以前述べた,Jacobsthal和の計算では高々数十桁ぐらいまでしか計算できないのと対照的である.(後記:クランドール・ポメランスのリンクが間違っていたので訂正.23:20)

0 件のコメント: