Переполнение: a * a mod n

Question

Мне нужно рассчитать a*a mod n, но a довольно большой, что приводит к переполнению, когда я его квадрат. Выполнение ((a%n)*(a%n))%n не работает, потому что (n-1) может переполнение. Это в C++, и я использую int 64.

Редактировать: example a value = 821037907258 и n = 800000000000, который переполняется, если вы его квадрат.

Я использую DevCPP, и я уже пробовал получать библиотеки с большими целыми числами, безрезультатно.

Редактировать 2: Нет, у этих цифр нет рисунка.

Answer 1

Вы можете реализовать умножение самостоятельно, добавив n каждый запуск и изменение результата сразу.

Answer 2

Если вы не можете использовать библиотеку большого целого, и у вас нет родной uint128_t (или аналогичного), вам нужно будет сделать это вручную.

Одним из вариантов является, чтобы выразить a как сумму двух 32-битовых величин, т.е. с = 2 б + гр, где б содержит 32 старших бит, и гр содержит 32 фунта. Квадрагирование - это набор из четырех кросс-умножений; каждый результат гарантированно вписывается в 64-битный тип. Затем вы выполняете операцию modulo, когда вы рекомбинируете отдельные термины (тщательно принимая во внимание сдвиги, необходимые для перестройки всего).

Answer 3

Я действительно считаю, что ((a% n) * (a% n))% n должно работать для целых положительных чисел. Почему вы думаете, что это не работает? У вас есть встречный пример? Если n может быть отрицательным, то оператор% не определен.

Answer 4

Я знаю, что вам больше не нужно это, и есть альтернативное решение, но я хочу добавить альтернативный метод его реализации. Он предоставляет два разных метода: double and add algorithm и способ обработки mod(a + b, n) с обнаружением переполнения.

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

Следующий код, вероятно, медленнее, чем принятое решение (даже при его оптимизации), но если скорость не является критичной, вы можете предпочесть ее для ясности.

unsigned addmod(unsigned x, unsigned y, unsigned n) 
{ 
    // Precondition: x<n, y<n 
    // If it will overflow, use alternative calculation 
    if (x + y <= x) x = x - (n - y); 
    else x = (x + y) % n; 
    return x; 
} 

unsigned sqrmod(unsigned a, unsigned n) 
{ 
    unsigned b; 
    unsigned sum = 0; 

    // Make sure original number is less than n 
    a = a % n; 

    // Use double and add algorithm to calculate a*a mod n 
    for (b = a; b != 0; b >>= 1) { 
     if (b & 1) { 
      sum = addmod(sum, a, n); 
     } 
     a = addmod(a, a, n); 
    } 
    return sum; 
} 

Answer 5

Вот двойной и добавьте реализация умножения a * b % m, без перелива, независимо от размера а, б и т.

(Обратите внимание, что res -= m и temp_b -= m линии полагаются на 64-разрядное беззнаковое целочисленное переполнение, чтобы дать ожидаемых результатов. Это должно быть хорошо, так как целое число без знака переполнения корректно определена в C и C++. По этой причине это important to use unsigned integer types .)

uint64_t mulmod(uint64_t a, uint64_t b, uint64_t m) { 
    uint64_t res = 0; 
    uint64_t temp_b; 

    /* Only needed if b may be >= m */ 
    if (b >= m) { 
     if (m > UINT64_MAX/2u) 
      b -= m; 
     else 
      b %= m; 
    } 

    while (a != 0) { 
     if (a & 1) { 
      /* Add b to res, modulo m, without overflow */ 
      if (b >= m - res) /* Equiv to if (res + b >= m), without overflow */ 
       res -= m; 
      res += b; 
     } 
     a >>= 1; 

     /* Double b, modulo m */ 
     temp_b = b; 
     if (b >= m - b)  /* Equiv to if (2 * b >= m), without overflow */ 
      temp_b -= m; 
     b += temp_b; 
    } 
    return res; 
} 

Это my modification из another answer to another similar question.