4n+1型素数の性質                        戻る

 次の表は、1000以下の素数表である。その中で、4n+1型の素数は赤字の数である。
全部で80個(168個中)ある。

2 79 191 311 439 577 709 857
3 83 193 313 443 587 719 859
5 89 197 317 449 593 727 863
7 97 199 331 457 599 733 877
11 101 211 337 461 601 739 881
13 103 223 347 463 607 743 883
17 107 227 349 467 613 751 887
19 109 229 353 479 617 757 907
23 113 233 359 487 619 761 911
29 127 239 367 491 631 769 919
31 131 241 373 499 641 773 929
37 137 251 379 503 643 787 937
41 139 257 383 509 647 797 941
43 149 263 389 521 653 809 947
47 151 269 397 523 659 811 953
53 157 271 401 541 661 821 967
59 163 277 409 547 673 823 971
61 167 281 419 557 677 827 977
67 173 283 421 563 683 829 983
71 179 293 431 569 691 839 991
73 181 307 433 571 701 853 997

 このページでは、4n+1型素数が持ついろいろな性質をまとめてみたい。

 素数が無限個あるように、4n+1型素数も無限個ある。また、(偶数)2+1を素因数分解

すると、その素因数はすべて4n+1型素数である。また、逆に、4n+1型素数は、ある偶数

に対して、(偶数)2+1の素因数となる。

例 x2+1 の形の整数の素因数は、2 または 4n+1型の素数であることを確認せよ。

 まず、いくつか計算してみよう。

 x=1 のとき、 x2+1=2

 x=2 のとき、 x2+1=5 → 5 は、4n+1型の素数

 x=3 のとき、 x2+1=10=2・5 → 5 は、4n+1型の素数

 x=4 のとき、 x2+1=17 → 17 は、4n+1型の素数

 x=5 のとき、 x2+1=26=2・13 → 13 は、4n+1型の素数

 x=6 のとき、 x2+1=37 → 37 は、4n+1型の素数

 x=7 のとき、 x2+1=50=2・5・5 → 5 は、4n+1型の素数

 x=8 のとき、 x2+1=65=5・13 → 5、13 はともに、4n+1型の素数

 x=9 のとき、 x2+1=82=2・41 → 41 は、4n+1型の素数

 x=10 のとき、 x2+1=101 → 101 は、4n+1型の素数

    ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

 上記の計算で気がつくことは、

 x が偶数のとき、x2+1 の形の整数の素因数は、4n+1型の素数のみ

になっていることだろう。

 x が偶数のとき、x2+1 は、4で割って1余る数で、素因数 2 は持たず奇数である。

 x が奇数のとき、x2+1 は、素因数 2 を必ず持つ。

 そこで、

  数 x2+1 の奇数の素因数は、4n+1型の素数のみ

であることは、次のように証明される。

(証明) x=1、2 のとき、命題は成立している。

 3以上の整数 x に対して、初めて命題が成立しないものとする。

 x が偶数のとき

  x2+1=A・B (A は、4n+3型の素数で、B は整数)と分解されるものとする。

 このとき、左辺は、4で割って1余る数なので、Bは、4で割って3余る数でなければならな

い。よって、適当に、Bの素因数のうち 4n+3型の素数とAとを入れ替えることにより、

A≦B としても一般性を失わない。

 ここで、 x<A とすると、 x+1≦A≦B で、

   x2+1=A・B≧(x+1)2=x2+2x+1

となり、矛盾するので、 A≦x である。

 このとき、 (x−A)2+1=x2+1−2xA+A2=A・B−2xA+A2=A(A+B−2x)

 x−A<x で、帰納法の仮定より、(x−A)2+1 の奇数の素因数は、4n+1型の素数の

みのはず。ところが、奇数 A は、4n+3型の素数なので矛盾。

 したがって、3以上の偶数 x に対して、命題は成立する。

 次に、x が奇数のとき

  x2+1=2・N (N は、4で割って1余る数) において、x が偶数のときと同様に、

 x2+1=2・A・B (A は、4n+3型の素数で、B は整数)と分解されるものとする。

 このとき、A・Bは、4で割って1余る数なので、Bは、4で割って3余る数でなければならな

い。よって、適当に、Bの素因数のうち 4n+3型の素数とAとを入れ替えることにより、

A≦B としても一般性を失わない。

 ここで、 x<A とすると、 x+1≦A≦B で、

   x2+1=2・A・B≧2(x+1)2=2x2+4x+2

となり、矛盾するので、 A≦x である。

 このとき、 (x−A)2+1=x2+1−2xA+A2=2・A・B−2xA+A2=A(A+2B−2x)

 x−A<x で、帰納法の仮定より、(x−A)2+1 の奇数の素因数は、4n+1型の素数の

みのはず。ところが、奇数 A は、4n+3型の素数なので矛盾。

 したがって、3以上の奇数 x に対して、命題は成立する。

 以上から、全ての自然数 x に対して、x2+1 の奇数の素因数は、4n+1型の素数のみ

であることが示された。(証終)


 このことから、次が成り立つことは明らかだろう。

系 (偶数)2+1 の素因数はすべて 4n+1型の素数である


 さらに、フェルマーにより見出され、オイラーにより証明された次の事実は有名であろう。

  4n+1型素数は、2つの平方数の和として表せる

 平成22年7月25日付けで、当HPの掲示板「出会いの泉」にHN「k.nika」さんが、この
4n+1型素数についての話題を書き込まれた。

 次のようなものを考えてみました。

 すべての正の整数は高々3つの三角数で表す事が出来るが、特に

4n+1型素数の n は 2つの三角数の和で表す事が出来る。


       n=a(a+1)/ 2 + b(b+1)/ 2          (ただし、a、b は非負の整数)

(注意) 便宜的に、0(0+1)/2=0 も三角数と呼ぶことにする。

(証明) 4n+1型素数は、2個の平方数の和で表すことができるので、P=A2+B2 と置ける。

   両辺を2倍して右辺を式変形し、

     2P=2A2+2B2=(A+B)2+(A−B )2   (ただし、A>B)

  P=A2+B2 より、A と B について、一方は偶数、他方は奇数になるので、

     A+B=2a+1 、A−B=2b+1  (ただし、a、b は非負の整数)

 とおける。このとき、

    2P=(2a+1)2+(2b+1)2=4a2+4a+1+4b2+4b+1

  よって、 P=2a2+2a+2b2+2b+1

    P=4n+1 なので、 4n+1=2a2+2a+2b2+2b+1

  したがって、 n=a(a+1)/2 + b(b+1)/2  となる。  (証終)

(コメント) P=A2+B2 から P=2a2+2a+2b2+2b+1 への精密化から得られる結
      果ですね!k.nika さんに感謝します。

 さらに、k.nika さんは、次の問題も考えられた。

 4n+1型素数Pは2つの平方数の和で表す事が出来るが、その2つの平方数は、

    P=(a+b+1)2+(a−b)2  (ただし、a、b は非負の整数で a>b)

と表す事が出来る。

例  5=22+12=(1+0+1)2+(1−0)2

   13=32+22=(2+0+1)2+(2−0)2

   17=42+12=(2+1+1)2+(2−1)2

   29=52+22=(3+1+1)2+(3−1)2

(証明) 4n+1型素数 P=A2+B2 において、

     2P=2A2+2B2=(A+B)2+(A−B )2   (ただし、A>B)

  このとき、A+B=2a+1 、A−B=2b+1  (ただし、a、b は非負の整数) とおける

 ので、2P=(2a+1)2+(2b+1)2={(a+b+1)+(a−b)}2+{(a+b+1)−(a−b)}2

ここで、 a+b+1=α 、a−b=β と置くと、2P=(α+β)2+(α−β)2=2α2+2β2

となり、 P=α2+β2=(a+b+1)2+(a−b)2 と表すことができる。  (証終)


 この問題について、らすかるさんが別証を与えられた。(平成22年7月25日付け)

(別証) P=A2+B2 (ただし、A>B) において、

       a=(A+B−1)/2 、 b=(A−B−1)/2

    とおくと、 a、b は非負の整数で、

       A=a+b+1 、 B=a−b

    なので、 P=(a+b+1)2+(a−b)2 と表すことができる。  (別証終)

 さらに、k.nika さんは、次の問題も考えられた。

 4n+1型素数 P=A2+B2 (ただし、A>B) において、斜辺の平方がPで、残り

の2辺がA、Bである直角三角形を考えるとき、その直角三角形の面積Sは、

    S=a(a+1)/2 − b(b+1)/2  (ただし、a、b は非負の整数 a>b)

と、高々2つの三角数の差に書ける。


(証明) S=AB/2=(a+b+1)(a−b)/2=(a2+a−b2−b)/2 より、

    S=a(a+1)/2 − b(b+1)/2  (証終)

 これについて、らすかるさんからのアドバイスです。(平成22年7月25日付け)

 三角数 (0)、1、3、6、・・・ の定義から、その階差数列は自然数列 1、2、3、・・・ と
なる。よって、面積が整数であれば、必ず2つの三角数の差で表すことができる。


 また、k.nika さんは、4n+1型素数Pにおいて、2つの平方数を求めるを作られた。
                                      (平成22年7月25日付け)

 この表の使い方について、4n+1型素数 P=Y2+Z2=109 を例として説明します。

(1) まず、最初に n を求める。 ・・・・・ n=(109−1)/4=27

(2) 表のやや中央、赤い三角数のラインから下で、「27」を探す。

(3) 「27」を見つけたら、そこから垂線を下ろすと、赤いY列の交点の数字とぶつかる。

   この場合、「10」が Y の値となる。

(4) 次に、(2)で探した「27」から、左斜め上45度のラインで同じ「27」を探す。

(5) 探したら、その数字の真上のZ列との交点の数字「3」が Z の値となる。

(確認) 102+32=100+9=109

    ちなみに、この表の数字の意味はこちら

(コメント) 何となく意味深な表ですね!k.nika さんに感謝します。


 k.nika さんが、「4n+1型奇数の n」について新たな問題を提起された。
                                       (平成22年8月1日付け)

 α2+β2 という形の 4n+1型の奇数 Q を考える。 α=2c+1、β=2d  (c、d: 非負
整数)とする。そして、次のような操作を行う。

 (1) n を超えない最大の平方数を求め r とする。(n≧r)
 (2) その数を n から引き、その答えを e とする。
 (3) 次に、e を4倍して1を足し、その答えを f とする。
 (4) √f を求める。


 この操作を、α の値を一定にし、β の d値 を1ずつ増やす形で計算し、横に並べてみる。

α=1の場合

番号 α β √f
2
17 2
37 2
65 16 2
10 101 25 2

 この場合、 √f=1 の値は αの値 ”1” と一致している。

α=3 の場合

番号 α β √f
25 2
45 11 2
73 18 2
10 109 27 2
12 153 38 2

 この場合も、√f=3 の値は、αの値 ”3” と一致している。

α=5 の場合

番号 α β √f
61 15 2 25
89 22 2 25
10 125 31 2 25
12 169 42 2 25
14 221 55 2 25

 この場合も、√f=5 の値は、αの値 ”5” と一致している。

 もし、このまま上手くいけば、4n+1型奇数Qの中には、4n+1型素数Pも当然含まれる
ので、n の値から最大平方を引くだけで、Y値が分かり、おのずと Z値も分かるのではない
かと期待してしまう。

α=7 の場合

番号 α β √f
113 28 2 13
10 149 37 2
12 193 48 2 12 49
14 245 61 2 12 49
16 305 76 2 12 49
18 373 93 2 12 49
20 449 112 102 12 49

 この場合、前半2つが破綻してしまったが、後の√f=7の値は、αの値”7 ”と一致してい
る。因みに、破綻した n=37 に対しては、最大平方より1つ下の平方数 52 を引いてみる
と、37−52=12 から、 f=49 となり、√f=7 で α値と一致する。

 n=28に対しても同様に計算して、28−42 =12 で、√f=7 となる。

ここで、この破綻の仕組みについてご教授をお願いしたい。

 (1) αの値と破綻する番号との因果関係
 (2) 一度破綻から回復すると、もう二度と破綻は起こらないのか
 (3) 4n+1型素数 P=Y2+Z2 のPのみが与えられた場合、n から、最大平方から何
    番目の平方数を引けば、YとZが求まるか分かるアルゴリズム
 (4) 4n+1型素数Pが与えられた場合、n から最大平方を引いてY、Zが求まる確率は?



 上記について、らすかるさんからコメントをいただきました。(平成22年8月2日付け)

 (1) αの値と破綻する番号との因果関係

   破綻するのは α2≧4β+5 つまり β≦(α2−5)/4 の場合。

   α<βに限定せず、β=2{(番号)−1} とするのであれば、(番号)≦(α2+3)/8

  のとき破綻する。

   α<βに限定する場合は、 (番号)=(β−α+1)/2 なので、(番号)≦{(α−2)2−5}/8

  のときに破綻する。

   なぜα<βに限定している?


 (2) 一度破綻から回復すると、もう二度と破綻は起こらないのか

   上記により、起こらない。

 (3) 4n+1型素数 P=Y2+Z2 のPのみが与えられた場合、n から、最大平方から何
    番目の平方数を引けば、YとZが求まるか分かるアルゴリズム

   それがわかったらすごいですね。

 (4) 4n+1型素数Pが与えられた場合、n から最大平方を引いてY、Zが求まる確率は?

   α≪βである可能性が高いとは考えられないので、一般的には、α2≧4β+5 を満
  たし、確率は0になると思います。



 FNさんも、4n+1型素数Pを α2+β2 の形で表すことについて、ExcelVBAで調べられま
した。(平成22年8月2日付け)

 k.nika さんは、α を奇数、β を偶数としていますが、そうはしないで、α>βとします。
100万以下で調べたら瞬時だったので1億以下で調べました。さすがにかなり時間がかかり
ましたが10分弱でした。むしろ書きだしたテキストファイルを読み込むのに苦労しました。適
当なエディターを持っていれば問題ないでしょうが、残念ながら持っていません。Excel2007
は100万行強まで読めますが、それでは足りません。ワードパッドで読みましたが非常に時
間がかかりました。

 1億の直近の10個の 4n+1 型素数についての結果は次の通りでした。Rは、α2 がP以
下の平方数のなかで大きい方から何番目かを表します。

  素数P   α  β   R
99999517 , 7819 , 6234 , 2181
99999541 , 9890 , 1479 ,  110
99999589 , 9425 , 3342 ,  575
99999617 , 8129 , 5824 , 1871
99999677 , 7429 , 6694 , 2571
99999721 , 7795 , 6264 , 2205
99999773 , 8998 , 4363 , 1002
99999821 , 8765 , 4814 , 1235
99999941 , 7346 , 6785 , 2654
99999989 , 8458 , 5335 , 1542

 次に、1億以下を1000万で区切って、4n+1型素数のRについて調べました。

       区間       素数の個数 R=1  R=1の確率  Rの平均値
         1〜 9999999  332180 14427 0.043431272 205.6074658
10000000〜19999999 302990 8815 0.029093369 384.2761543
20000000〜29999999 293609 7491 0.025513523 497.7437851
30000000〜39999999 287908 6704 0.023285216 589.6343624
40000000〜49999999 283765 6309 0.022233186 669.4256903
50000000〜59999999 280218 5872 0.020955114 739.0882242
60000000〜69999999 278048 5655 0.020338215 803.9461064
70000000〜79999999 275655 5295 0.019208794 863.0004897
80000000〜89999999 274020 5075 0.018520546 921.0241588
90000000〜99999999 272111 4934 0.018132306 972.00692

  ※素数の個数は、4n+1型の素数の個数、R=1は、R=1の個数。

 k.nika さんが問題にされていた確率は、R=1の確率ですが、1億近くで2%弱です。50
個に1個近くがR=1だということで、かなり大きいとも言えます。因みに、1億以下で、R=1
となるもっとも大きい素数は「99998497」です。「99999989」から小さい方へ数えて35番目
です。1億と言えば普通にはかなり大きい数ですが、たかが108だとも言えます。このぐらい
の桁数なら今のコンピュータならごく単純なプログラムでも処理できそうです。1015ぐらいに
なるとどうでしょうか。「1000000000000037」は、Maximaで調べると素数で、4n+1型です。
これを、α2+β2 の形で表すα、βを求めることはできるでしょうか。


 k.nika さんより(平成22年8月3日付け)

 どうもありがとうございます。αの値と破綻する番号との因果関係が不規則で、悩んでおり
ました。早速らすかるさんの計算式をもとに、さらに発展させていきたいと思います。
 究極的には、4n+1型素数Pの値のみから、Y2+Z2 を求める方法を考えたいと思います。
また、FNさん、どうもありがとうございます。大変時間のかかる作業、感謝いたします。このデ
ータはとても助かります。R=1が50個に1個とはとても高い確率だと思います。R=1〜 が
それぞれ単純に同じ確率だとして、たとえば、ある 4n+1型素数Pが与えられたとして、R=
10まで計算していいとすると、5個に1個は、Y2+Z2 が求められるという事ですから、これは
すばらしいデータであると思います。あとは、「1000000000000037」を、Y2+Z2 に出来るよう
がんばります。


 らすかるさんが、より大きな素数について調べられた。(平成22年8月3日付け)

1015〜1015+1000 の中で、

1000000000000037=260435862+179368792 、R=5579191
1000000000000241=315012042+27702252  、R=121573
1000000000000249=304650322+84783152  、R=1157745
1000000000000273=315080972+26906922  、R=114680
1000000000000297=295925642+111481012  、R=2030213
1000000000000357=275491212+155256542  、R=4073656
1000000000000513=315066722+27073272  、R=116105
1000000000000613=236043672+210436182  、R=8018410
1000000000000741=281533752+144009542  、R=3469402
1000000000000873=230186082+216827972  、R=8604169
1000000000000921=294915152+114127362  、R=2131262

1016〜1016+1000 の中で、

10000000000000061=865612062+500715252  、R=13438795
10000000000000069=917853622+396919052  、R=8214639
10000000000000453=998384422+56820332  、R=161559
10000000000000481=957728092+287675002  、R=4227192
10000000000000597=914412892+404782742  、R=8558712
10000000000000613=968027832+250842822  、R=3197218
10000000000000669=876881902+480705872  、R=12311811
10000000000000753=982850172+184405922  、R=1714984
10000000000000793=804867232+593454922  、R=19513278
10000000000000861=998903942+46807252  、R=109607
10000000000000897=716434162+697654712  、R=28356585
10000000000000909=985548452+169393782  、R=1445156
10000000000000949=916700182+399575752  、R=8329983
10000000000000957=909308342+416122992  、R=9069167

1017〜1017+1000 の中で、

100000000000000013=2972771232+1078253782  、R=18950644
100000000000000021=2700348862+1645635452  、R=46192881
100000000000000049=2471462572+1972783002  、R=69081510
100000000000000081=2918514002+1217487592  、R=24376367
100000000000000141=2843135702+1384405792  、R=31914197
100000000000000181=3161457702+72008412  、R=81997
100000000000000337=3114901962+545330892  、R=4737571
100000000000000369=3156933002+183777132  、R=534467
100000000000000589=3092048422+662749252  、R=7022925
100000000000000609=3159407282+134705752  、R=287039
100000000000000669=2843667252+1383313622  、R=31861042
100000000000000781=2628725952+1757782662  、R=53355172
100000000000000817=2841500962+1387758012  、R=32077671
100000000000000889=2845247082+1380061252  、R=31703059

1018〜1018+1000 の中で、

1000000000000000009=10000000002+32  、R=1
1000000000000000177=7735718842+6337085612  、R=226428117
1000000000000000201=9960770992+884896202  、R=3922902
1000000000000000381=9433852852+3316989662  、R=56614716
1000000000000000621=8864616142+4628021252  、R=113538387
1000000000000000841=10000000002+292  、R=1
1000000000000000861=9073851152+4203001942  、R=92614886
1000000000000000877=9836528062+1800754212  、R=16347195
1000000000000000913=9777779832+2096430682  、R=22222018
1000000000000000997=9979645662+637708792  、R=2035435

 数が大きくなると、Rもどんどん大きくなりますが、1018〜1018+1000に、R=1が2つもある
のは奇跡的な感じがします。

 理論値を概算してみました。

 Nが大きい値として、α2+β2 がN以下になる組合せは、α>βとして約(π/8)N通りあり、
このうち、R=1となる組合せは約(2/3)N(3/4)通りあります。よってこの中に素数が均等
に出現すると仮定すると、N以下の素数で、R=1となる確率は、

   {(2/3)N(3/4)}/{(π/8)N}=(16)/(3πN(1/4))≒2.4/N(1/4)

となります。

  N<10000000 で 約0.043  、 N<100000000 で 約0.024

となりますので、FNさんが調査された値(約2%弱)とほぼ合っています。

 「R=1が50個に1個とはとても高い確率」について、確かにNの大きさの割にはそのよう
に思えます。4乗根ですからね。しかし、N→∞ のとき、(確率)→0 ですから、例えば、50
桁のような大きい数になると「ほぼ皆無」と言えますね。

 らすかるさんの結果に対して、FNさんからのコメントです。(平成22年8月3日付け)

 1015 ぐらいで大変かと思ったのですが、その辺は軽く超えて、1018 でもできますか。1025
ぐらいになればさすがにきついでしょうか。Excel では15桁までなので、1000000000000037
と入れると1000000000000030になってしまいます。いつまでも ExcelVBA ばかりではだめで
すね。今日VisualC++をInstallしました。使う気になるまで何日もかかりそうですが。

 4n+1型の素数Pは、2つの自然数の平方の和に書けるという定理の証明は読みました。
オイラーによるものと本質的に同じだそうですが、その証明は実際に2つの平方の和に書く
手順を与えます。しかし相当に面倒です。だから普通はPから平方数を引いていって、平方
数になるものを捜すのが実際的なようです。理論値というあたりの話は全くわかりません。


 らすかるさんが用いられたプログラムの概要です。(平成22年8月4日付け)

 4n+1=N に対して、α=[√N]、β=[√(N-[√N]2)] として、

  α2+β2 がNより小さければ、βに1を足す
  α2+β2 がNより大きければ、αから1を引く


以上2行を繰返し、α2+β2=N となったら終わり。

 乗算をしなくて良いように若干工夫はしていますが、基本は上記だけです。

 1015 あたりは一瞬ですが、1018 あたりでは時間がかかるもの(Rが大きいもの)は20秒
ほどかかりました。

 また、らすかるさんは、FNさんの「1025 ぐらいになれば、さすがにきついでしょうか?」とい
う問いかけに答えて、プログラムを作り直され、次の計算結果を得られた。

 新しいアルゴリズムでは、最後の10200+357 でも1秒もかかりません。

   参考ページ: http://ror.hj.to/r/blog/category/1/16/1

1025〜1025+1000 の中で、

1025+13=29976069710022+10071506577472
1025+349=29664515184432+10955206016902
1025+513=31199803650172+5154828046682
1025+561=23392985270152+21278351443442
1025+609=27030635758202+16411725397032
1025+657=30931786288562+6574541580892
1025+937=31525921115842+2473114998912

1050〜1050+1000 の中で、

1050+577=76110653438083542454504012+64862689068739216422454242
1050+709=92506034078701742684365782+37982017574505857528717752
1050+889=83604740837780774436549552+54865720713825601313931922
1050+897=91825791339743398110992312+39598283357109135513627442
1050+961=100000000000000000000000002+312

10100〜10100+1000 の中で、

10100+949
=996979214701385194475416564188485091846285240163822
         +77668819055070508451725982180298333694401232778952

10200〜10200+1000 の中で、

10200+357
=87342995146970964150923244222621726434876511735966
 100580445510752230595346527415586930628585747178742
        +48694981248134869822313779563554735739904013676676
         055344760129023715374107107898588166442850446621912

 FNさんからのコメントです。(平成22年8月4日付け)

 10200 あたりでも瞬時にできてしまうとは全く驚くばかりです。参考ページを読ませていた
だきました。

 中心は「4n+1型の素数が2つの平方数の和である」の証明(本質的にオイラーによる)で
した。やっぱり、オイラーは偉い。オイラーの証明はベストに近い見つけ方でもあったようで
す。A2+B2=MP から、a2+b2=mp を作るとき、m≦M/2 ですが、例としてあがって
いるケースでは、おおかた1桁落ちてますね。そこまでいかなくても2回で1桁ぐらい落ちそ
う。この部分は時間に関しては問題なさそうです。

次に、x2≡−1 を解くことですが、確かに原子根がわかっていれば問題ないです。(と言っ
ても仮に2が原子根だとして2(p-1)/2を計算するプログラムを私が書けるかと言えば書けま
せん。pが200桁ぐらいあるとして)では、原子根をどうやって求めるかですが、ここに書いて
あるのは、p−1を素因数分解してます。200桁ぐらいある数の素因数分解は一般には無茶
苦茶な時間がかかると聞いてます。試しにMaximaでfactor(10^200+356);を実行したら黙っ
てしまいました。しかし原子根はいっぱいあるから、2、3、5、・・・を (p-1)/2乗していって、
−1になるものを捜せばかなり早くみつかるのでしょう。

ということで理屈としてはできそうです。そのことと実際にプログラムを書くこととはかなり距
離がありますが。

 上の参考ページに参考としてあげてある次のページに、「4n+1型の素数が2つの平方数
の和である」の簡明な証明が書いてあります。証明だけであればこんなに簡単にできるのに
驚きました。ただ実際に2つの平方数をみつけるのには役に立たないです。やはりオイラーに
よる証明でないと。

 さらに一文証明(one-sentence proof)なるものが載ってますが、実際には確認すべきことが
非常に多く one-page proof ぐらいになりそうです。でもおもしろそうです。なお、明らかですが
一文証明の6行目のif x<2yはif x>2yの間違いです。


らすかるさんからのコメントです。(平成22年8月4日付け)

 私は最初そのページを見て、「桁数が多くなると素因数分解が困難になるからダメだ」と思
ったのですが、実際に試しているうちに、素因数分解は必要なく、また原始根を見つける必
要もないことに気付きました。

 FNさんのおっしゃる通りで、2、3、5、・・・を (p-1)/2乗していって−1になるものを探せば
良いだけです。(p-1)/2乗が−1になるものは原始根とは限りませんが、A=a(p-1)/4 とすれ
ば、A2+12=kp となるのですから原始根でなくても何も問題ありません。実際に手作業
で百個以上の素数で調べた中では、(p-1)/2乗して−1になるものが17までで必ず見つかっ
ていました。


 k.nika さんからのコメントです。(平成22年8月5日付け)

 らすかるさんからの質問:「なぜ、α<β に限定しているのですか?」について、

(α>β)において、β=4の場合、s =( n を(√f =α)に変えるための平方数 )とする。

番号 α β √f
41 10 2 25
65 16 2 12 49
97 24 2 20 81
11 137 34 2 30 121 11
13 185 46 2 42 169 13

 α>βの場合には、Nから最大平方を引くのではなくて、√f=αにするための n から引く、
あるひとつの平方数を求めなくてはいけません。よって、この場合は、R=1の確率は非常に
低くなってしまいます。もし、(α>β)の集合と(α<β)の集合のそれぞれのR=1を求める
とぜんぜん違う値になると思います。


 FNさんからのコメントです。(平成22年8月5日付け)

 一度原子根を求めたいと思っていたので、(p-1)/2乗して-1になるものとを調べてみました。
100万以下の素数Pについて2、3、5、・・・と調べて最初に見つかる原子根Gと、最初に見つか
る(p-1)/2乗が-1になるものFを調べてみました。ただし、4n+1型ではなくすべての奇素数
について調べました。

 F=2 となるものが半分ぐらいあります。最大のFは43でした。Fについては素数だけ調べ
れば十分です。小さい方から何番目の素数がFになるかの平均値は、1.991ほどでした。
4ん+1型だけで調べた方がいいですがほとんど差はないでしょう。平均して2つ目でみつか
るわけだから全く問題なしです。参考までに、19までについて、G=A、F=A の個数を書い
ておきます。

 
G=A F=A
29341 39276
17814 19644
10882 9828
4412
5455 4918
10 1847
11 2926 2466
12 259
13 1844 1220
14 630
15 342
17 921 610
18 36
19 579 303
20以上 1209 232
78497 78497

 また、「なぜα<βに限定しているのですか?」について、「α<βに限定してはまずいの
ではないですか」という意味だと思います。他の限定がなければα<βとしていいですが、
k.nika さんは、α、β の偶奇を決めておられますから、その上で、α<β とすると半分ぐ
らいが考慮の対象外となってしまいます。あとで、α>β のケースは考えようということでし
ょうか。


 k.nika さんからのコメントです。(平成22年8月6付け)

 あとで、α>βのケースは考えようと考えております。α>β のケースと α<β のケース
では、α の求め方がまったく違うので別々に考えた方がいいのでは?と思うのです。
α>βの集合について1億ぐらいまではR=1〜10までの確率は二桁(%)いくのではないか
と思っております。


 らすかるさんからのコメントです。(平成22年8月6付け)

 G=A、F=Aの個数は私も気になっていて、自分でも調べようと思っていました。今までの
方法でも十分効率が良いのですが、効率をさらに上げる方法に気づきました。

 もし、(p-1)/4 が偶数の場合、a(p-1)/4 が -1 でも良いわけですし、(p-1)/8 も偶数なら、
(p-1)/8 が -1 でも良いわけです。

 aN (mod p)を計算する場合、もともと (p-1)/2k=q (奇数)で、a (mod p)を計算し
てから2乗を繰り返していますので、上記の値は計算途中で既に得ています。

 よって、次のように処理すると効率良く計算できます。

 ・a を計算し、値が 1 か -1 なら、a を変更して繰り返します。

 ・a が 1 でも -1 でもなければ、これを順次2乗していけば、いつか -1 となり、その時の
  2乗する前の値がAとなります。

# もし、-1 とならずに 1 になったり、(p-1)/2乗まで計算しても -1 にならなかった場合は、
 元の数は合成数です。

 この改善策の効果は以下のようになりました。
(対象は10億以下の4k+1型の数で、上記の判断で合成数と判断されなかった合成数(=偶
然-1になったもの)もわずかですが含みます。)

【改善前】
a    F=a
2  12712640
3   6356290
5   3178525
7   1588828
11   794792
13   396771
17   198747
19    99633
(以下略、a は最大83)

素数1個につき約半分ずつになるのは    
FNさんの結果と同じ
  【改善後】
a    F=a
2   21187637
3    3329111
5     696713
7     160103
11     38502
13      9354
17      2192
19      510
(以下略、a は最大37)

 かなり改善されていることがわかると思います。改善前は平均2個目でしたが、改善後は
平均1.2個目です。改善後のプログラムで10500+1189を平方和に分けたら、実行時間は1
秒でした(改善前は1.6秒)。因みに、10500+1189は、10500より大きい2番目の素数です。
1番目は10^500+961なのですが、これは分解結果が、(10250)2+312 となってあまりにも面
白くないので次のを探しました。ここら辺になると、素数を探すのも大変ですね。


 k.nika さんからの新しい問題提起です。(平成22年8月17日付け)

 またひとつ ご教授頂きたい事がございます。違う方法を考えてみました。

 2つの4n+1型素数を、Pn、Pm とし、 Pn=A2+B2 、Pm=C2+D2 とする。

 Pn・Pm=Q とし、Q の値のみ与えられているものとする

 Qを平方和に分けるアルゴリズムを用いて、2種類の平方和 Q1、Q2 に分ける。

ブラーマグプタの二平方恒等式- Wikipedia

  Q1=(AC - BD)2+(AD+BC)2 、Q2=(AC+BD)2+(AD - BC)2

このとき

 (1) この2種類以外平方和は存在しないのか。

 (2) この2種類の平方和は、ブラーマグプタの二平方恒等式の内容と一致していると見
   て良いのか。

 (3) 探し出した4つの平方数から、どれが(AC - BD)で(AD+BC)であるとか調べる方
   法はあるのか。(これは分かればラッキーという感じです。)

 以上3点になります、これが肯定的に分かれば、うまくすれば素因数分解の桁数を減らせ
そうな気がするのですが・・・どうぞ宜しくお願いいたします。



 この問いかけに対して、らすかるさんからのコメントです。(平成22年8月18日付け)

 (1) この2種類以外平方和は存在しないのか。

   4n+1型の2素数の積であれば、実質的に2通りしか存在しないはずです。

 (2) この2種類の平方和は、ブラーマグプタの二平方恒等式の内容と一致していると見
   て良いのか。


   2通りですから、一致していると思います。

 (3) 探し出した4つの平方数から、どれが(AC - BD)で(AD+BC)であるとか調べる方
   法はあるのか。


   (AC-BD)と(AC+BD)の偶奇は同じ、(AD-BC)と(AD+BC)の偶奇は同じで、

     (AC-BD)<(AC+BD) 、 (AD-BC)<(AD+BC)

   ですから、CとDの入れ替えを除けばただちにわかりますね。

 ただし、問題は大きな合成数の場合は平方和に分けるのが困難であるという点です。

 例の平方和に分けるアルゴリズムは、素数の場合は、−1の平方根が容易に見つかりま
すので巨大な数でも高速に処理できますが、合成数の場合はそうはいきません。もし、−1
の平方根が容易に見つかるのであれば、平方和に分けなくてもただちに素因数分解できま
す。

 このことについて、k.nika さんからのコメントです。(平成22年8月19日付け)

 平方和に分けるには、−1の平方根を求める必要があり、−1の平方根が見つかれば、
平方和に分ける必要はないとは困りました

 では、そういう難しい議論はとりあえず抜きにして、2つの4n+1型素数の積を、方法は問
わず2種類の平方和に分ける事が出来たという流れで、私の気がついた事について書かせ
て頂きたいと思います。

 まず、2つの4n+1型素数を、Pn、Pm とし、 Pn=A2+B2 、Pm=C2+D2 とする。

 次に、 Pn・Pm=Q とし、Q の値のみ与えられたとする

 Qを2種類の平方和に分ける。

  Q1=(AC - BD)2+(AD+BC)2 、Q2=(AC+BD)2+(AD - BC)2

 次に、以下の計算をする。

   ((AC - BD)+(AC+BD))/2=AC

   ((AD - BC)+(AD+BC))/2=AD

   ((AD+BC)-(AD - BC))/2=BC

   ((AC+BD)-(AC - BD))/2=BD

   AC+AD+BC+BD=( A+B )( C+D )

 ここまでの目的は、 (A2+B2)(C2+D2)を(A+B )( C+D ) の形に変える事です。

 次に、(A+B )( C+D )を既存の素因数分解プログラムで解く。

   (A+B )( C+D )= Fa×G×H×I×・・・

 次に、その素因子をいろいろ組み合わせて、以下の式に入れて割り切るまで試す。

 たとえば、 ( 4+5 )( 7+8 )=135=3×3×3×5=(3×3)(3×5)とする。

 まず、(3×5)を( C+D )であると仮定して、

   {(AC + AD)2+(BC+BD)2}/(C+D)2=A2+B2

 これで、Qを割ってみて割り切れれば正解になります。(以上)

 この計算で、うまくいけば、たとえば200桁の計算を100桁強ぐらいにまで落とせるので
はと思うのですが...。なにか計算ミス、見落とし等あればご教授頂けますよう、宜しくお
願いいたします。


 らすかるさんからのコメントです。(平成22年8月19日付け)

 間違いはないと思いますが、AC、AD、BC、BDが出れば、

  Aは、ACとADの最大公約数 、Bは、BCとBDの最大公約数、

  Cは、ACとBCの最大公約数 、Dは、ADとBDの最大公約数

ですから、さらに素因数分解する必要はないですね。

実例  790037は、790037=712+8862 、790037=6262+6312 の2通りに書ける。

 偶奇が同じ組の和と差の半分を求めて、

 (631+71)/2=351 、 (631-71)/2=280 、 (886+626)/2=756 、 (886-626)/2=130

 GCD(351,756)=27 、GCD(280,130)=10 、GCD(351,130)=13 、GCD(280,756)=28

  ∴ 790037=(272+102)*(132+282)=829*953 のように求められる。

 因みに、 X2≡−1 (mod 790037) となる790037/2以下の2数は、157756 と 255915です
が、これらがわかっていれば、

  GCD(790037,255915+157756)=829 、GCD(790037,255915-157756)=953

のように素因数が求められます。


(追記) 平成22年9月20日付け

 この話題については、k.nikaさんのHPサイト「4n+1型素数の部屋」をご覧ください。
分かり易く説明されています。



  以下、工事中