Модульное возведение в степень в степени двойки

Итак, я недавно поработал с функцией 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. Тем не менее, я уже дважды проверил, чтобы убедиться, что нет не-степеней двойки.

Спасибо за любую помощь, которую вы можете оказать!


c++ math exponentiation
person Mandalf The Beige    schedule 01.07.2014    source источник
comment
Вы пробовали добавить несколько std::cerr << "M " << M << ", B " << B << ... << '\n'; строк, чтобы увидеть, где что-то идет не так? Или с помощью отладчика?   -  person Tony Delroy    schedule 01.07.2014

Ответы (1)


arrow_upward
2
arrow_downward

Это правда, что если x взаимно простое с n (x и n не имеют общих делителей), то x ^ a = x ^ (phi (a)) (mod n), где phi - равенство Эйлера функция. Это потому, что тогда x принадлежит мультипликативной группе (Z / nZ), которая имеет порядок phi ( а).

Но для x, не взаимно простого с n, это уже неверно. В вашем примере у основания действительно есть общий множитель с вашим модулем, а именно 2. Так что трюк здесь не сработает. Однако, если вы хотите, вы можете написать дополнительный код для этого случая - возможно, найдите наибольшую степень двойки, на которую делится x, скажем, 2 ^ k. Затем разделите x на 2 ^ k, запустите исходный код, сдвиньте его вывод влево на k * e, где e - ваш показатель степени, и уменьшите по модулю M. Конечно, если k не равно нулю, это обычно приводит к ответу нуля.

person p_a_c    schedule 01.07.2014