大数的模重置

Question

大数的模重置

3

对于一个玩具程序，我需要一种有效的计算方法。

(2**64 * x) % m

其中，x 和 m 是 Java 的 long 类型，** 表示指数运算。可以计算为：

 BigInteger.valueOf(x).shiftLeft(64).mod(BigInteger.valueOf(m)).longValue()

或者通过反复将 x 向左移动并减少，但这两种方法都非常缓慢。这不是过早的优化。

澄清：

‣ 使用 BigInteger 的任何算法可能比上述表达式更慢。

‣ 可以假设 m 太大而无法使用 int。

 long n = (1L<<32) % m; 
 return ((n*n) % m) * (x % m)) % m

"would do." 可以翻译为“会做。”

句子的完整翻译为：“缓慢的转移和减少算法有点像会做。”

// assuming x >= 0
long shift32Left(long x, long m) {
    long result = x % m;
    for (int i=0; i<64; ++i) {
        x <<= 1;
        // here, `x<0` handles overflow
        if (x<0 || x>=m) {
            x -= m;
        }
    }
}

- maaartinus

你的意思是：(2^64 * x) % m？ - hqt

m和/或x有任何限制/信息吗？ - Sirko

1

@hqt 是的，假设你不是指 xor。我指的是 $x^{64}$，但是在 SO 上 tex 符号无法使用。 - maaartinus

@Sirko 不，除了它们很大之外。适合“int”的情况很容易处理并单独处理。 - maaartinus

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- hqt · Accepted Answer

通用形式：

(a1 * a2 * a3 ... * an) % m = [(a1 % m) * (a2 % m) * ... * (a3 % m) ] % m

应用上述公式，我们有：

(2^64 * x) % m = (((2^64) % m) * (x % m)) % m

对于第一部分：2^64 mod m。我可以给出更一般的情况：2^t mod m。下面是伪代码。它将在N(log t)次运行中完成。此伪代码仅适用于t和m为普通整数的情况。根据t和m的范围，您可以在合适的点使用BigInteger来修复函数内部的计算。

long solve(long t, long m) {
   if (t == 0) return 1 % m;
   if (t == 1) return t % m;
   long res = solve(t/2, m);
   res = (res * res) % m;
   if (t % 2 == 1) res = (res * 2) % m;
   return res;
}

感谢OldCurmudgeon。以上代码可以简化为一行：

BigInteger res = (new BigInteger("2")).
   modPow(new BigInteger("64"), new BigInteger("" + m));

这里是modPow的实现。该实现使用了不同的方法。算法从m开始: 将m拆分为m = 2^k*q。然后找到2^k和q的模数，然后使用中国剩余定理结合结果。

 public BigInteger modPow(BigInteger exponent, BigInteger m) {
        if (m.signum <= 0)
            throw new ArithmeticException("BigInteger: modulus not positive");

        // Trivial cases
        if (exponent.signum == 0)
            return (m.equals(ONE) ? ZERO : ONE);

        if (this.equals(ONE))
            return (m.equals(ONE) ? ZERO : ONE);

        if (this.equals(ZERO) && exponent.signum >= 0)
            return ZERO;

        if (this.equals(negConst[1]) && (!exponent.testBit(0)))
            return (m.equals(ONE) ? ZERO : ONE);

        boolean invertResult;
        if ((invertResult = (exponent.signum < 0)))
            exponent = exponent.negate();

        BigInteger base = (this.signum < 0 || this.compareTo(m) >= 0
                           ? this.mod(m) : this);
        BigInteger result;
        if (m.testBit(0)) { // odd modulus
            result = base.oddModPow(exponent, m);
        } else {
            /*
             * Even modulus.  Tear it into an "odd part" (m1) and power of two
             * (m2), exponentiate mod m1, manually exponentiate mod m2, and
             * use Chinese Remainder Theorem to combine results.
             */

            // Tear m apart into odd part (m1) and power of 2 (m2)
            int p = m.getLowestSetBit();   // Max pow of 2 that divides m

            BigInteger m1 = m.shiftRight(p);  // m/2**p
            BigInteger m2 = ONE.shiftLeft(p); // 2**p

            // Calculate new base from m1
            BigInteger base2 = (this.signum < 0 || this.compareTo(m1) >= 0
                                ? this.mod(m1) : this);

            // Caculate (base ** exponent) mod m1.
            BigInteger a1 = (m1.equals(ONE) ? ZERO :
                             base2.oddModPow(exponent, m1));

            // Calculate (this ** exponent) mod m2
            BigInteger a2 = base.modPow2(exponent, p);

            // Combine results using Chinese Remainder Theorem
            BigInteger y1 = m2.modInverse(m1);
            BigInteger y2 = m1.modInverse(m2);

            if (m.mag.length < MAX_MAG_LENGTH / 2) {
                result = a1.multiply(m2).multiply(y1).add(a2.multiply(m1).multiply(y2)).mod(m);
            } else {
                MutableBigInteger t1 = new MutableBigInteger();
                new MutableBigInteger(a1.multiply(m2)).multiply(new MutableBigInteger(y1), t1);
                MutableBigInteger t2 = new MutableBigInteger();
                new MutableBigInteger(a2.multiply(m1)).multiply(new MutableBigInteger(y2), t2);
                t1.add(t2);
                MutableBigInteger q = new MutableBigInteger();
                result = t1.divide(new MutableBigInteger(m), q).toBigInteger();
            }
        }

        return (invertResult ? result.modInverse(m) : result);
    }

对于第二部分：根据x和m的范围，您可以轻松使用BigInteger或普通计算。