自分メモ２

2010年09月22日(水)

8k+1型の素数Pは x^2 + 2y^2 = P と表すことができる。これを計算する方法の自分メモ(および考察)

例)
19 = 4^2 + 2*1^2
193 = 11^2 + 2*6^2

これも3k+1型同様な方法で計算できます。

x^2 + 2 = n*P、すなわち x^2 = -2 (mod P) をまず解くところから。

すなわち、有限体Fpにて x^2 = -2の根をもとめることになります。

以下 N=P-1とします。

ところで 4k+1型の素数には自乗して-1になる数があります。それは原始根をeとすれば、e^(N/4) に相当するのでした。 8k+1も4k+1型ですから、当然そういう数があります。

その数を iと置けば

(1+i)^2 = 2i

うーん。惜しい。右辺のiが邪魔ですね。しかしNは８の倍数ですから、自乗して iになる数、すなわち8乗して1になる数があります。それは e^(N/8)のような数です。この数をjとすれば

(j+ij)^2 = 2ijj = -2

これが答えです。左辺を実際に計算すると

j = e^(N/8)
ij = e^(3N/8)

ということになります。

例) 193の原始根は5である。N=192だから、N/8は24, 3N/8は72

5^24 = 43 5^72 = 184

故に 43+184=23=34 (mod 192)

が答え。実際

34^2+2 = 1185 = 11 * 193

あとは、前回同様 K(√-2)を考えて、その中で素因数分解をしていくわけですが、ここで右辺に11がでてきました。

これは8k+1型ではありません。困りました。

実は 8k+3型の素数も x^2 + 2y^2 = P と表すことができるのです。実際11は 3^2+2 と表せるので、K(√-2)では既約ではありません。

が、ここで、説明したような8k+1型のやり方ではどうやっても答えを求めることができません。

そこで、次のようにします。

Fpでは数 x は (P-1)/2乗すると-1になります。したがって、さらに１乗、すなわち(P+1)/2乗すると、-xになります。

これを利用します。

今 x^2 = -2 (mod P)に解があるとします(※)。両辺を (P+1)/4乗すると

x^((P+1)/2) = (-2)^((P+1)/4)

-x = (-2)^((P+1)/4)

x = -(-2)^((P+1)/4)

これが答えです。

4k+3型の素数Pに関しては P+1が４の倍数になるので、こういう技が使えるわけです。

例) P=11とします。

x^2 = -2 (mod 11)

両辺を3乗して

x^6 = -x = -8 (mod 11)

故に x= 8。

実際、8^2+2 = 66

で、最後に(※)ですが、これは平方剰余の相互法則で解があるかどうかがわかります。解がある条件は

p=8k+1, 8k+3

となります。

で、これだけでは何ですので、もうちょっと考察を。

P=4k+3

とするとこのFpには-1の平方根がありません。そこでそういう数があるとして、iとおきましょう。

すると、a + bi (a, bはFpの元)というものが考えられます。これはP^2個の元からなります。P^2 = Qとおきます。

ところで、このような数は加減乗除に関して閉じており体になります。0を覗くQ-1個の元に関しては、Q-1乗して初めて1となる数、すなわち原始根を持っています。 (何故そうなるのかと言えば、多項式環 Fp[X]の x^2+1による剰余環が聖域だから)

例)P=11とする。Q=121である。e = (1+4i)とすれば

e^2 = (7+8i), e^3 = (8+3i), .... e^120 = 1

120乗して初めて1になるのでeは原始根。

ところで、奇素数Pにおける、Q-1は必ず８の倍数になるので、このような体Fqでは1の８乗根があります。

その中でも8乗しないと１にならない数が４つあり、それは指数が、(Q-1)/8, 3(Q-1)/8, 5(Q-1)/8, 7(Q-1)/8 となるところで、例えばP=11なら

e^15, e^45, e^75, e^105 です。

今e^15をjとおけば、j^3, j^5, j^7が８乗根となります。

実際計算してみると、

j= e^15 = 4+7i
j^3 = e^45 = 4+4i
j^5 = e^75 = 7+4i
j^7 = e^105 = 7+7i

ところで

e^120 = 1
e^60 = -1
e^30 = i

だから、

e^15 = jとすれば ij = e^45

故に (e^15 + e^45)^2 = 8^2 = -2(mod 11)

となるわけです。見れば分かる通り、和を取るとiの係数が０になるのが味噌で、iの係数が0 というのは、つまりその数がFpの元になるということ。

このようにe^15 と e^45が共役だから綺麗に消えてくれるわけですが、どんな奇素数でも共役になるというわけではありません。

ところで、Fqにはフロベニウス写像というのがあります。簡単に言うと

Fqにおいて、元をp乗すると、必ずその共役元になる

というものです。実際 e^15の 11乗を考えれば、

(e^15)^11 = e^165 = e^45

(e^120=1だから)

さらに考察すれば j=e^15は 8乗根なわけだから、８乗すると１になってしまうわけで、となると、jをP乗するときは、Pを8で割った余りが重要になります。

もしPを8で割ったあまりが3ならばフロベニウス写像により、jは j^3に移されます。あまりが７ならば j^7に移されます。

11は 8k+3型ですから、 j^3 すなわち ijが共役元であり、(j+ij)^2が２となります。

一方 8k+7型は、 j^7すなわち -ijが共役元ですから、(j-ij)がFpの元になることがわかります。実際その平方を計算すると

(j-ij)^2 = 2

となります。よって、8k+7型の素数では

平方して 2 となる元があることがわかります。実際

3^2 = 2 (mod 7)

なるほど、こう考えると平方剰余の相互法則もまた違った視点で見えてくるな。と思った次第。

続く(予定)

元祖ワシ的日記