Существует ли алгоритм вычисления мультипликативного порядка x по модулю y (для y <1000), который не требует типа BigInteger?

Question

Алгоритм, который я использую в данный момент, очень быстро набирает обороты. Шаг в алгоритме, который я делаю, вызывает x к результату функции totient, примененной к y. В результате вы можете столкнуться с очень большими числами.

Например. При расчете multiplicative order из 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) или в общем, любой (а^Ь мод с) без получения значения намного больше, чем с. См 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 multiplicative-order (a n) 
    (if (> (gcd a n) 1) 
     0 
     (do ((order 1 (+ order 1)) 
      (mod-exp a (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 
     while mod_exp != 1 : 
      order += 1 
      mod_exp = (mod_exp * a) mod n 
     return order