algorithm - 从 a、b 和 a^n 以模 p 计算 b^n

Question

是否有任何算法可以计算 (b^N mod p), 给定 a, b, p(这是一个素数)和 (a^N mod p) 但N 未知？

一个简单的方法是离散对数得到 N，但有没有更有效的方法？或者问题等价于离散对数？

Answer 1

总的来说是没有办法的。这是因为你的条件不足以固定b^N (mod p)的值。

例如，设 a = 4、b = 2、p = 5 和 a^N (mod p) = 1。那么 N 可以是 2 或 4，因为 4 ² = 1(模 5)和 4⁴ = 1(模 5)。但是，2² = 4 (mod 5) 和 2⁴ = 1 (mod 5)，所以给出的信息不足以确定 2 ^的值N.

如果给你更多的信息——也许你被告知a和b的阶数模p相等，或者b的阶数除以a的阶数，或者a是原根——那么有可能.但我不知道执行此操作的有效算法。