素因数分解

たとえば、2^9+5^12のような数を素因数分解したいのですが、工夫したやり方？のようなものがみつかりません。
アドバイスお願いします。

No.1 ベストアンサー 回答者： naniwacchi 回答日時： 2009/10/23 00:00

2^9+5^12であれば、

a^3+b^3 = (a+b)(a^2-ab+b^2)
の因数分解が使えるのではないでしょうか？

この回答へのお礼

アドバイスありがとうございます。
しかし、うまくいきませんでした。

お礼日時：2009/10/23 00:45

No.3 回答者： warumx 回答日時： 2009/10/25 09:41

こんにちは。

例題の数は9桁ですが、一般的にはこの大きさの整数を
手計算で素因数分解するのは少し無理でしょうね。
ExceｌのVBAで組んだプログラムで計算すると簡単にできます。
2^9+5^12 = 244141137 = 128563*211*3^2
アルゴリズムはフェルマーの方法を使っています。

100桁を超えるような大きな整数の素因数分解はコンピュータを
使っても非常に難しいとされてます。
対象としている整数の大きさによると思いますが、10数桁まで
ならばフェルマーの方法で十分のようです。

No.2 回答者： Rice-Etude 回答日時： 2009/10/23 10:31

No.1の方の回答にありますように、例題の数の場合は

2^9+5^12=(2^3)^3+(5^4)^3
=A^3+B^3
（但し、A=2^3=8、B=5^4=625）
と考えて、三乗の和の因数分解に当てはめれば、まずは二つの因子に分解できます。

但し、そこから更に因数分解ができるのか、できたとしてその値をすぐに求められるか、それがすぐに分かるかは状況によるとしか言えません。例題の場合、それぞれの二つの因子を見て、あることに気がつけば、更に二つずつの因子に分解でき、計4つの因子に分解できます。そのうち、小さい方から3つまではそれが素数とすぐに判明するのですが、残り一つの大きな数が素数かどうか判明するには、コンピューターを使わないのであれば少し時間がかかると思います。

＃実際はその残りの数も素数なので、例題は4つの因子（但し、一つは重複しているので、3つの素数による分解、そのうち一つが二乗）による素因数分解になります。

素因数分解の求め方でよく知られているのが「エラストネスのふるい」というもので、これは小さい素数を使って順に割り算を行っていくものです。しかし、大きな数になると、とたんにまともに計算ができなくなります。

「エラストネスのふるい」よりも効率の良い求め方もあるにはあるのですが、それでもある特殊な場合を除いて、現在の最も性能の良いコンピューターを使って、今知られている中で最も効率の良い解き方を使っても、一般的な非常に大きな数の素因数分解は現実的に行えません。素因数分解はそれだけ解くのが難しい問題なのです。