素因数分解 - trinoの走り書き

素因数分解は原則的にゴリ押ししかないということで桁が増えてくると事実上不可能になってくる。それを利用した暗号技術がRSAだ。詳しくは割愛するがもし暗号解読しようと思ったら512bitの数値を素因数分解することになる。
しかし512bit数値を素因数分解するのがそんなに大変なことなのか？とちょいと疑問に思って簡単なプログラムを書いてみました。

unsigned int n;
cin >> n;

unsigned int nLimite = static_cast< unsigned int >( sqrt( static_cast< double >( n ) ) ) + 1;

vector< unsigned int > aFactor;
for( unsigned int i = 2; i <= nLimite; i++ ){
	while( n % i == 0 ){
		aFactor.push_back( i );
		n /= i;
		nLimite = static_cast< unsigned int >( sqrt( static_cast< double >( n ) ) ) + 1;
	}
}
if( n != 1 ){
	aFactor.push_back( n );
}

最終的にaFactorの中に素因数が全て格納されます。
intが32bitなので最大32bitの数値を素因数分解できます。いまどきのコンピュータなら多分一瞬で出来るでしょう。ついでに、intを__int64にして64bitも試してみました。これも殆どの場合が一瞬で終了しましたが時間のかかる奴だと1分程要しました。
原則的にゴリ押ししかできないので、元の数値が一桁上げれば時間も一桁上がる。64bitで1分としたら512bitなら桁は512-64=448、なので２^448倍かかることになる。はい。宇宙の年齢が微々たる時間に感じるくらいすごいことになってますね。
ちなみに、RSAの開発元で、素因数分解に賞金がかかっているということでちょっくら挑戦できたらいいかなぁ〜等となめきった考えでページにいってみました。
http://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html
はい。なんだか気の遠くなるような数値ですね。いろいろ数学の知識がないととてもじゃないけど全くの不可能と言っていいでしょうね。しかしまあ、全く希望がないわけではない。まず、数値自体が2つの素数であるということで、その素数は両方とも大きいはずである。のでそっちから先に当たってみる。あとはモンテカルロ的にそのあたりを攻めまくれば運がよければ宝くじよりは確率は高いかもしれない。

ついでに私も問題を作ってみました。賞金は出せませんが(ていうか出せるほどの難易度はない)出来た人には昼飯ぐらいは奢ってあげます。
1234567901234567900987654320987654321
数学センスのある人ならすぐ解けるかも。