Biginteger 유형이 필요하지 않은 X Modulo Y (y <1000의 경우)의 곱셈 순서를 계산하기위한 알고리즘이 있습니까?

Question

현재 사용하고있는 알고리즘은 매우 빠르게 매우 빠르게 진행됩니다. 알고리즘의 단계 엑스 적용되는 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

모듈 식 지수를 사용하면 C보다 훨씬 큰 값을 얻지 않고 (10 ^ morder % 53) 또는 일반적으로 (a ^ b mod 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

왜 지수인가인가? 모듈로를 곱할 수는 없습니다 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 (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