0 (Favした一覧ページはユーザーページから) Tweet

二次体$\mathbb{Q}(\sqrt{d})$の整数環を考えることで、問題が簡単になる場合がある。

ガウス整数

$\mathbb{Z}[i]:=\{a+bi|a,b\in\mathbb{Z}\}$はガウス整数と呼ばれている。 ガウス整数$\mathbb{Z}[i]$は余り付き割り算が行える（gcdが定義できてEuclidの互除法が計算できる）ことから素元分解の一意性が導かれる。

演習問題

yukicoder No.321 (P,Q)-サンタと街の子供たち)
ガウス整数を用いた夕叢霧香さんの解説が整数論テクニック集のページ34にある。

$p=x^2+y^2$の整数解

$p$を奇素数とする。ガウス整数環$\mathbb{Z}[i]$で考えることにより$O(\log(p))$で求めることができる [1]。$p=3\pmod 4$のとき、解は存在しない($\bmod 4$で考えると分かる)。 $p=1 \pmod 4$のとき平方剰余の相互法則より、$-1$は平方剰余である。従って$u^2=-1 \bmod p$を満たす$u$が存在する。(適当な平方非剰余$k$をとり、$u = k^{(p-1)/4} \pmod p$とすればよい)。 このとき、ある$m$が存在して $$u^2+1=mp\Leftrightarrow(u+i)(u-i)=mp$$ である。 素元 $\pi \mid p$ を適当にとる。$\pi \mid p$ かつ $\pi \mid \alpha$（$\alpha$ は $u\pm i$ のうち都合の良い方）。 $p\nmid \alpha$ なので、$p\nmid \pi$。 $\mathrm{N}(p)=p^2$であるので$p$は2つの素元$p = \pi \pi'$に分解される。 これと $p\nmid \alpha$ より、$\gcd(p,\alpha) = \pi$である。従って$\gcd(u+i,p)=x+yi$となる$(x,y)$をとることで$x^2+y^2=p$となる組$(x,y)$が得られた。 ガウス整数の素元分解の一意性から、$(x,y)$は自明な重複($(y,x)$,$(-x,y)$,etc)を除いて一組に定まる。 計算量は$O(\log p)$である。

演習問題

UVA 12031 - Summation of Four Squares
与えられた$T(< 120000)$個の$n(< 10^{17})$について$n=x^2+y^2+z^2+w^2$を満たす$(x,y,z,w)$をそれぞれ求める問題(四平方数定理より必ず存在)。[1] で$O(\log^2 n)$のアルゴリズムが与えられている。

[1] Rabin, Michael O., and Jeffery O. Shallit. "Randomized algorithms in number theory." Communications on Pure and Applied Mathematics 39.S1 (1986): S239-S256.