说明如何使用a基计算离散对数的有效算法可以有效地计算基数为b的离散对数。

Question

我有一项练习，内容如下：

设p是奇数素数，a和b是生成元\mathbb{Z}​_p^*。假设我们有一个用基A计算离散对数的有效算法a。说明了该算法如何利用基b有效地计算离散对数。

在考虑改变基本规则时，我做了以下工作：

B(b,x):
    return A(x) / A(b)

这是正确的，演习结束了吗？我想说是的，但是和我目前正在解决的另一个练习相比，这很容易，所以我想我错过了一些东西。

Answer 1

这是正确的，演习结束了吗？

我不能说你的教授希望你在多大程度上明确，但它本质上是正确的(如果我给它打分，我会接受它作为答案)。现在，您的教授可能希望您解释(或提供一个证据)为什么这是正确的。

Answer 2

对我来说，有些事情有点不正确或缺少：

• 如果B是一种“用基本b计算离散对数”的算法，那么它不需要输入b (就像A没有输入a一样)。
• 它没有详细说明/操作的具体操作，这是非常重要的。走p=2311，a=53，b=3，x=5。A(x)\mapsto322，A(b)\mapsto989.我们怎样才能找到来自B(x)\mapsto1988的322/989呢？
• 如果A以足够的概率工作(包括，总是)，那么B是否具有足够的概率(或者如果适用的话，总是工作)，以便与所要求的证明相匹配？
• 还没有说明为什么B是有效的。