素因数分解問題
問題
問題：次の数字を素因数分解せよ。
数字：
2452466449002782119765176635730880184670267876783327597434144517150616008300385
8721695220839933207154910362682719167986407977672324300560059203563124656121846
5817904100131859299619933817012149335034875870551067
桁数にして210桁の整数になります。なんとか兆なんとか億という大きな数の呼び方が
ありますが、210桁までいくとそういった呼び方は与えられていません。つまり、正しく
読むことはできませんが、この整数を正しく因数分解できたら、おそらく賞金がもらえるでしょう。
素因数分解って何だっけ？
素因数分解とは、ある数が与えられたときに、その数をできるだけ小さい数の掛け算として
表すことです。例えば、12という数字を素因数分解しようとすると、2*2*3という答えになります。
12程度であれば、計算は簡単でしょう。しかし、9167という数字を素因数分解
しようと思うと、手計算では難しいでしょう。ちなみに答えは、89*103になります。このように
大きな数の素因数分解で、しかもその解も2つの比較的大きな素数であれば難しくなります。
さっきの例の9167程度であれば、コンピュータで計算すれば一瞬で求められるでしょうが、
元の問題のような210桁にもなる数の素因数分岐はそういうわけにはいきません。恐らく、
今手元にあるパソコンで計算させると、4887661558879417773188225975289750432634374270
5770856603753876036599582144017538944639170485年程度かかるという試算です。
この問題の背景や、アプローチについては続きにて
問題の背景にあるのは？
この大きな桁数の素因数分解の背景にあるのは、RSA暗号の十分なビット長を知ることです。
RSA暗号に関する記事は以前
で書いているので、そちらをご確認下さい。
この問題にどうアプローチする？
多くのリソースを活用できる立場にあるとすれば、
- スーパーコンピュータを利用
- ワークステーションを利用
- 並列計算を利用
などが考えられます。とはいえ、こういった高性能コンピュータを使ったとしても、
解けるのはおそらく100年以上かかるかと思います。また、個人レベルであれば、
- CPUではなく、GPUで演算させる
が有力かなぁと思います。とはいえ、個人レベルで挑戦するとすれば、「まずできない」ことを
第一に考えながら趣味程度で行うことを推奨します。
関連記事
関連記事
[PR]
トラックバック
http://yamablo.com/2009/06/24-153021.php/trackback
