Post-Quantum 狂想曲 前夜

第4話 困ったときの

　グラフを見ると,周期性があるように見える.周期性といえばフーリエ変換じゃな.

　数式処理系にはたいていフーリエ変換の関数かパッケージが用意されている.

　b=8,c=0　で作ったデータを離散フーリエ変換してみぃ.これは一般に複素数じゃ. 扱いがっ面倒なので,変換したデータの各点の値と,共役な値を掛け合わせると,実数になる.

これのグラフを,作ってみるのじゃ.

　R=3で作ったデータをフーリエ変換してパワースペクトルにすると,3に対応した位置に高いピークが出る.　R=4でデータを作ると4に対応した高いピークが出る.

　ここで,R=3でNを作ってR=4と仮定した推定値で計算したデータをフーリエ変換する,R=4に相当する小さいピークが出る.

　しかし,これだけでは,あまり役に立たないのじゃ. n桁程度のqx=q+n/2桁程度の偏差なら,フーリエ変換で大きなピークが出るが,偏差が大きくなると,中途半端な大きさのピークになるので,qxが推定できんのじゃ

　ここで,R=3のデータに対してR=3.05とR=2.95と仮定したデーターを作ってみる.　そうすると,それぞれ,R=3.05とR=2.95に対応した位置にピークが出る.　このピークをよく見ると,裾野が少し広がっているのじゃ.　R=3に対してR=4.05やR=3.95を仮定したデータでは,ピークの裾野は,あまり広がっていない.

　R=3の場合　R=3.1あたりから裾野が広がって,R=3.05あたりで広がりが最大になって,R=3.01以下では裾野が広がらなくなる.R=3でピークが大きくなるが,これはq/pがほとんど3になっている場合で,ちょっとでもずれると,ピークは大きくならない.R=2.99あたりから,裾野が広がり始めて,R=2.95あたりで,広がりが最大になる.　このことから,Rは2.95から3.05の間にあることがわかる.

p, q　が50桁程度とすると,下25桁と上3桁は推定できることになる.

　あと22桁を何とかすれば,使えるアルゴリズムになるんじゃが......

運がよければ,フェルマーの因数分解を使うと,解けるかもしれん.　素因数分解の答えは,たぶんRの（上限+下限）/2の付近にある確率が高い.

　グラフを使う方法で答えが見つからない場合は,グラフの上限から上向きのフェルマー法と,グラフの下限から下向きのフェルマー法で計算を進めるのじゃ. グラフの利用で下n/2桁を計算する手間が省けるのじゃ.

もし,残りの桁数を推定できる方法を見つけても,公開するのはご法度じゃ.

公開は,ポスト・クァンタム狂想曲が落ち着いてからにしたほうがええな.

　ここに書かれたことがフェイクかそうでないかは,手を動かして,コードを実行した者だけが判断できるのじゃ.

N/(q+s)の小数部分のデータがq/pを内包していることは,数学の神秘を感じるのじゃ.

　FFTによる高速乗算アルゴリズムというのがあるんじゃが,あの逆で,因数分解はできんものじゃろうか.

　そういえば,AIを補助に使った因数分解もあったのう.　AIに,あの周期的なグラフを学習させれば,正しい方向が「増」なのか「減」なのかだけでも教えてくれればいいんじゃが.

　AIのやることは,人間には理解しがたい.　碁の計算は, 二種類の原子AとBが交互に飛んできて基板に吸着するときの最低エネルギーの計算と等価かもしれんのじゃから.

フェルマーの因数分解で、面白いことに気づいたんじゃ。　フェルマーの因数分解の過程をグラフにすると, 　2つの曲線の交点のy座標が、q/pが3のときに限りpと等しくなるんじゃ。　これも、何かヒントになるかもしれん.

諸君の健闘を祈る.

おや？　誰か来たようじゃ　ちょと待っておれ　　ワァ　何をす#&~!?%