Самый быстрый алгоритм для вычисления (a ^ (2 ^ N))% m? - PullRequest
Новая
       21

Самый быстрый алгоритм для вычисления (a ^ (2 ^ N))% m?

12 голосов
/ 22 марта 2012

Существуют хорошо известные алгоритмы криптографии для вычисления модульного возведения в степень (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) </p>

Ответы [ 3 ]

18 голосов
/ 22 марта 2012

Если m простое число, вы можете вычислить это намного быстрее.

Вы начинаете с вычисления p = 2 N % (m-1) двоичным методом справа налево.

Затем вы используете двоичный метод справа налево для вычисления p % m, что равно исходному выражению из-за маленькой теоремы Ферма .

Если m не простое, но достаточно маленькое, чтобы его можно было учесть, вы можете вычислить общую функцию Эйлера и использовать Теорема Эйлера .

Если оптимизация в зависимости от m невозможна, возможно, лучшее, что вы можете сделать, это использовать Сокращение Монтгомери .

3 голосов
/ 22 марта 2012

Также в качестве обобщения ответа Евгения: если вы знаете факторизацию 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, однако.

0 голосов
/ 22 марта 2012

Евгений и Расмус дают отличные ответы. Чтобы добавить к этому, не забудьте использовать последовательный квадрат для сил. То есть, напишите показатель степени, скажем 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)
...