Вычислить x ^ (1 / y) mod m fast (модульный корень)

Question

Как быстро решить x ^ ( 1 / y) mod m, где x, y, m - все положительные целые числа?

Это обратный расчет для x ^ y mod m. Например

сторона A вручает стороне B заранее согласовать положительное целое число y и m

сторона A генерирует число x1 (0

партия B вычисляет x2 ^ ( 1 / y) mod m, так что она возвращается x1

Я знаю, как быстро вычислить x1 ^ y mod m, но я не знаю, как быстро вычислить x2 ^ ( 1 / y) mod m. Какие-либо предложения?

Я не знаю, как назвать этот вопрос. Если x ^ y mod m называется возведением в моду, это называется модульным корнем?

Answer 1

Я думаю, что вы задаете этот вопрос: учитывая y, m и результат x^y (mod m) найдите x (при условии 0 <= x

В общем, это не имеет решения - например, для y=2, m=4, 0^2, 1^2, 2^2, 3^2 = 0, 1, 0, 1 (мод 4), поэтому, если вам дан квадрат числа 4, вы не сможете вернуть исходное число.

Однако в некоторых случаях вы можете сделать это. Например, когда m простое, а y взаимно простое с m-1. Тогда можно найти y 'такой, что для всех 0 <= x

Обратите внимание, что (x ^ y) ^ y '= x ^ (yy'). Не обращая внимания на тривиальный случай, когда x=0, если m является простой, маленькая теорема Ферма говорит нам, что x^(m-1) = 1 (mod m). Таким образом, мы можем решить yy' = 1 (mod m-1). Это решение (которое может быть найдено с использованием расширенного евклидова алгоритма) в предположении, что y и m-1 взаимно просты.

Вот рабочий код, с примером с y=5, m=17. Он использует модульный обратный код из https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm

def egcd(a, b):
    if a == 0: return b, 0, 1
    g, x, y = egcd(b%a, a)
    return g, y - (b//a) * x, x

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise AssertionError('no inverse')
    return x % m

def encrypt(xs, y, m):
    return [pow(x, y, m) for x in xs]

def decrypt(xs, y, m):
    y2 = modinv(y, m-1)
    return encrypt(xs, y2, m)

y = 5
m = 17

e = encrypt(range(m), y, m)
print decrypt(e, y, m)

RSA основан на случае, когда m является произведением двух различных простых чисел p, q. Применяются те же идеи, что и выше, но нужно найти y 'такой, что yy' = 1 (mod lcm((p-1)(q-1))). В отличие от вышеизложенного, сделать это легко нельзя только при наличии y и m, потому что не существует известных эффективных способов нахождения p и q.