我需要计算一个* a mod n,但是a相当大,当我对它进行平方时会导致溢出.执行((a％n)*(a％n))％n不起作用,因为(n-1)2可能溢出.这是在C中,我使用的是int64_t

编辑：

示例值：a = 821037907258,n = 800000000000,如果将其平方,则会溢出.

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

编辑2：

不,这些数字没有模式.

解决方法:

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

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