计算a * a mod n而不会溢出 [英] Calculate a*a mod n without overflow

问题描述

我需要计算a*a mod n，但是a相当大，当我平方时会导致溢出.进行((a % n)*(a % n)) % n无效，因为(n-1) ² 可能溢出.这是在C ++中，我正在使用int64_t

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

示例值:a = 821037907258和n = 800000000000，如果将其平方，则溢出.

Example value: a = 821037907258 and n = 800000000000, which overflows if you square it.

我正在使用DevCPP，并且我已经尝试过使大整数库无法正常工作.

I am using DevCPP and I've already tried getting big-integer libraries working to no avail.

不，这些数字没有规律.

No, there's no pattern to these numbers.

推荐答案

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

If you can't use a big-integer library, and you don't have a native uint128_t (or similar), you'll need to do this manually.

一种选择是将a表示为两个32位量的总和，即 a = 2 ³² b + c ，其中 b 包含32个msbs，而 c 包含32个lsbs.那么，平方是一组四个交叉乘法.保证每个结果都适合64位类型.然后，在重新组合各个术语时进行取模运算(请仔细考虑重新排列所有内容所需的移位).

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).

这篇关于计算a * a mod n而不会溢出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！