Модульное возведение в степень над степенью 2
Так что я недавно поработал с функцией modpow. Одной из форм, которые мне были нужны, была Модульная Экспонентация, когда Модуль — Степень 2. Итак, я получил код и начал работать. Отлично, без проблем. Затем я прочитал, что один прием, который вы можете сделать, чтобы получить его быстрее, вместо того, чтобы использовать регулярную экспоненту, принимает его модуль над коэффициентом модуля.
Теперь, когда модуль является степенью двойки, ответом является просто степень на 2 меньше, чем текущая. Ну, это достаточно просто. Так что я закодировал это, и это сработало ….. иногда.
По некоторым причинам есть некоторые значения, которые не работают, и я просто не могу понять, что это такое.
uint32 modpow2x(uint32 B, uint32 X, uint32 M)
{
uint32 D;
M--;
B &= M;
X &= (M >> 1);
D = 1;
if ((X & 1) == 1)
{
D = B;
}
while ((X >>= 1) != 0)
{
B = (B * B) & M;
if ((X & 1) == 1)
{
D = (D * B) & M;
}
}
return D;
}
И это один набор чисел, для которого он не работает.
Base = 593803430
Exponent = 3448538912
Modulus = 8
И нет, в этой функции нет проверки, чтобы определить, является ли модуль модулем степени 2. Причина в том, что это внутренняя функция, и я уже знаю, что ей будут переданы только полномочия 2. Тем не менее, я уже дважды проверил, чтобы убедиться, что никакие не-степени 2 получают.
Спасибо за любую помощь, которую вы, ребята, можете оказать!
Решение
Это правда, что если х относительно простое к n (x и n не имеют общих факторов), то x ^ a = x ^ (phi (a)) (mod n), где phi — функция Эйлера. Это потому, что тогда х принадлежит мультипликативная группа (Z / nZ), который имеет порядок фи (а).
Но для x, не являющегося относительно простым для n, это больше не верно. В вашем примере база имеет общий фактор с вашим модулем, а именно 2. Таким образом, хитрость здесь не сработает. Однако, если вы хотите, вы можете написать дополнительный код для решения этого случая — возможно, найти наибольшую степень 2, на которую делится x, скажем, 2 ^ k. Затем разделите x на 2 ^ k, запустите исходный код, сдвиньте его вывод влево на k * e, где e — ваш показатель степени, и уменьшите по модулю M. Конечно, если k не равно нулю, это обычно приводит к ответу нуля.
Другие решения