公開鍵暗号の安全性（素因数分解）
意味・解説
巨大な数を素因数分解することの数学的な困難さを安全性の根拠とした公開鍵暗号（RSA等）の仕組み。
2つの巨大な素数 $p$ と $q$ を掛け合わせて $N$ を作るのは簡単だが、逆に $N$ から $p$ と $q$ を求めるには天文学的な計算量が必要になる。この性質（一方向性関数）を利用して秘密鍵を守る。
くわしく
「デジタルの不可逆な南京錠」の仕組みです。
1.仕組み：
100桁以上の素数同士を掛け算するのはコンピュータなら一瞬です。しかし、その結果（200桁以上の数）を元の素数に分解するには、スーパーコンピュータを何年も動かす必要があります。
2.鍵長の影響：
コンピュータの性能が上がると解読リスクが高まるため、現在は2,048ビット以上の長い鍵（$N$）を使うことが推奨されています。ポイントは、皆さんがネットショッピングでクレジットカード番号を入力する際、その裏側でこの「計算の壁」が情報の流出を防いでいるからです。
例文
SSL/TLS通信において、素因数分解の困難性を利用したRSA暗号を用いることで、通信経路の安全性を確保している。
同義語: 計算量的安全性
分類: 暗号理論