Нахождение модуля с очень большим возведением в степень и делителем в C

Question

Мне нужна функция в C, которая вычисляет a^n mod q, где делитель q определяется как очень большой (15 383 399 235 709 406 497), а показатель степени n может также быть таким же большим.

Основываясь на свойстве умножения по модулю, что (a * b) mod n = ((a mod n) * (b mod n)) mod n, моя попытка выглядит следующим образом:

#include <stdio.h>

unsigned long long int modExp(unsigned long long int base, unsigned long long int expo, unsigned long long int mod)
{
    unsigned long long int out = 1;
    unsigned long long int cnt;
    for (cnt=expo; cnt>0; cnt--)
    {
        out = (out * base) % mod;
    }
    return out;
}

int main()
{
    printf("%llu", modExp(3, (189 + 50 * 223), 15383399235709406497));
    return 0;
}

Как видно из основной функции, описанной выше, я проверил свою функцию modExp с показателем базы 3, показателем степени (189+ 50 * 223) и делитель 15383399235709406497. Он выдал вывод 3915400295876975163 с некоторыми предупреждениями о том, что

In function ‘findxA’:
findxA.c:17:32: warning: integer constant is so large that it is unsigned [enabled by default]
     unsigned long long int h = 12036625823877237123;
                                ^
findxA.c:17:5: warning: this decimal constant is unsigned only in ISO C90 [enabled by default]
     unsigned long long int h = 12036625823877237123;
     ^
findxA.c:18:32: warning: integer constant is so large that it is unsigned [enabled by default]
     unsigned long long int q = 15383399235709406497;
                                ^
findxA.c:18:5: warning: this decimal constant is unsigned only in ISO C90 [enabled by default]
     unsigned long long int q = 15383399235709406497;
     ^
findxA.c: In function ‘main’:
findxA.c:34:48: warning: integer constant is so large that it is unsigned [enabled by default]
     printf("%llu", modExp(3, (189 + 50 * 223), 15383399235709406497));
                                                ^
findxA.c:34:5: warning: this decimal constant is unsigned only in ISO C90 [enabled by default]
     printf("%llu", modExp(3, (189 + 50 * 223), 15383399235709406497));
     ^

Чтобы проверить этот ответ, я сравнил результат (заданный функцией C) с выводом, заданнымоценивая выражение 3^(189 + 50 * 223) `mod` 15383399235709406497, написанное на Haskell.Это выражение Хаскелла вычисляется с другим десятичным числом, 12349118475990906085.Я думаю, что это моя функция C, которая неправильна, так как я считаю, что Haskell лучше справляется с обработкой таких больших десятичных знаков.

Как я могу улучшить свою функцию C, modExp?

Редактировать : я попробовал вариант в качестве первого ответа на этот вопрос. Однако, поскольку я пытаюсь иметь дело с десятичной дробью без знака long long int, я переключил все типы ввода и возврата изint без знака long long int.Это привело к ошибке сегментации.

Edit2 : Я неправильно использовал описанную выше функцию.Это не дает ошибки сегментации;но он по-прежнему не выводит правильное десятичное число.

Answer 1

Чтобы уменьшить вероятность переполнения, вы можете положиться на (x*y)%z == ((x%z) * (y%z)) % z.

Например (не проверено):

unsigned long long int modExp(unsigned long long int base, unsigned long long int expo, unsigned long long int mod)
{
    unsigned long long int baseMod = base%mod;
    unsigned long long int out = 1;
    unsigned long long int cnt;
    for (cnt=expo; cnt>0; cnt--)
    {
        out = ( (out%mod) * baseMod) % mod;
    }
    return out;
}

Также обратите внимание, что возведение в степень может быть выполнено более эффективно, как "произведение квадратов ».Например, x ** 5 == 1*(x**4) * 0*(x**2) * 1*(x**1) потому что 5 == 1*4 + 0*2 + 1*1 (или 5 == 101b).

Например (не проверено):

unsigned long long int modExp(unsigned long long int base, unsigned long long int expo, unsigned long long int mod)
{
    unsigned long long int out = 1;
    unsigned long long int temp = base%mod;

    while(exp0 > 0) {
        if( (exp0 & 1) != 0) {
            out = (out * temp) % mod;
        }
        temp = (temp*temp) % mod;
        exp0 >>= 1;
    }
    return out;
}

Для больших показателей это должно иметь огромное значение в производительности (например, если показатель равен 123456, то цикл будет иметь 17 итераций вместо 123456 итераций.)

Также;если это для какой-то криптографии (не маловероятно);тогда вам следует четко заявить об этом, потому что вы, вероятно, захотите «постоянного времени» (чтобы уменьшить вероятность синхронизации побочных каналов - например, вывести информацию об экспоненте из того, сколько времени modExp() требуется для выполнения).

В заключение;даже с изменениями числа до 15 383 399 235 709 406 497, вероятно, слишком велики для unsigned long long (вам необходимо обеспечить mod * mod <= ULLONG_MAX);это означает, что вам, вероятно, понадобится использовать / реализовать операции с большими целыми числами (например, может быть typedef struct { uint32_t digit[4]; } MY_NUMBER_TYPE вещь для обработки 128-битных целых чисел с функциями умножения и по модулю).

Answer 2

Это никогда не сработает!

Этот результат умножения здесь один

out = (out * base) % mod;

требует потенциально больше, чем 64-битный тип данных.И если происходит целочисленное переполнение (т. Е. Самые значимые биты обрезаются), операция мода оказывается неправильной!

Используйте более крупные типы данных или используйте другой подход: -)

Если вам нравится, между прочим, используйте этот тестовый код, чтобы увидеть, что на самом деле ДВАЖДЫ происходит целочисленное переполнение с вашими входными данными:

#include <stdio.h>

unsigned long long int modExp(unsigned long long int base, unsigned long long int expo, unsigned long long int mod)
{
    unsigned long long int out = 1;
    while(expo>0)
    {
        if(expo % 2 == 1)
            out = (out * base) % mod;
        expo = expo >> 1;
        if (base * base < base) printf("WARNING! INTEGER OVERFLOW!!!!\n");
        base = (base * base) % mod;
    }
    return out;
}

int main()
{
    printf("%llu", modExp(3, (189 + 50 * 223), 15383399235709406497));
    return 0;
}