溢出:a*a mod n

Question

我需要计算a*amod n但是a相当大,当我对它进行平方时会导致溢出.这样做((a % n)*(a % n)) % n行不通,因为(N-1)²可以溢出.这是用C++编写的,我使用的是int 64.

编辑:示例值= 821037907258和n = 800000000000,如果您将其平方,则会溢出.

我正在使用DevCPP,我已经尝试过让大整数库工作无效.

编辑2:不,这些数字没有模式.

Answer 1

如果您不能使用大整数库,并且您没有本机uint128_t(或类似),则需要手动执行此操作.

一种选择是表示a两个32位量的总和,即a = 2 ³² b + c,其中b包含32个msbs,c包含32个lbs.然后,平方是一组四次交叉乘法; 每个结果都保证适合64位类型.然后在重新组合各个术语时进行模运算(仔细考虑重新调整所有内容所需的转换).

Answer 2

您可以自己实现乘法，每次运行添加n，并立即对结果进行修改。