用 % 处理溢出

Question

我有一个 Java 函数，如下所示：

private static long fieldPrime = 4294967291L; // 2^32-5
public final static long modMult(long a, long b) {
    long r = (a*b) % fieldPrime;        
    return r;
}

它将两个值相乘（保证在 0 和 2^32-5 之间），然后对一个大素数取模。

它适用于大多数数字，但有时 a*b 溢出，这会导致函数返回错误的值。不幸的是，Java 不支持无符号长整型（这本来可以解决问题）并且 BigInteger 太慢。我可以用其他方法解决这个问题吗？即，当我检测到溢出时，我可以以某种方式调整 r （在这种情况下 a*b < 0 总是意味着它已经溢出）。

Answer 1

这应该可行（如果 a 和 b 都在 0 和 fieldPrime-1 之间）：

  private static long fieldPrime = 4294967291L; // 2^32-5
  private static long correctionFactor = fieldPrime+25; //fieldPrime + (2^64) mod fieldPrime 

  public final static long modMult(long a, long b) {
      long r = (a*b);
      if (r>=0)
      {
        return r % fieldPrime;
      }
      else
      {
        return ((r% fieldPrime)+correctionFactor)%fieldPrime;  
      }
  }

当发生溢出时，a*b 实际上是 a * b - 2^64，因此需要添加 (2^64 mod fieldPrime)。需要再加1个fieldPrime和1个%运算，使结果在0到fieldPrime-1范围内（否则可能为负数）。

（如果 fieldPrime>2^32，则不会以这种方式工作。）

编辑
else部分也可以改成：（

    return (fieldPrime-a)*(fieldPrime-b)%fieldPrime;

不知道哪个更快。）

Answer 2

一旦您知道自己再次处于安全范围内（取模后），您可以将 a、b 和 fieldPrime 转换为双精度并将结果转换回 long。然而，在某些情况下，双精度数可能会导致舍入错误。

除此之外，我想说 BigInteger 是你最好的选择，如果它太慢，也许你可以制作一些可以使用字节数组而不是长整型的东西，但我怀疑这会快得多。