(KM)离散对数
离散对数
在整数中，离散对数（英语：Discrete logarithm）是一种基于同余运算和原根的一种对数运算。而在实数中对数的定义 logb a 是指对于给定的 a 和 b，有一个数 x，使得bx = a。相同地在任何群 G中可为所有整数 k定义一个幂数为 bk，而离散对数 logb a是指使得 bk = a的整数 k。 离散对数在一些特殊情况下可以快速计算。然而，通常没有具非常效率的方法来计算它们。公钥密码学中几个重要算法的基础，是假设寻找离散对数的问题解，在仔细选择过的群中，并不存在有效率的求解算法。
未解决的计算机科学问题：是否存在离散对数问题的多项式时间经典算法？
未解决的计算机科学问题
计算复杂性理论
P = NP问题。这是七个千禧年大奖难题之一
NC (复杂度)
NP = co-NP问题
P = BPP问题
P = PSPACE问题
BQP和NP之间的关系是什么？
独特游戏猜想
指数时间假说是真的吗？
单向函数存在吗？
算法
两个n位数乘法算法速度最快的是什么？
速度最快的矩阵乘法算法是什么？
可以在多项式时间内做整数分解吗？
可以在多项式时间内计算离散对数吗？
可以在多项式时间内解决图同构问题吗？
可以在多项式时间内解决奇偶校验游戏吗？
线性规划问题是否存在强多项式时间的解法？这是Smale问题列表中的第9个问题。
快速傅里叶变换算法的复杂性上下限是什么？他们能比Θ（N log N）快吗？
可以在次二次时间内解决3SUM问题吗？
伸展树动态最优性猜想
K-服务器问题
编程语言理论
POPLmark
Barendregt–Geuvers–Klop猜想
广义星高问题
其他问题
Aanderaa–Karp–Rosenberg猜想