すばやく素因数分解する方法は？

質問

「暗号解読」（サイモン・シン（著）青木薫（訳） 新潮社）という本を読んで、急に素数のことに関心を持ちました。

数十桁もある数（合成数）を素因数分解するのは、えらく時間がかかることが書かれていました。

中学生が計算する素因数分解や、「エラトステネスのふるい」のほかに、手計算や計算機を使って、合成数から素数を見つける方法（素因数分解）を知りたいので、ご存知の方教えてください。

できれば、計算機科学における現在、最速の素因数分解の方法（アルゴリズム）を知りたいです。

回答No.1

yosa · ベストアンサー

確か、いまだはっきりした公式はできていないですよね？。
素因数分解。
いまあるアルゴリズムは、結局しらみつぶしに探し出す方法
でしかないと聞いたことがあります。

ちなみに、10進数の2000桁の素数を全て見つけ出そうとした場合、
全宇宙の全ての物質を現代の最速コンピュータの生産に
当てて並列処理を行ったとしても、宇宙の滅亡までに
計算が終了しないといわれています。

お礼

早速のご回答ありがとうございました。そうなんですか…中学生が習う素因数分解なので、いろいろな解法があると思ったんですけど、、、難しい問題なんですね。

回答No.3

graphaffine

確かに素因数分解が難しい問題である事は確か（と言ってもいろんな問題の中では容易なほうだとは思いますが）ですが、公式はちゃんとあります。
参考サイト（この分野では結構有名）を見ると次のようなもの等があります。
* Brute force method
* ρ method（Pollard, Brent）
* ｐ－１ method
* ｐ＋１ method

参考URL：

http://www.asahi-net.or.jp/~KC2H-MSM/mathland/math12/index.htm

お礼

面白いサイトをご紹介いただき、ありがとうございました。

回答No.2

Mell-Lily

素因数分解を速やかに行う、有効な方法はありません。このことが、素因数分解を暗号に利用する理由なのです。

お礼

意外ですね。中学生で習うことなので、簡単だと思っていましたが…