Calculating the modulus of a large square

Question

I want to calculate the modulus of a square: n^2 % m, where both n and m are large numbers (but less than the maximum of a 64 bits integer). The problem arrises when n^2 gets larger than the 64 bits maximum.

Is there an algorithm available to do this calculation? I know n^2 % m = (n % m)^2 %m, but this doesn't help me when m > n.

Answer 1

Let n = k * 2³² + j where j, k < 2³². Then 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;
}