I need to calculate a*a mod n but a is fairly large, resulting in overflow when I square it. Doing ((a % n)*(a % n)) % n doesn't work because (n-1)² can overflow. This is in C++ and I'm using int64_t

Edit:

示例值：a = 821037907258，n = 800000000000，如果对其进行平方，则会溢出。

我正在使用 DevCPP，并且我已经尝试过让大整数库工作但无济于事。

Edit 2:

不，这些数字没有规律可循。

如果您不能使用大整数库，并且您没有本机uint128_t（或类似），您需要手动执行此操作。

One option is to express a as the sum of two 32-bit quantities, i.e. a = 2³²b + c, where b contains the 32 msbs, and c contains the 32 lsbs. Squaring is then a set of four cross-multiplications; each result is guaranteed to fit into a 64-bit type. You then do the modulo operation as you recombine the individual terms (carefully taking into account the shifts needed to realign everything).