Post-Quantum 狂想曲 前夜

第2話 奇妙な因数分解

　宿題は,やってきたかな？　

　あちこち,不調で,更新が遅くなってすまんのぅ.

　RSA暗号では,巨大合成数の素因数分解が重要だということは,わかったんじゃなかろうか.

　数式処理ソフトの,計算精度は,200桁程度に設定しておこう.

　ＰＣの浮動小数演算ユニットを利用できる設定にしておこう.

　必要なパッケージは,適宜読み込んでおくことじゃ.

　さて,p,qを巨大な素数としよう.それぞれ50桁程度としておこう.

ここで　p <q として　q/p　=ほとんど整数　例えば3とする.　qは3*pに最も近い素数になる.

p, q は素数だから　q/pは　2.99999999..............9936....... とか3.000000000000000.....00182......

等,３に非常に近い数値になる.これをRとする.

　選んだp, q が素数かどうかは,素数判定関数で,チェックしておいて欲しい.　適当な大きい数をの「次の素数/前の素数」関数を使ってもいい

N=pqとする.NとR=q/pが既知なら

　p=sqrt(N/R)に最も近い素数　　　

　q=R*sqrt(N/R)に最も近い素数

検算すると

　p*q= R*(sqrt(N/R)^2

= R*N/R

=N

　ここでsqrtは平方根を求める関数じゃ

m=2^b*2^c　とする

r=m/(2^b)とする

これは,後の都合で,2のべき乗で指定する.

ここはLaTexが使えないのは,不便じゃな.　式が書きづらい.

-----------------------------------

j=1

for s from -m to m by r do

if frac(N/(q+s)）≦　0 then f[j]=1

else

f[j]=frac(N/(q+s)）

end if

　ｊ＝ｊ＋1

end do

----------------------------------

　計算は,これだけじゃ.　処理系によって,文法が異なるので,適当にやってくれ.

-mからmまでsをrずつ変えて割り算をして,答えの小数部分を取り出しているだけじゃ.

if文は　結果を表示するときに対数目盛りを使うから,log(0)がエラーにならないための例外処理じゃ.

fracは割り算の小数部分だけを取り出す関数じゃ.　処理系によって名前が違うので、相当する関数を使って欲しい。

s=0のときNはqで割り切れるのでf[j]=0となる.

このデータを横軸s,縦軸f[j]でグラフを作って欲しい

b=8,c=0程度でやってみればいい. 512点のデーターができるはずじゃ

縦軸は,対数目盛りのほうが,わかり易いグラフが描ける.

f[j]が0になると対数がエラーになるので,適当な例外処理が必要じゃ

s=0のところで段がついた,振動するグラフが描けたはずじゃ.

s=0のところで,fはゼロとなって割り切れる.

では,　b=8　c=75として同じようにグラフを描くと,,逆三角形のグラフができるはずじゃ.

グラフの範囲は±10^25程度になっている.

　気をつけて欲しいのは,このグラフは細部が,描かれていない点じゃな.　分解能と走査範囲は両立しないのじゃよ.　c=0以外では,グラフは,サンプリングした値がプロットされることになる。.

この逆三角形は,s=0を中心に,両側10^24程度の幅がある.

　今日の宿題は,この広がりが何を意味するかじゃ？

　数式処理系の使い方の練習に,p, q, Rを色々変えて試してみるのじゃ.

　素因数分解は普通,「数体ふるい」など,数論を使うから,こんなばかばかしい方法は使わない.　q+sを法とした剰余（mod）を使うから浮動小数点演算は使わないのじゃ.

mod演算でも同じような結果が出るが,ハードの演算機能を使ったほうが速いのじゃ.

実際に,何をしているか,数式処理システムがなしで読んでいる者には,わからんじゃろぅ.

おぬしらに忠告しておく. 決して糠喜びはしないことじゃ.　暗黙のうちに、知らないはずのpとかqとかRのデータを、使ってしまっていたとか、よくあることじゃ.