流れる空の中で数学を。

とある数学好きの「手作りすうがく」と「気ままな雑記」。

【素因数分解】分解長という概念を導入してシミュレーションしてみた【RSA暗号】

Python RSA暗号オリジナルプチ研究数論素因数分解数学

素因数分解

素数 $p,q$ に対して、 $N=pq$ を考える。このとき、 $q-p=d(N)$ が分かっていれば、

$N=pq=p(p+d(N))$

$p^2+d(N)p-N=0$

$p=\frac{1}{2}(-d(N)+\sqrt{d(N)^2+4N})$

と求まる。

プログラム

$N$ が半素数の場合のみ出力している。

giste505f5b0bfc142369b1c51f116aabf10

計算結果

$N=1\sim1000$ の計算結果

f:id:FoxQ:20210824194025p:plain — N＝１～1000までのd(N)

$N=1\sim10^4$ の計算結果

f:id:FoxQ:20210824194159p:plain — N＝１～10^4までのd(N)

塗りつぶされていしまったので、 $d(N)\le N/100$ の場合のみを出力してみる。

f:id:FoxQ:20210824194436p:plain — N＝１～10^4までのd(N)<N/100

結論

規則性はなさそうだ。残念！

おまけ(3次元プロット、 $(p,q,D(N))$ )

プログラムを3次元のプロットに拡張した。

gistd196b3f0c353cf106c67c9815a04aa36

f:id:FoxQ:20210824204946p:plain — (p,q,D(N))の3次元プロット

当たり前と言えば当たり前だが、規則性が見えた。ただし、 $p,q$ の情報は事前にわかっていないので、この種のプロットはあまり意味がない。

おまけ２(2次元プロット、 $(p,q)$ )

赤線は、 $q=5000/(p-1)$ 。より一般には、 $q=\frac{N}{2(p-1)}$ でだいたいフィットできそう。

f:id:FoxQ:20210824211118p:plain — (p,q)の二次元プロット