質問: 大きな数の素因数分解 本で、2^67-1 を手計算で因数分解するのに、日曜日が3年かかるという話があったのですが、 ・手計算でできるのでしょうか? ・逆に手計算で3年もかかるものでしょうか? どうやって計算したと思いますか?
回答: ある自然数を素因数分解する方法として誰もが思いつくのは その数を割り切る素数を探すということです. 2^67-1の素因数分解は 193707721×761838257287 です. 193707721(9桁)は10749692番目の素数, 761838257287(12桁)は28947792875番目の素数です. 素数の一覧表を見るのが禁止だとすると,これらが素数であることを確かめる必要があります. ちなみに,レオンハルト・オイラーが生涯に発見した最大の素数は多分 2147483647(10桁)です. 2^n-1という形をした数をメルセンヌ数といい,それが素数であるときメルセンヌ素数といいます. wikipedia「メルセンヌ数」によれば 素数pに対し2^p-1の素因数は2pを法として1と合同,8を法として1または-1と合同だそうです.67は素数なのでこれが使えます. 【メルセンヌ素数の歴史(wikipediaより抜粋)】 1772年 オイラーが8番目のメルセンヌ素数2^13-1=2147483647を発見 1876年 リュカが12番目のメルセンヌ素数2^127-1を発見 1996年 メルセンヌ素数の発見を目的としてgimpsが発足 現在までに51個のメルセンヌ素数が発見されており,そのうち順番が確定しているのは47個