離散対数
離散対数の計算は難しい問題(効率良いアルゴリズムが知られていない)だが、 逆の過程である離散的な冪乗は容易(→冪乗#効率的な演算法)である。 この非対称な関係は整数の因数分解と乗算との関係に似ている。 これらの非対称性は暗号システムの構築に利用される。
離散対数による暗号システムでは普通は群 G {\displaystyle G} として巡回群 Z p × {\displaystyle \mathbb {Z} _{p}^{\times }} を採る。
最近の暗号システムでは有限体上の楕円曲線の周回部分群における離散対数を利用する。
2012年6月18日、富士通、情報通信研究機構(NICT)、九州大学は278桁(923ビット)の離散対数を用いた「ペアリング暗号」を解読したと発表した。これはIntel Xeonプロセッサー252コアを148日稼働した結果である。スーパーコンピュータ「京」で換算すると13.6分に相当し、十分解読可能といえる(3357ビットならば将来にわたり十分安全といえるとしている。)。