Modulo умножения больших чисел

Question

Да, я знаю, что вопрос может показаться наивным, но я много искал в Google и на этом сайте, но не смог найти удовлетворительного ответа на него. Я просто хочу вычислить (A * B)% MOD, если a длинный длинный, а также b и MOD. Предположим, что MOD больше, чем A и B, такие, что A% MOD = A и B% MOD = B, но A * B больше, чем 64 бит. Как можно исправить значение (A * B)% MOD?

Answer 1

Основная идея заключается в том, чтобы сначала определить непереполняющую функцию addmod, которая использует отрицательные числа в своей арифметике. Затем определите timesmod с помощью битовых операций. Сложность времени равна O(N), где N - количество используемых бит (в этом случае 64).

#include <iostream> 
using namespace std; 

typedef long long BigInt; // must be signed, to detect overflow 

BigInt A = 0x7fffffffffffff01; 
BigInt B = 0x7fffffffffffff02; 
BigInt M = 0x7fffffffffffff03; 

// For simplicity it is assumed x, y, and m are all positive. 
BigInt addmod(BigInt x, BigInt y, BigInt m) 
{ 
    x %= m; 
    y %= m; 
    BigInt sum = x-m+y; // -m <= sum < m-1 
    return sum < 0 ? sum + m : sum; 
} 

BigInt timesmod(BigInt x, BigInt y, BigInt m) 
{ 
    x %= m; 
    y %= m; 
    BigInt a = x < y ? x : y; // min 
    BigInt b = x < y ? y : x; // max 
    BigInt product = 0; 
    for (; a != 0; a >>= 1, b = addmod(b,b,m)) 
    if (a&1) product = addmod(product,b,m); 
    return product; 
} 

int main() 
{ 
    cout << "A = " << A << endl; 
    cout << "B = " << B << endl; 
    cout << "M = " << M << endl; 
    cout << "A*B mod M = " << timesmod(A,B,M) << endl; 
    return 0; 
} 

Выход:

A = 9223372036854775553 
B = 9223372036854775554 
M = 9223372036854775555 
A*B mod M = 2 

Это легко подтверждается, так как A=-2 и B=-1 мод M.

Примечание: этот код не оптимизирован.

Answer 2

У меня нет времени ответить на это прямо сейчас, поэтому я дам указатель и вернусь, чтобы позже отредактировать этот ответ. Посмотрите «умножение грамотности» в своем любимом учебнике алгоритмов (или поисковой системе). Основная идея состоит в том, чтобы разделить как A, так и B на кусочки, обработать куски по отдельности, а затем объединить куски, чтобы завершить расчет.

Answer 3

Я думаю, что вы можете сформировать 128-битный продукт в две части (высокие 64 бит и низкие 64 бит) и уменьшить каждую часть по модулю p. Предполагая, что p составляет около 4^k, вы можете затем выяснить, сколько p находится в этом количестве, разделив hi64/(p>>k); это должно дать вам примерно k-1 бит правильного ответа. Вычитайте, что много p от всего, и теперь hi64 имеет около k-1 меньше бит. Сделайте это снова, но вычислите (hi64 << k-1)/(p >> k). Затем сделайте это снова, вычислив (hi64 << k+k-2)/(p >> k).

Шрифт, предложенный другим плакатом, звучит лучше, но я этого не понимаю. Надеюсь, этот плакат вернется и завершит свой ответ!