元祖ワシ的日記

ひらめいたのでメモしておく。

3n+1型の素数Pは x^2 + 3y^2 = P と表すことができる。 その証明は代数学の環論でされるわけですが、数学者というのは証明しちゃったあと 具体的にそれを求めるアルゴリズムをちゃんと説明してくれないから困るわけで。

このやり方をずーっと考えていました。

自明なやり方は1..P-1までの数全てについて、試してみる。所詮数は有限だ。 しかし、これは、Pが大きくなると数が多くなり結構大変です。

オイラが出した手法は次の通り。

step 1) x^2 + 3 = 0 ( mod p)

の解を解く。つまり x^2 + 3 がpで割り切れるのだから、x^2 + 3 = npである。(nは整数)

step 2) step1の式は

x^2 + 3y^2 = np でy = 1としたものである。ここから、頑張ってより小さい x, y, nを探してゆき、最終的に nを１にする。

この二本立て。

さて、アルゴリズム的には STEP2のほうがすぐ思い付いた。

これは二次体の整数 K(√-3)を考えれよい。この世界では左辺は

(x-y√-3)(x+y√-3) = np と因数分解できる。

左辺は共役でn, pで割り切れないから、右辺のnもpも共役な積に分解されるはずである。

ここで証明をはしょって結論だけかけば、nは 3n+1の形の素数((a-b√-3)(a+b√-3)と分解可)、3(=√-3*√-3)、4(=(1+√-3)(1-√-3))、の積である。

故にこれらの因数で左辺の２項のどちらかが割り切れる。 (例えばnが素因数として 4を含むなら (x-y√-3), (x+y√-3)のどちらかが(1+√-3)で割り切れるはずだ。

このようにして、どんどん分解していけば最終的に求める式が求まる。

で、問題のSTEP1ですが、こちらはこうやる

x^2 = -3 ( mod p)

を求める。

ところで、 3n+1の素数Pの原始根をeとすれば n=P-1乗すると1になるのだが、これは3で割り切れるから、mod Pでは1の三乗根がある。これらの数は nを三等分したところ、すなわち

e^(n/3)

e^(2n/3)

である。これをωとω^2とおけば

ω + ω^2 = -1

に注意してその差の自乗を計算すると

(ω - ω^2)^2 = (ω^2 + ω - 2ω^3) = -3

故にω - ω^2 が答えである。

(ω - ω^2)^2はいわゆる判別式。

ω + ω^2 = -1となるのは

ωはx^3 - 1の根であり、自明な根１をくりだしてやれば

x^3 - 1 = (x-1)(x^2 + x + 1)

第二項が０になるはずだからω^2 + ω +1 = 0

このあたり円分多項式とかなり関連があるわけで、 このようにリンクするのがまた面白い。

例 素数2011を考える。原始根は3である

ω= 3^670 = 205 ω^2 = 3^1340 = 1805

故にその差 1600 = -411 (mod 2011)がSTEP１の解。実際

411^2 + 3 = 84 * 2011

である。 84は 4*3*7と因数分解できる。7は3n+1型だから、(x+y√-3)(x-y√-3)の形に 表せる。4も3も同様。実際に割って行くと

44^2 + 3*5^2 == 2011

を得る。

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

1.5年ぶり。

今回は3日目の東館。 蒸し暑そうだな。。。

まだ２週間以上もあるけれど、昨日帰宅後頑張り、とりあえず本らしきもの(第１稿)が出来たので、多分出展は間違いないでしょう。ということでアナウンス。

内容は

「正６５５３７角形作図法」

こちらのエントリを詳しくまとめたものです。結果はもちろん、導出方法の解説をも載せています。ちなみに、全部の式を載せると３００ページを越えますが、幸い式は規則的なので頑張って圧縮。２４ページに納めました。

今までの流れにのっとり一冊３００円くらい売ります。

なお、自分軟弱なんで在庫が捌けたら撤収すw お求めはお早めに。

16人でマージャン大会をすることになりました。 (基本事項だと思いますがマージャンは４人でします)

誰もが他の人と(少なくとも一回は)卓を囲むとすれば最低何局必要 でしょうか？(どのように大局を組めばよいでしょう？)

なお、捕捉しますと Aさんが B,C,Dさんと試合すれば、B,C,Dさんについてはクリアしたことになります。 (つまり A,B,C,Eのような試合をしなくてもよい)

前mixiかどっかに書いたような気もするけど、再掲。

Aさんにしてみれば、自分以外の人は15人いるわけですから、3人づつ相手を入れ換えていけば、Aさんは最低５局しなければならないのはすぐわかると思います。 うまい組合せを考えて、BさんCさんDさん...も５局でおさまる...ようなものはあるでしょうか？

なお卓は４つあり、４試合同時進行が可能です。 出来る限り同時進行をして早く終らせたいというのもあります。

ヒント

答えは各人が５局(のべ２０局)になります。しかも４卓同時進行できる すばらしい組合せがあります。

これは組合せを力技で考えても解けないでしょう。 GF(4)の体を考えないと解けない。体をしらなくてもCRCを知ってれば解けるかも。

次回のコミケのネタは正65537角形作図法にしようかなと。 マニアックすぎるかなぁ？ｗ

ということで、まずはネタフリ。

今回は正15角形。

定規とコンパスだけで作図可能な素数の正多角形は 3, 5, 17, 257, 65537です。それより大きい作図可能な正多角形が あるのかどうかは分かっていません。

そしてそれらの数を掛け合わせた数もまた作図可能です。 ただし１つの数は1回しか使えない。つまり、正9角形は作図できないけど、 正15角形は作図可能なのです。その理論でいえば作図できる最小の奇数の正多角形は 4294967295角形ということになりますね。

で、やり方ですが、正三角形と正五角形が作図できる人なら結構簡単です。 実際、正三角形と正五角形が正15角形には含まれるので、図の X₅とX₆が正15角形の弧になるから、これをもとに円を区切っていけばokです。

それで解決といえば解決なのですが、しかしまた、 以前にも書いたように、これは方程式、

x¹⁵-1=0　--(1)

の根と関係があります。それはガウス平面に書けば、半径1の円上の点を15等分した点になります。

「定規とコンパスで作図が出来る」ということは 「方程式の係数からはじめて、平方根と加減乗除を繰り返すだけで解が求まる」 ということと同値。

故に(1)が方程式として解けることに他なりません。 そこで今回はこれをといてみようかなと。

まず(1)式を因数分解。 自明な解1があるから、(x-1)で因数分解できるのはガチ。

残りですが、 3乗根および5乗根もまた根になることがわかっているので (x²+x+1)および (x⁴+x³+x²+x+1) で因数分解できます。 計算してみると

x¹⁵-1=(x-1)(x²+x+1)(x⁴+x³+x²+x+1)(x⁸-x⁷+x⁵-x⁴+x³-x+1) となります。この4項目の8次方程式

x⁸-x⁷+x⁵-x⁴+x³-x+1 --(2)

が解けてしまうのです。どうみても解けそうにないこの式が解けてしまうというのは なんとも不思議です。この式の8根は、ガウス平面状のX₁, X₂, X₄, X₇, X₈, X₁₁, X₁₃, X₁₄になるのはわかっています。つまり

(2)=(x-X₁)(x-X₂)(x-X₄)(x-X₇)(x-X₈)(x-X₁₁)(x-X₁₃)(x-X₁₄)

右辺を展開すれば

x⁸-(X₁+X₂+X₄+X₇+X₈+X₁₁+X₁₃+X₁₄)x⁷ +...+X₁X₂X₄X₇X₈X₁₁X₁₃X₁₄

だから(2)式とx⁷の項と定数項の係数を比較すれば

X₁+X₂+X₄+X₇+X₈+X₁₁+X₁₃+X₁₄=1

X₁X₂X₄X₇X₈X₁₁X₁₃X₁₄=1

となります。

ここでちょっと中断して基本事項の確認。

X₅, X₁₀は1の3乗根（つまりω）、すなわち x² + x + 1の解だから、 。
また、X₅ + X₁₀ = -1。

X₃, X₆, X₉, X₁₂は1の5乗根、すなわち x⁴ + x³ + x² + x + 1の解だから、全部足すとやはり-1。

これを踏まえて次のステップにいきます。

A₀=X₁+X₂+X₄+X₈
A₁=X₇+X₁₁+X₁₃+X₁₄

とすれば

A₀ + A₁ = 1

です。一方　A₀A₁を計算してみると

(X₁ + X₂ + X₄ + X₈)(X₇ + X₁₁ + X₁₃ + X₁₄)
=(X₁ + X₂ + X+4 + X+7 + X+8 + X₁₁ + X₁₃ + X₁₄)+ (X₃+X₆+X₉+X₁₂)+4X₁₅
=1 -1 + 4 =4

故にA₀, A₁は x² - (A₀+A₁)x + A₀A₁、すなわち x² - x + 1の根で



次に

B₀ = X₁ + X₄
B₁ = X₂ + X₈

とすれば

B₀+B₁ = A₀

B₀B₁ = (X₁+X₄)(X₂+X₈) = X₃ + X₉ + X₆ + X₁₂ = -1

故に同様に計算すれば



最後に

X₁ + X₄ = B₀
X₁X₄ = X₅ = ω

だから



となります。これが解(の１つ。そして偏角が最小のもの)。式で書くと



根号の符号をどちらに取るかという問題があるけれど、正しく選択すればX₁が見事に求まります。

なおgoogleで計算するとこうなります。→検算結果

その必要条件は何か？という問題。

まずmod3で考えることにより

2^n+1 ≡ (-1)^n+1 (mod 3)

nが奇数のときは右辺は0になるので、必ず3で割り切れる。故に素数にはなりえない。 ということでnは偶数であることがいえます。

n = 2^(k * 奇数)

ならば

2^n + 1 = (2^k)^(奇数) + 1

となるので、mod 2^k+1で考えれば右辺は0になる。故に素数にはなりえない。 例えば2^12+1 = 4097は 16^3 + 1だから17で割り切れる。

ということで肩の指数は 2^kの形である必要があるわけです。 まぁつまりフェルマー数ということですな。

小さいほうから書いていけば

3, 5, 17, 257, 65537, 4294967297, ...

このうち素数なのは65537まで。その先に素数があるかどうかは 未解決問題。

こういうタイトルでいいのかどうかわからないけれど、こういう問題す。

二人の盗賊が宝石の山の宝を盗み出した。追っ手が迫ってるので、 素早く納得いくように分けたい。秤など使わないで、平等に分ける方法はあるか？

答えとしては以下のようになります。

１）盗賊Aが宝を均等と思われるところで二つの山に分ける。

２）盗賊Bがその山のうち特だと思われるほうを先に選ぶ。

ここまでは有名。 この問題をn人に拡張できるのか？というのが最近考えています。

これが結構難題。

たぶん答えはあるんですが（ググるとそれらしきものにヒットするしね～） 解答を見たら負けということで。

もし話し合いというのを許すなら、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を選べない。 よってこの方法では手詰まりです。 なんかもっとうまい方法はないですかねぇ？じゃんけんすれば一発という解答はなしの方向でｗ

TeXの数式をそのままgifにしてくれるという　mimetex

こんなものがあったのか。便利だのう。思わず沢山書いちゃうな。これは。







しかし昔とった杵柄というのは恐ろしいモノですね。悩まずにTeXで式が書けてしまうｗ

世間一般には『メルセンヌ素数』の発見に興味があるようですが、 あえて素数ではないメルセンヌ数を素因数分解してみました。

？はそれ以上分解できるかもしれないやつ。

101で30分くらい。ちなみにリストにない137は結構強敵で、自分のアルゴリズムだとなかなか素因数をみつけられません。

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?

超有名な最大公約数を求めるアルゴリズム。 その理論はともかく、rubyで書くなら

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

こんなもんですかね？Cなら

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

それにしても紀元前にこのアルゴリズムを考えたユークリッドはすごいわ