元祖ワシ的日記

フェルマーによると、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の素因数が大きくても問題ないです。詳しくは関連を