以模p中的a,b和a ^ n计算b ^ n

Question

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

一个简单的方法是获得N的离散对数,但是有更有效的方法吗？或者问题相当于离散对数？

Answer 1

一般来说没有办法.这是因为你的条件不足以确定b ^N(mod p)的值.

例如,设a = 4,b = 2,p = 5,并且^N(mod p)= 1.那么N可以是2或4,因为4 ² = 1(mod 5)和4 ⁴ = 1( mod 5).但是,2 ² = 4(mod 5)和2 ⁴ = 1(mod 5),因此给出的信息不足以固定2 ^N的值.

如果给你更多的信息 - 也许你被告知a和b模p的顺序是相等的,或者b的顺序除以a的顺序,或者a是原始根 - 那么它是可能的.但我不知道这样做的有效算法.