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

Question

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

Например.При расчете мультипликативный порядок из 10 по модулю 53:

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

Следующий алгоритм работает немного лучше с точки зрения избежания больших чисел, но он все равно терпит неудачу там, где 10^mЗаказать больше, чем емкость типа данных:

  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.Видеть Википедия для получения подробной информации также есть этот пример кода:

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

Зачем возводить в степень?Разве ты не можешь просто умножить по модулю? н в цикле?

(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