　前回,グラフは正しい関係のp, q, R, Nを使っておったが,今回は変な計算をしてみる

例えば,qx＝q+10^25　として, Nx=p*qx とする.

ここで,Nxだけ与えられて,qx/pxは３に非常に近いという情報を知っていたとする.

計算が合わないのは承知の上で,とりあえずpxとqxの推定値を計算してみる.

　ps=sqrt(Nx/3)に最も近い素数　　　

　qs=3*sqrt(Nx/3)に最も近い素数

として, f[j]=frac(Nx/(qs+s)）のグラフを描いてみる.

そうすると,s=0以外の部分に,逆三角形のグラフが描かれるはずじゃ.

ps*qs=Ns≠Nxじゃから,Nxはpsでもqsでも割り切れんのじゃ.　その代わりに,逆三角形のグラフの最小値のsから,qx=ps-sになっているのじゃ.　正しくない計算をしたら,正しい答えが,別の位置に現れただけの話じゃ.

　qsを調整して,三角形の頂点が,s=0の位置に来るようにするのじゃ.

走査範囲を小さくして,さらに調整する.途中から三角形ではなくなるので,階段状のエッジがs=0の位置に近づくようにqsを調整するのじゃ.　走査範囲は変数cで決まる.　c=0で,グラフのエッジの位置がs=0の位置に一致したときのps-「調整した量」が目的のqxじゃ

　異世界転生ラノベでは,ここで

「ジャジャジャーン　おめでとうございます,貴方は因数分解のスキルを得ました」

というお知らせがくる場面じゃな.

　Rが2, 3, 4, 5, 6・・・・・・・・10くらいまでは,うまくいくはずじゃ.

n桁の2つの素数p, q　があってN=p*q　q/pはほとんど整数に近い場合, pまたはqまたはp, q両方の周りのn/2桁程度ずれたpx, qxの積Nxは,グラフを描くことで素因数分解できる!　のじゃ

　ただし,任意のNが与えられたとき,これが上記の条件を満足する可能性は非常に小さいので,ほとんど役にはたたんじゃろうな. それに,与える偏差がn/2より大きくなると,特徴的なパターンが崩れて,どこにあるのかわからなくなってしまうんじゃ.　走査範囲を広げるにはcを大きくすればいい.

　Rが簡単な有理数の場合もうまく行く場合がある.

　暗号の鍵は,q/pが十分大きくなるように選ばれるはずなので,この方法で解けることは無いはずじゃ.　もし,q/pが小さい整数に近い鍵があれば,それは脆弱な鍵ということになる.

ハートをクリックで、簡単に応援の気持ちを伝えられます。（ログインが必要です）

新規登録で充実の読書を

マイページ: 読書の状況から作品を自動で分類して簡単に管理できる; 小説の未読話数がひと目でわかり前回の続きから読める; フォローしたユーザーの活動を追える
通知: 小説の更新や作者の新作の情報を受け取れる
閲覧履歴: 以前読んだ小説が一覧で見つけやすい