RSA暗号が破れる素因数分解についてです。

質問

自然数 N を、√N （＝ Nの平方根）未満の自然数であって、末位の数字が１，３，７，９のもののうち、小さいもの順のものどもで以て、割ってゆき、N を素因数分解する計算の、時間計算量のオーダーは、
どれ位のものでしょうか。

回答No.1

_kappe_ · ベストアンサー

最大で(4√N)/10回割り算をすれば結果が出るので、計算量のオーダーは高々O(N^0.5)です。数学的な知見があればもっと低くなるかもしれません。

ただし、10進数表記の場合の1の位を見て判断するのは2と5の倍数による試行を除外できているだけであって、あまり効率がいいとは言えません。

Nをxという値で割り切れるかどうかを試すとします。2≦x≦√Nです。
たとえば、x≧31のときはxを30で割った余りが1,7,11,13,17,19,23,29のときだけN÷xを試すことにすれば、xが2と3と5の倍数の場合を除外できて、N÷xの回数をさらに減らせます(4/10→8/30)。30は2と3と5の最小公倍数です。
もっとも、これは計算量の係数を下げる工夫であって計算量のオーダーには影響を与えません。

お礼

早速の、懇切ご丁寧な御回答を誠に有難う御座いました。

補足

それでは、多項式時間の中でも最低の次数の一次式時間であるところの、N　よりも、更に、遥かに低い時間計算量ですね？
　つまり、RSA暗号など、組み合わせ爆発による指数関数的な時間計算量など要すること無しに、ごくごく短時間で破れますね？
　なお、Microsoft Bing AI による回答に関する、追加の質問にも御回答いただきますならば、幸甚に存じます。