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

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

Например. При вычислении множительного порядка 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

algorithm math discrete-mathematics
person ilitirit    schedule 13.03.2009    source источник
comment
Не часть исходного вопроса, а изящный способ объединить ответы от @schnaader и @Svante. Множительный порядок, который вы ищете, должен делить totient(c), поэтому вам не нужно проверять каждое a^b. Если вы перечисляете делители totient (c), вы можете использовать метод @schnaader для возведения в степень, а метод @Svante использовать уже вычисленные результаты для вычисления других, например 10 ^ 1, 10 ^ 2 (путем возведения в квадрат), 10 ^ 4 (возводя в квадрат), 10^13 = (10^4)^3 * (10^1), 10^26 (возводя в квадрат). (Если это ни один из них, он должен быть 52).   -  person Chris Nash    schedule 01.03.2011

Ответы (2)


arrow_upward
7
arrow_downward

Используя модульное возведение в степень, можно вычислить (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;
}
person schnaader    schedule 13.03.2009
comment
Не могу поверить, что я забыл об этом, особенно учитывая, что я использовал его два дня назад. Думаю, мне нужен кофе. - person ilitirit; 13.03.2009
comment
Или, может быть, немного поспать и выпить кофе после этого;) - person schnaader; 13.03.2009

arrow_upward
6
arrow_downward

Зачем возводить в степень? Разве вы не можете просто умножить по модулю 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
person Svante    schedule 13.03.2009
comment
Вы проверили код для a = 49 и n = 3? Я получаю 2, но должен быть 1. Что я делаю не так? - person Hans-Peter Stricker; 07.12.2018
comment
Вы правы, была ошибка. Исправлено: нужно также делать модуль для начального значения. - person Svante; 07.12.2018
comment
Кроме того, это не должно возвращать 0, если аргументы не взаимно просты, но сигнализировать об ошибке. - person Svante; 07.12.2018