溢出：a * a mod n [英] Overflow: a*a mod n

问题描述

我需要计算 a * a mod n ，但 a 是相当大，导致溢出时，我平方。由于（n-1） ² 可能溢出，因此执行（（a％n）*（a％n））％n 这是在C + +和我使用int 64的。

编辑：示例a值= 821037907258和n = 800000000000，

我使用的是DevCPP，我已经尝试让大整型库无效。

编辑2：无，这些数字没有模式。

解决方案

如果你不能使用大整数库，有一个原生 uint128_t （或类似的），您需要手动进行。

表示 a 作为两个32位量的总和，即 a = 2 ³² b + c ，其中 b 包含32个msbs， c 然后，平方是一组四个交叉乘法;每个结果保证适合64位类型。然后，在重新组合各个术语时（请仔细考虑重新对齐所有内容所需的位移），执行模运算。

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 int 64's.

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

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

edit 2: No, there's no pattern to these numbers.

解决方案

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.

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屋！