Có cách nào để làm (A * B) mod M mà không tràn cho unsigned dài A và B?

Question

Tôi không muốn cơn ác mộng về cài đặt GMP trên Windows.

Tôi có hai số A và B, unsigned long long s, theo thứ tự độ lớn 10^10 hoặc nhiều nhất, nhưng ngay cả khi thực hiện ((A%M)*(B%M))%M, tôi bị tràn số nguyên.

Có chức năng homebrew để tính số (A*B)%M cho số lớn hơn không?

Answer 1

Nếu mô đun M đủ nhỏ hơn ULLONG_MAX (trường hợp này nằm trong vùng 10^10), bạn có thể thực hiện theo ba bước bằng cách tách một trong các yếu tố thành hai phần. Tôi giả định rằng A < M và B < M và M < 2^42.

// split A into to parts 
unsigned long long a1 = (A >> 21), a2 = A & ((1ull << 21) - 1); 
unsigned long long temp = (a1 * B) % M; // doesn't overflow under the assumptions 
temp = (temp << 21) % M;     // this neither 
temp += (a2*B) % M;      // nor this 
return temp % M; 

Đối với giá trị lớn hơn, bạn có thể chia nhỏ các yếu tố trong ba phần, nhưng nếu các module trở nên thực sự gần gũi với ULLONG_MAX nó trở nên xấu xí.