Вычислить b ^ n из a, b и a ^ n по модулю p

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 (мод p) = 1. Тогда N может быть либо 2, либо 4, поскольку 4 ² = 1 (мод 5) и 4 ⁴ = 1 (мод 5).Однако 2 ² = 4 (мод 5) и 2 ⁴ = 1 (мод 5), поэтому приведенной информации недостаточно, чтобы зафиксировать значение 2 ^N .

Если вам дается больше информации - возможно, вам говорят, что порядки a и b по модулю p равны, или порядок b делит порядок a, или a является первообразным корнем- тогда это возможно.Но я не знаю эффективного алгоритма для этого.