離散対数
さらに、3 ≡ 1 (mod 17) を満たす最小の正整数 m は 16 である(すなわち、16 は (Z/17Z) における 3 の位数である)から、方程式の解はこの形のものに限られる。以上のことから、この方程式の解は k ≡ 4 (mod 16) で表せる。
もう少し一般に、n を整数として既約剰余類群 G = (Z/nZ) が巡回群であると仮定する(そのような n は 2, 4 および素数冪 q と 2 q の形に書けるものに限られる)と、群 G の位数は φ(n) だから位数 φ(n) となる元(n を法とする原始根 (primitive root of modulo n) と呼ばれる)b が存在して、G の各元 a に対して b ≡ a となるような k は φ(n) を法として一意に定まる(このときの離散対数はしばしば指数 (index) と呼ばれる)。先の例では φ(17) = 16 で b = 3 が (Z/17Z) を生成する位数 16 の元であり、a = 13 に対して k mod 16 が一意に定まっていることが確認できる。
↑ Shor, Peter (1997). “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”. SIAM Journal on Computing 26 (5): 1484–1509. arXiv:quant-ph/9508027. doi:10.1137/s0097539795293172. MR1471990.
↑ 「次世代暗号の解読で世界記録を達成」 情報通信研究機構・プレスリリース 2012年6月18日