解読法と素因数分解 – まいとう情報通信研究会

効率良い解き方が見つかっていない素因数分解も、コンピュータを使えばかなりの桁まで現実的に行えます。ところが、その数を構成する二つの素数 P と Q が少し大きくなっただけで、割り出すのに必要な計算時間が莫大に増えてしまうのです。現在、素数が 50 桁づつのペア（掛けて 100 桁）程度なら、現実的にコンピュータで素因数分解できます。というのは、ＲＳＡ暗号の発明者の一人で RSA Security 社の創業メンバーでもある Rivest 博士が 1970 年に出題した 129 桁の数（２つの素数をかけ合わせた数）の素因数分解問題（ RSA-129 問題）が、1994年に多重多項式ふるい法という方法によって解かれたというニュースが流れたからです。 その２つの素数をかけ合わせた 129 桁の数とは、 114381625757888867669235779976146612010218296721

[boxmanx99]

RSA暗号 素因数分解 N≠NP問題