Математика: Теория чисел.

Быстрое возведение в степень по модулю.

Этот алгоритм вычисляет a ^d( mod m ) за O( logm ) арифметических операций. При этом, конечно, предполагается, что натуральные числа a и d не превосходят по величине m.

1. Представим d в двоичной системе счисления d = d₀2^r + ... + d_r-12 + d_r, где d_i, цифры в двоичном представлении, равны 0 или 1, d₀=1.

2. Положим a₀ =a и затем для i=1, ... ,r вычислим
a_i = a_i-1² * a^di (mod m).

3. a_r есть искомый вычет a^d ( mod m ).

Вверх по странице, к оглавлению и навигации.