巨大な数の素因数分解に賞金をかけているRSA ChallengeのひとつであるRSA-576の素因数分解にドイツ連邦情報技術保安局のチームが成功した。RSA-576は576ビット長の巨大な整数(10進数で174桁)で、素因数分解の成功に1万米ドルの賞金がかけられていた。RSA Challengeはまだこの解を正解認定していないが、解答とされている素数をかけるとRSA-576が得られることを簡単に自分でも確認できる。RSA Challengeの背景と今回の素因数分解に使われた手法についてはMathworldの記事が詳しい。
RSAを筆頭に公開鍵暗号はふたつの巨大な素数をかけるのは簡単だが、その結果をまた元の素数に因数分解するのは困難、という性質に基づいている。素因数分解が可能になれば公開鍵から秘密鍵が計算できるので、今回の発表はひとつの576bit長のRSA鍵そのものの解読に相当する。