是否有算法计算x模y(对于y <1000)的乘法顺序,不需要BigInteger类型？

使用模幂运算,可以计算(10 ^ mOrder%53)或通常任何(a ^ b mod c)而不会得到比c大得多的值.有关详细信息,请参阅维基百科,此示例代码也是如此:

Bignum modpow(Bignum base, Bignum exponent, Bignum modulus) {

    Bignum result = 1;

    while (exponent > 0) {
        if ((exponent & 1) == 1) {
            // multiply in this bit's contribution while using modulus to keep result small
            result = (result * base) % modulus;
        }
        // move to the next bit of the exponent, square (and mod) the base accordingly
        exponent >>= 1;
        base = (base * base) % modulus;
    }

    return result;
}

为什么取幂？难道你不能在循环中乘以模数n吗？

(defun multiplicative-order (a n)
  (if (> (gcd a n) 1)
      0
      (do ((order 1 (+ order 1))
           (mod-exp (mod a n) (mod (* mod-exp a) n)))
          ((= mod-exp 1) order))))

或者,在ptheudo(原文如此)代码中:

def multiplicative_order (a, n) :
    if gcd (a, n) > 1 :
        return 0
      else:
        order = 1
        mod_exp = a mod n
        while mod_exp != 1 :
            order += 1
            mod_exp = (mod_exp * a) mod n
        return order