元祖ワシ的日記

フェルマーによると、3で割ると１余る素数は

x^2 + 3y^2

（ただしx, yは整数）と表すことができるそうな。

というわけで、先日見つけた素数

5316666001

は 3n+1型なので、そのように表せるわけですが トリビアルなやりかた（１から順番に探していく）方法だと、結構大変。特に素数がでかくなると、計算量が半端ないようで。

答え分かりますか？

72151^2 + 3*6080^2 = 5316666001

まずは x^2 + 3 = 0 (mod p)なる xを探すところから始まるわけですが、 特定の型ではうまく言っても、一般的にとなるとこれが結構しんどかった。

原始根の指数との対応が求まれば簡単に計算できるのだけど、指数を求めるのは 計算として難しいと言われていること（DH鍵交換はこれが計算するのが難しいという 大前提で成立している）

散々悩んだ末、p-1の素因数の和くらいのオーダで計算ができるようになりました。 p-1が大きな素因数を持っていないなら、これなら100桁くらいでも大丈夫でしょう。

こういうのを考え始めるとキリがないなぁ。楕円関数使うともっと効率よさそうなのがありそうだけど、考えるのが面倒なのでペンディング。

なお4n+1型の２つの平方の和で表すほうはとても簡単に求まります。ハイ

追記）
確率的アルゴリズムを用いればp-1の素因数が大きくても問題ないです。詳しくは関連を

もし話し合いというのを許すなら、4人の場合は次のようにすればよいでしょう。 １）A、BとC、Dのグループにわける。 ２）A、B連合は相談して山を二つに分ける。 ３）C、D連合は相談してどちらかの山を先に選ぶ。 ４）あとは、それぞれの山を二人で先ほどのように分ければよい。 しかし話し合いをしているヒマすらないという場合も考えられますし、 そもそも決裂してしまったら意味がない。しかも3人の場合はどうするんだ？ とか考えると、もっとよいやり方があるのかなぁ・・と １）Aが3つに分ける。 ２）Bが1つの山を選ぶ ３）Cがさらに1つの山を選ぶ。もし、B、Cが別の山を選べば、それで確定。 ４）B、Cが同じ山を選んだとすれば、Aは残りの山のどちらかから1つ選ぶ。 ５）残った2つの山を1つにまとめ、Bが再配分。先にCが選び、残りをBとする。 これでいいような気がするけど、ちょっと問題があるんですよねぇ。 100の宝石を分けるとき、Aが１，49，50と分けたとします。 B、Cが二人とも50を選ぶことはありません。Bが選んだあとCも50を選ぶとすると、Aは４9を選ぶことになり、その結果B、Cは51を二人で分け合うことになるからです。これは損です。 よって、Cは49を選ぶしかない。つまり、このケースではBの選択権が強すぎて、 Cはどう転んでも最大利益の50を選ぶ権利がありません。 じゃぁ、B、Cが同じのを選択したときはCに権利があるとすると、 今度はCの選択権が強すぎてBはどう転んでも50を選べない。 よってこの方法では手詰まりです。 なんかもっとうまい方法はないですかねぇ？じゃんけんすれば一発という解答はなしの方向でｗ

2^11-1	23 * 89
2^23-1	47 * 178481
2^29-1	233 * 1103 * 2089
2^41-1	13367 * 164511353
2^43-1	431 * 9719 * 2099863
2^47-1	2351 * 4513 * 13264529
2^53-1	6361 * 69431 * 20394401
2^59-1	179951 * 3203431780337
2^67-1	193707721 * 761838257287
2^71-1	228479 * 48544121 * 212885833
2^73-1  439 * 2298041 * 21514198099633918969?
2^79-1	2687 * 202029703 * 224958284260258499201?
2^83-1	167 * 57912614113275649087721?
2^97-1	11447 * 13842607235828485645766393?
2^101-1	7432339208719 * 341117531003194129?
2^103-1	2550183799 * 3976656429941438590393?
2^109-1	745988807 * 870035986098720987332873?
2^113-1	3391 * 65993 * 23279 * 1868569 * 1066818132868207?
2^131-1	263 * 10350794431055162386718619237468234569?

def gcd(a, b)
  while true
    if a > b
      a %= b
      return b if a == 0
    else
      b %= a
      return a if b == 0
    end
  end
end

def gcd(a, b)
  while true
    if a > b
      return b if (a %= b) == 0
    else
      return a if (b %= a) == 0
    end
  end
end

def gcd(a, b)
  while true
    return b if (a %= b) == 0
    return a if (b %= a) == 0
  end
end

int gcd(int a, int b)
{
    while(1){
	if(!(a %= b))
	    return b;
	if(!(b %= a))
	    return a;
    }
}

補足） p次の円分多項式は p-1の素因分解と大きな関係があります。 今回はp=11なので 10 = 2 x 5 故に2乗根（平方根）を求め、5乗根を求めることで、根を求めることができました。 同じ原理で考えれば、もしp=13なら平方根2回と立方根を1回で解くことができます。 同様に、 p=17ならば平方根4回 p=19ならば平方根1回と立方根2回 p=23ならば平方根1回と11乗根1回 p=23のときは11乗根は11通りの選び方があり、その選択肢も多いのですが、これは実際に値を計算をしてと同じになるものを選ぶ以外の方法を知りません。昨今は三角関数などすぐ計算できるので、とりあえずそれで計算するのがよいかなぁと。 また、解くためには p-1の素因数の累乗根が必要ともなりますが、 p-1の素因数の累乗根は既知であるとしても何ら問題はありません。 （数学的帰納法で証明可） 一般に、奇素数pに対し、p-1は偶数ですから最初の拡大は必ず平方根にすることが可能です。 そしてこの平方根は必ず √pまたは√-pとなります。 もっと具体的に言えば、4n+1型の素数は√pに。4n-1型は√-pになります。 もしpが 2^(2^n) + 1型の素数であれば、平方根だけで根を求めることができます。 そのような数は 3, 5, 17, 257, 65537 です。平方根は定規とコンパスで作図可能なので、上記の正多角形は定規とコンパスだけで作図可能ということになります。 最後に数を並べる時ですが、これは原始根にそって並べます。 たとえば11の原始根は2ですので1から始めて2倍2倍で並べてゆくと(11を超えたら11を引く） 1, 2, 4, 8, 5, 10, 9, 7, 3, 6 といった列ができます。この列を1つおきに並べると 1, 4, 5, 9, 3 2, 8, 10, 7, 6 となります。これがB0,B1の正体です。 余談） C0, D0, E0, F0の選び方はそれぞれ5通りあります。したがって全体としてはで5^4 = 625通りの選び方があることになります。 C0の一つの解をηとすれば、他の4つの解はησ、ησ^2、ησ^3、ησ^4です。 D0, E0, F0も同様です。 ところで、 ξ^4 = (B0+σ^4C0+σ^3D0+σ^2E0+σ^1F0)/5 ξ^5 = (B0+σ^3C0+σ^1D0+σ^4E0+σ^2F0)/5 ξ^9 = (B0+σ^2C0+σ^4D0+σ^1E0+σ^3F0)/5 ξ^3 = (B0+σ^1C0+σ^2D0+σ^3E0+σ^4F0)/5 です。 したがって625通りの組み合わせの中にξ,ξ^4,ξ^5,ξ^9,ξ^3が現れることになります。 すなわち625通り中、5通りだけが 11乗根の解を与えることになります。 試しにその625通りの根を複素平面上に図示してみました。 正五角形の頂点が根の候補で、赤い○をつけたところが11乗根（の半数）です。 角頂点は4個の正五角形の頂点となっています。図では一番小さい五角形の頂点を線で結んでみました。 なんとも意味深な模様ではないでしょうか？