Рассчитайте n, где a ^ n mod m = 1?
Какой самый быстрый способ вычислить первое n, удовлетворяющее уравнению
^ ^ мод м = 1
Здесь a, n, m может быть простым или составным
mod: является оператором модуля
Решение
Что не так с прямым способом:
int mod_order(int m, int a) {
for(int n = 1, an = a; n != m; n++, an = an * a % m) if(an % m == 1) return n;
return -1;
}
Другие решения
- Если gcd (a, m)> 1, то такого n не существует. (Очевидные)
- В противном случае, если m простое число, n = m-1. (доказательство)
- В противном случае (и в более общем случае) n = ф (m), где ф — функция Эйлера. (доказательство)
Как видите, вычисление ф (m), по сути, аналогично факторизации m. Это можно сделать за время sqrt (m) или быстрее, в зависимости от того, насколько сложным является алгоритм, который вы используете. Простой:
int phi(m){
if(m==1) return 1;
for(int d=2; d*d<m; ++d){
if(m%d != 0) continue;
int deg = 1; long acc=1;
for(; m%(acc*d)==0; ++deg) acc*=d;
acc /= d;
return phi(m/acc)*acc*(d-1)/d;
}
return m-1;
}
Upd: мой плохой. a ^ (ф (m)) = 1 (mod m), но может быть меньшее значение n (для a = 1, n = 1, без разницы, что такое m; для a = 14, m = 15, n = 2). n — делитель ф (m), но эффективное вычисление минимально возможного n кажется сложным. Задача может быть разделена с помощью этот теорема (минимальное n является наименьшим общим кратным для всех степеней для соответствующих остатков). Но когда m простое число или имеет достаточно большой простой делитель, и есть только один a (в отличие от вычисления n для множества различных a с одним и тем же m), у нас как бы нет выбора. Вы можете посмотреть на 1, 2.