• ベストアンサー
  • 暇なときにでも

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

「暗号解読」(サイモン・シン(著)青木薫(訳) 新潮社)という本を読んで、急に素数のことに関心を持ちました。 数十桁もある数(合成数)を素因数分解するのは、えらく時間がかかることが書かれていました。 中学生が計算する素因数分解や、「エラトステネスのふるい」のほかに、手計算や計算機を使って、合成数から素数を見つける方法(素因数分解)を知りたいので、ご存知の方教えてください。 できれば、計算機科学における現在、最速の素因数分解の方法(アルゴリズム)を知りたいです。

共感・応援の気持ちを伝えよう!

  • 回答数3
  • 閲覧数614
  • ありがとう数5

質問者が選んだベストアンサー

  • ベストアンサー
  • 回答No.1
  • yosa
  • ベストアンサー率16% (28/170)

確か、いまだはっきりした公式はできていないですよね?。 素因数分解。 いまあるアルゴリズムは、結局しらみつぶしに探し出す方法 でしかないと聞いたことがあります。 ちなみに、10進数の2000桁の素数を全て見つけ出そうとした場合、 全宇宙の全ての物質を現代の最速コンピュータの生産に 当てて並列処理を行ったとしても、宇宙の滅亡までに 計算が終了しないといわれています。

共感・感謝の気持ちを伝えよう!

質問者からのお礼

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

その他の回答 (2)

  • 回答No.3

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

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

共感・感謝の気持ちを伝えよう!

質問者からのお礼

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

  • 回答No.2

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

共感・感謝の気持ちを伝えよう!

質問者からのお礼

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

関連するQ&A

  • 素因数分解について

    X=√4,840,000 を素因数分解?? で解く場合、100*2*11=2,200 となると思いますが、素数の100を1000にしては駄目ですか? そもそも、素因数分解のルールが理解出来ていません。 素因数分解の簡単なやり方を分かり易く教えて下さる方、宜しくお願いいたします。 因数分解は方程式なので、取っ付きにくいイメージがあります。

  • 素数の素因数分解

    素数(例えば17)の素因数分解について  (1)すでに素因数分解は終わっている (17の素因数分解は17)  (2)素因数分解はできない のどちらの見解が正しいですか?

  • 素因数分解について

     ものすごく大きな素数二つを掛け合わせた数を素因数分解することは難しい、というようなことを本で読みました。 これって暗号を作ることにも利用されているみたいですが、どうしてこの数を素因数分解することが難しいのでしょうか?

  • 素因数分解について

    中学三年で習う素因数分解についてです。 素因数分解をするときに、数字を最小の素数で割らなければいけない理由は何ですか? また、素因数分解を利用して最大公約数と最小公倍数を求めるための式(共通の素数をかけていくという式です)の意味が理解できません。。 何故あの式で最小公倍数と最大公約数が出るんでしょうか? テストが近いのでかなり焦っています。 どなたか詳しく説明してくださる方、回答よろしくお願いします。

  • 素因数分解について

    多分、すごく初歩的な質問だと思いますが、次のことは正しいですか? 1と素数以外の整数は、すべて素因数分解できる。 よろしくお願いします。

  • 素因数分解の問題

    久々に素因数分解の問題を解いてみようとしたところ、いきなり躓いてしまいました。 二桁の整数nに168をかけると、ある数の二乗になりました。この整数nはいくらになるかという問題です。 168を素因数分解し、n×168=n×2^3×3×7となることは分かります。 これから先、どのように組み立てて解けばよいのか分かりません。 解説では、各素数が偶数個になるように解くと書かれており、ある数の二乗になるため、 n=2×3×7×m^2となっていました。 どうしてこのような式なるのですか? A=A^p×b^q×c^rとなっている時、各指数がすべて偶数(2の倍数)なっていれば、Aは何かの二乗になることは確かめてみました。

  • 素因数分解!?

    xは自然数でx^2=736164のときxを求めよ。という問題なのですが、素因数分解してくと2、2、3、3の順で分解できるのはすぐ気づきます。しかし20449でとまってしまいます・・。なんとか143で分解できると気づいてx=858と答え出せたのですが、もっと上手い解き方ありますか?あるいは、2~3桁の素数の積を一瞬で見分ける方法はありますか?わかる方いましたらお願いします。

  • 素因数分解 解き方

    素因数分解 解き方 120=2X2X2X3X5  ←どうやってこの数が出てきたんですか? 3 =2 x3x7ってどうやったらこうなるんですか?  今、素数をマスターできましたが素因数分解はまだです。   詳しくお願いします!

  • 素因数分解

    素因数分解はわらずとも解に至ります。それをどうしたら、みなさんにお伝えできるか 数学教育協議会等にも顔を出したり、ずいぶん前から、たくさんの新しい事を創り、双子素数などは、 ペア素数の定理として、すべて一括に実証されます、素因数分解などは、桁数は関係ありません。素因数分解の世界記録、現在NTT総合研究所とドイツのボン大学とスイスのローザンヌ大学とフランス、オランダの研究機関が共同で3年もかかってしまう、わずか232桁です、これは、すべて、割るがベースにある からです。割るを、使わずとも、解に至ります。どうして、理解しようとしないのか、わかりません。 古代バビロニアの人々ですらできたのです。4000年も前です、基本は考え方です。難しく、難解な高等数学入りません。平方根を厳密解を求める、つまり、開平がちゃんと、理解でき、従来の2個ずつ、開くことを拡張して、8個、とか、16個いっぺんに開く方法もあるので、そういう工夫をすれば、よい。 あとは、大きい数値を、扱えるかどうかです。つまり素因数分解は、one-way-function出はありません。232桁も数分でしょう。

  • 素因数分解の問題

    「1から30までのすべての自然数の積をXとすると、Xの末尾には0がいくつ並ぶことになるか。なお、Xは29以下のすべての素数の積、X=2a×3b×5c×7d・・・×29で表される。」という問題があります。解説の、「10を素因数分解すると2×5であるから、末尾に並ぶ0の個数nは、Xのすべての素数の積 X=2a×3b×5c×7d・・・×29 において、aとcの内大きくない方である。」という記述が理解できません。どなたか教えてくださいませんか?