algorithm - 是否有一种算法可以计算不需要 BigInteger 类型的 x 模 y（对于 y < 1000）的乘法阶数？

Question

我目前使用的算法很快就会遇到非常高的数字。我要在算法中的一个步骤将x提高到应用于y的 totient 函数的结果。结果是您可能会遇到非常大的数字。

例如。计算10 模 53的乘法阶数时：

10^totient(53) == 10^52 == 1 * 10^52

以下算法在避免大数字方面表现更好，但在10^mOrder大于数据类型的容量时仍然失败：

  mOrder = 1
  while 10^mOrder % 53 != 1
      if mOrder >= i
          mOrder = 0;
          break
      else
          mOrder = mOrder + 1

Answer 1

使用模幂运算，可以计算 (10 ^ mOrder % 53) 或一般情况下的任何 (a ^ b mod c)，而不会得到比 c 大得多的值。有关详细信息，请参阅Wikipedia，也有此示例代码：

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;
}

Answer 2

为什么要取幂？你不能在一个循环中乘以模n吗？

(defun 乘法阶数 (an)
  （如果（>（gcd an）1）
      0
      （做（（订单1（+订单1））
           (mod-exp (mod an) (mod (* mod-exp a) n)))
          ((= mod-exp 1) 顺序))))

或者，在 ptheudo (sic) 代码中：

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