是否有用于计算的X模y中的乘法顺序的算法（用于Y <1000），其不需要一个BigInteger类型？

Question

我使用目前的算法运行到非常高的数字非常快。在算法的一个步骤，我到加注的 X 以应用到的 y中的欧拉函数的结果即可。其结果是，你可以遇到非常大的数字。

EG。当计算乘法订单 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

使用模幂，它没有得到多值比C更大的可能计算（10 ^ mOrder％53）或在一般情况下，任何（一个^ B模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;
}

Answer 2

为什么exponentiate？你就不能乘模的名词的在一个循环？

(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