読み方 ： そいんすうぶんかいもんだい
素因数分解問題【prime factorization problem】
概要
素因数分解とは、任意の自然数を素数の掛け算の形で表す操作を指す。例えば、「15」という数は「3×5」という素数の組み合わせに分解できる。どのような正の整数も、素因数の並び方を除けば分解の結果は一通りに定まる。
対象となる数が小さいうちは、2や3、5といった小さい素数で順に割っていく「試し割り法」で答えを求められる。フェルマー法や二次ふるい法、数体ふるい法などのアルゴリズムも知られているが、入力する数が大きくなるほど計算量は急速に増加する。
特に、数百桁に及ぶ巨大な素数同士を掛け合わせて得られた合成数を扱う場合、現代のスーパーコンピュータを用いても、元の素数を現実的な時間内に割り出すことは極めて困難とされる。掛け算そのものは一瞬で完了する一方、その逆算に当たる素因数分解には膨大な時間を要するという非対称性があり、暗号技術で秘密の情報を割り出しにくくするために応用されている。
この計算の難しさを用いるのがRSA暗号である。二つの大きな素数の積から公開鍵を導出し、片方の素数から秘密鍵を得る。公開鍵で暗号化されたデータは、正当な利用者が持つ秘密鍵のみで復号できる。公開鍵から秘密鍵を割り出すには合成数を2つの素数の積に分解しなければならず、今のところ多項式時間で素因数分解を実行できる古典的なアルゴリズムは見つかっていない。
一方、量子コンピュータ上の計算手順である「ショアのアルゴリズム」は、理論上この素因数分解問題を従来のコンピュータより飛躍的に短い時間で解くことができる。大規模で誤り耐性を備えた量子コンピュータが実現すれば、RSA暗号を含む既存の暗号方式の安全性に影響を及ぼす可能性があるとされており、素因数分解問題の困難性に依存しない「耐量子暗号」（PQC）への移行が進められている。
(2026.7.3更新)
共有ボタンをタップ