Самый быстрый алгоритм для вычисления (a ^ (2 ^ N))% m?
Известны алгоритмы криптографии для вычисления модульного возведения в степень (a ^ b)% c (например, двоичный метод справа налево: http://en.wikipedia.org/wiki/Modular_exponentiation).
Но существует ли алгоритм для вычисления модулярного возведения в степень вида (a ^ (2 ^ N))% m быстрее, чем с "классическими" алгоритмами?
Большое спасибо!
Примечание:
1) m может быть очень большим простым... или нет (поэтому оптимизация не зависит от m)
2) N может достигать 2 ^ 32-1 (N < 2 ^ 32)
Ответы
Ответ 1
Если m - простое, вы можете вычислить это намного быстрее.
Вы начинаете с вычисления p = 2 N% (m-1) с двоичным методом справа налево.
Затем вы используете двоичный метод справа налево для вычисления a p% m, который равен исходному выражению из-за Маленькая теорема Ферма.
Если m не является простым, но достаточно малым, чтобы его можно было учитывать, вы можете вычислить функцию Euller totient и использовать теорему Эйлера.
Если оптимизация в зависимости от m не возможна, возможно, самое лучшее, что вы можете сделать, это использовать сокращение Montgomery.
Ответ 2
Кроме того, как обобщение для Евгения отвечает: если вы знаете факторизацию m: m = p1 * p2 * ... * p{n}, вы можете использовать теорему Эйлера:
Вычислить тоталь phi(m)= (p1-1)*(p2-1)*...*(p{n}-1).
Затем вы можете вычислить p = 2^N % phi(m) и найти a^(2^N) % m = a^p % m.
Однако в этом случае не используется специальная форма 2^N.
Ответ 3
Евгений и Расмус дают отличные ответы. Чтобы добавить к этому, не забудьте использовать последовательное возведение в квадрат для полномочий. То есть, напишите экспоненту, скажем E, в базе 2:
E = b0*1 + b1*2 + ... + bk*2^k
где каждый bi является либо 0, либо 1, а bk = 1 является последним ненулевым битом. Затем вы можете поднять число, скажем N, экспоненте E на
N^E (mod m) = n0^b0 * n1^b1 * ... * nk^bk (mod m)
где
n0 = N (mod m)
n1 = n0^2 (mod m)
n2 = n1^2 (mod m)
...
nk = n(k-1)^k (mod m)
Например, для вычисления 28^27 mod 76 у вас есть N = 28, E = 27, m = 76, а вычисление
27 = 1 + 2 + 8 + 16
E = b0 + b1 + b3 + b4
и
n0 = 28 (mod 76)
n1 = 28^2 (mod 76) = 24
n2 = 24^2 (mod 76) = 44
n3 = 44^2 (mod 76) = 36
n4 = 36^3 (mod 76) = 4
и, наконец,
28^27 (mod 76) = 28 * 24 * 36 * 4 (mod 76) = 20
N^ E (mod m) = n0 * n1 * n3 * n4 (mod 76)
