ApowBmodC

ApowBmodC - это алгоритм, позволяющий с помощью поразрядного обхода найти a ^ b % c не вычисляя a ^ b.

Дано 3 числа, a, b, и c. Необходимо вычислить pow(a, b) % c, не вычисляя pow(a, b). (a и b могут быть очень большими, то есть возведение a в степень b привело бы к переполнению.)

Решение

Псевдокод

d = 1;
t = a;
x1 = b;

// классический цикл для итерации по всем двоичным разрядам, начиная с последнего
while (x1 > 0) {
	if (x1 % 2 == 1) {
		d = (d * t) % c;
	}
	t = (t * t) % c;
	x1 /= 2;
}

// d - результат

Си

long int aPowbModC(long int a, long int b, long int x) {
	
	long int t = a;
	long int x1 = b;
	long int d = 1;
	
	if (x1 > 0) {
		for (;;) {
          
			if (x1 % 2 == 1) {
				d = (d * t) % x;
			}
          
			x1 /= 2;
			if (x1 <= 0) break;
			t = (t * t) % x;
		}
	}
    
	return d;
}

Пример

Вычислить: pow(175, 235) % 257

235 = 11101011

# d t
0 d = 1 t = 175
1 d = (1 * 175) % 257 = 175 t = pow(175, 2) % 257 = 42
2 d = (175 * 42) % 257 = 154 t = pow(42, 2) % 257 = 222
3 Без изменений, так как x1 чётный. t = pow(222, 2) % 257 = 197
4 d = (154 * 197) % 257 = 12 t = pow(197, 2) % 257 = 2
5 Без изменений, так как x1 чётный. t = pow(2, 2) % 257 = 4
6 d = (12 * 4) % 257 = 48 t = pow(4, 2) % 257 = 16
7 d = (48 * 16) % 257 = 254 t = pow(16, 2) % 257 = 256
8 d = (254 * 256) % 253 = 3 Вычислять нет смысла, ответ уже получен.

Результат: 3

Заметка: Если b равен c, результат будет a % b


Copyright © 2019 Александр Майоров. Все права защищены.