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

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

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

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

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

No.1 ベストアンサー 回答者： yosa 回答日時： 2003/09/24 21:07

確か、いまだはっきりした公式はできていないですよね？。

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

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

この回答へのお礼

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

お礼日時：2003/09/24 21:21

No.3 回答者： graphaffine 回答日時： 2003/09/25 01:09

確かに素因数分解が難しい問題である事は確か（と言ってもいろんな問題の中では容易なほうだとは思いますが）ですが、公式はちゃんとあります。

参考サイト（この分野では結構有名）を見ると次のようなもの等があります。
* Brute force method
* ρ method（Pollard, Brent）
* ｐ－１ method
* ｐ＋１ method

参考URL：http://www.asahi-net.or.jp/~KC2H-MSM/mathland/ma …

この回答へのお礼

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

お礼日時：2003/11/04 08:12

No.2 回答者： Mell-Lily 回答日時： 2003/09/24 23:53

素因数分解を速やかに行う、有効な方法はありません。

このことが、素因数分解を暗号に利用する理由なのです。

この回答へのお礼

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

お礼日時：2003/11/04 08:31