计算大正方形的模数

Question

我想计算一个正方形的模数：n^2 % m，其中 n 和 m 都是大数（但小于 64 位整数的最大值）。当 n^2 大于 64 位最大值时，就会出现问题。

是否有可用的算法来进行此计算？我知道 n^2 % m = (n % m)^2 %m，但是当 m > n.

时这对我没有帮助

Answer 1

令 n = k * 2³² + j 其中 j, k < 2³²。那么n^2%m=(2⁶⁴k²+2*k*j*2³² + j²) % m

#include <iostream>

int main()
{
    uint64_t n = 17179874627;
    uint64_t m = 27778894627;

    uint64_t k = n >> 32;
    uint64_t j = n & 4294967295;

    uint64_t a = (k * k) % m;   // k^2
    a = (65536 * a) % m;        // 2^16 * k^2
    a = (65536 * a) % m;        // 2^32 * k^2
    a = (65536 * a) % m;        // 2^48 * k^2
    a = (65536 * a) % m;        // 2^64 * k^2

    uint64_t b = (j * 65536) % m;
    b = (b * 65536) % m;        // j * 2^32
    b = (b * k) % m;            // k * j * 2^32
    b = (2 * b) % m;            // 2 * k * j * 2^32

    uint64_t c = (j * j) % m;   // j^ 2

    std::cout << "Result " << (a + b + c) % m;
}

Answer 2

根据 invisal 的回答，我将其扩展为 Delphi 情况代码 (n1 * n2) % m:

k1 := n1 shr 30;
j1 := n1 and 1073741823; // = 2^30 - 1
k2 := n2 shr 30;
j2 := n2 and 1073741823;

a1 := (k1 * k2) mod m;
for i := 1 to 4 do
  a1 := (32768 * a1) mod m;

a2 := (k1 * j2) mod m;
for i := 1 to 2 do
  a2 := (32768 * a2) mod m;

a3 := (k2 * j1) mod m;
for i := 1 to 2 do
  a3 := (32768 * a3) mod m;

a4 := (j1 * j2) mod m;

Result := (a1 + a2 + a3 + a4) mod m;

注意 Delphi 没有无符号 64 位整数，所以我使用 2^30 而不是 2^32。

计算大正方形的模数

Calculating the modulus of a large square

algorithm

math

modulus