Я хочу вычислить am mod n, где n — простое число, а m — очень большое. Вместо этого с вычислением двоичной мощности я хотел бы найти такой x, что ax = a (mod n), а затем вычислить < strong>a(m mod x) mod n.
Очевидно, что такой x существует для любого a, потому что в какой-то момент задействует цикл mod n, но я не нашел, как вычислить его с помощью модульной арифметики. Интересно, я что-то упустил или, может быть, для этого существует какой-то численный метод?
Ваш модуль является простым, что позволяет легко начать, как по теореме Ферма (неуместно названной «маленькой»), затем
a^n ≡ a (mod n)
для всех a. Эквивалентом является формулировка
a^(n-1) ≡ 1 (mod n), if n doesn't divide a.
Тогда у вас есть
a^m ≡ 0 (mod n) if a ≡ 0 (mod n) and m > 0
и
a^m ≡ a^(m % (n-1)) (mod n) otherwise
(обратите внимание, что предложенное вами a^(m % x) в целом неверно, если m = q*x + r, у вас будет
a^m ≡ (a^x)^q * a^r ≡ a^q * a^r ≡ a^(q+r) (mod n)
и вам нужно будет повторить это сокращение для q+r, пока вы не получите показатель степени меньше, чем x).
Если вас действительно интересует наименьшее x > 1 такое, что a^x ≡ a (mod n), то снова случай a ≡ 0 (mod n) тривиален [x = 2], а для остальных случаев пусть y = min { k > 0 : a^k ≡ 1 (mod n) }, тогда искомое x = y+1, и, так как единицы в кольце Z/(n) образуют ( циклическая) группа порядка n-1, мы знаем, что y является делителем n-1.
Если у вас есть факторизация n-1, делители и, следовательно, кандидаты на y легко находятся и проверяются, поэтому найти y не составит труда, но обычно это намного больше работы, чем вычисление a^r (mod n) для одного единственного 0 <= r < n-1.
Найти факторизацию n-1 может быть тривиально (например, для простых чисел Ферма), но это также может быть очень сложно. Вдобавок к тому факту, что найти точный период a по модулю n обычно гораздо сложнее, чем просто вычислить a^r (mod n) для некоторого 0 <= r < n-1, очень сомнительно, стоит ли вообще пытаться еще больше уменьшить показатель степени.
Как правило, когда модуль не является простым числом, аналогичный случай, когда gcd(a,n) = 1, с заменой n-1 на λ(n) [где λ — это функция Кармайкла, которая дает наименьший показатель степени группы единиц Z/(n); для простых чисел n у нас есть λ(n) = n-1].
^это сила? сделал<sup>- person Grijesh Chauhan schedule 11.05.2013