Ответ не содержит полного формального математического доказательства правильности.Я предположил, что это не нужно здесь.Кроме того, это было бы очень неразборчиво на SO (например, без MathJax).Я буду использовать (чуть чуть) специфический простой факторизация алгоритм.Это не лучший вариант, но достаточно.
tl; dr
Мы хотим вычислить a^x mod m.Мы будем использовать функцию modpow(a,x,m).Описано ниже.
- Если
x достаточно мало (не имеет экспоненциальной формы или существует p^x | m), просто вычислите его и верните - Разделите на простые числа и вычислите
p^x mod m отдельно длякаждое простое число, используя modpow функцию - Расчет
c' = gcd(p^x,m) и t' = totient(m/c') - Расчет
w = modpow(x.base, x.exponent, t') + t' - Сохранение
pow(p, w - log_p c', m) * c' в A Таблица
- Множество всех элементов из A и возврат по модулю m
Здесь pow должно выглядеть как паутинка питона.
Основная проблема:
Поскольку текущий лучший ответ касается только особого случая gcd(a,m) = 1, и OP не рассмотрел данное предположение, я решил написать этот ответ.Я также буду использовать полную теорему Эйлера .Цитируя Википедию:
Теорема Эйлера :Если n и a являются взаимно простыми положительными целыми числами, то 
где φ (n) равно функция времени Эйлера .
Предположение numbers are co-prime очень важно, как показывает Nabb в комментарии .Итак, во-первых, мы должны убедиться, что числа взаимно просты.(Для большей ясности предположим, что x = b^(c^...).) Поскольку 
, где 
, мы можем разложить a, отдельно вычислить q1 = (p1^alpha)^x mod m,q2 = (p2^beta)^x mod m... и затем вычислить ответ простым способом (q1 * q2 * q3 * ... mod m).Число имеет не более o(log a) простых факторов, поэтому мы будем вынуждены выполнить не более o(log a) вычислений.
Фактически нам не нужно делить на каждый простой фактор a (если нетвсе встречаются в m с другими показателями), и мы можем комбинировать с одним и тем же показателем, но это пока не заслуживает внимания.
Теперь рассмотрим проблему (p^z)^x mod m, где p простое.Обратите внимание на важное замечание:
Если a,b - положительные целые числа, меньшие m, а c - некоторое положительное целое число и 
, тогда true - это предложение 
.
Используя приведенное выше наблюдение, мы можем получить решение для актуальной проблемы.Мы можем легко рассчитать gcd((p^z)^x, m).Если x * z большие, это число, сколько раз мы можем разделить m на p.Пусть m' = m /gcd((p^z)^x, m).(Уведомление (p^z)^x = p^(z*x).) Пусть c = gcd(p^(zx),m).Теперь мы можем легко (см. Ниже) вычислить w = p^(zx - c) mod m', используя теорему Эйлера, потому что эти числа взаимно просты!А после, используя приведенное выше наблюдение, мы можем получить p^(zx) mod m.Исходя из вышеизложенного предположения wc mod m'c = p^(zx) mod m, поэтому ответ на данный момент - p^(zx) mod m = wc, а w,c легко вычислить.
Поэтому мы можем легко вычислить a^x mod m.
Вычислить a^x mod mиспользуя теорему Эйлера
Теперь предположим, что a,m взаимно просты.Если мы хотим вычислить a^x mod m, мы можем вычислить t = totient(m) и заметить a^x mod m = a^(x mod t) mod m.Это может быть полезно, если x велико и мы знаем только определенное выражение x, например, x = 7^200.
Посмотрите на пример x = b^c.мы можем вычислить t = totient(m) и x' = b^c mod t, используя возведение в степень, возводя в квадрат алгоритм во Θ(log c) времени.И после (используя тот же алгоритм) a^x' mod m, что равно решению.
Если x = b^(c^(d^...), мы решим его рекурсивно.Сначала вычислите t1 = totient(m), после t2 = totient(t1) и так далее.Например, возьмите x=b^(c^d).Если t1=totient(m), a^x mod m = a^(b^(c^d) mod t1), и мы можем сказать b^(c^d) mod t1 = b^(c^d mod t2) mod t1, где t2 = totient(t1).все, что мы вычисляем с использованием возведения в степень по алгоритму возведения в квадрат. Примечание : Если какой-то фактор не взаимно прост с показателем степени, необходимо использовать тот же трюк, что и в основной задаче (на самом деле, мы должны забыть, что он экспонентный и рекурсивно решить проблему, как в основнойпроблема).В приведенном выше примере, если t2 не является относительно простым с c, мы должны использовать этот трюк.
Вычислить φ(n)
Обратите внимание на простые факты:
- если
gcd(a,b)=1, то φ(ab) = φ(a)*φ(b) - , если
p простое φ(p^k)=(p-1)*p^(k-1)
Следовательно, мы можем разложить на множители n (ак. n = p1^k1 * p2^k2 * ...) и отдельно рассчитать φ(p1^k1),φ(p2^k2),..., используя факт 2. Затем скомбинируем это, используя факт 1. φ(n)=φ(p1^k1)*φ(p2^k2)*...
Стоит помнить, что, если мы будем вычислять многократно, мы можем захотеть использовать Сито Эратосфена и сохранить простые числа в таблице. Это уменьшит постоянную.
python пример: (правильно, по той же причине, что и этот алгоритм факторизации )
def totient(n) : # n - unsigned int
result = 1
p = 2 #prime numbers - 'iterator'
while p**2 <= n :
if(n%p == 0) : # * (p-1)
result *= (p-1)
n /= p
while(n%p == 0) : # * p^(k-1)
result *= p
n /= p
p += 1
if n != 1 :
result *= (n-1)
return result # in O(sqrt(n))
Дело: abc mod m
Потому что на самом деле он делает одно и то же много раз, я думаю, этот случай покажет вам, как решить эту проблему в целом.
Во-первых, мы должны разделить a на основные силы. Лучшим представлением будет пара <number,
exponent>.
c ++ 11 пример:
std::vector<std::tuple<unsigned, unsigned>> split(unsigned n) {
std::vector<std::tuple<unsigned, unsigned>> result;
for(unsigned p = 2; p*p <= n; ++p) {
unsigned current = 0;
while(n % p == 0) {
current += 1;
n /= p;
}
if(current != 0)
result.emplace_back(p, current);
}
if(n != 1)
result.emplace_back(n, 1);
return result;
}
После разделения мы должны вычислить (p^z)^(b^c) mod m=p^(z*(b^c)) mod m для каждой пары. Во-первых, мы должны проверить, если p^(z*(b^c)) | m. Если да, ответ просто (p ^ z) ^ (b ^ c), но это возможно только в том случае, если z,b,c очень мало. Я считаю, что мне не нужно показывать пример кода.
И наконец, если p^(z*b^c) > m, мы должны вычислить ответ. Во-первых, мы должны рассчитать c' = gcd(m, p^(z*b^c)). После того, как мы можем рассчитать t = totient(m'). и (z*b^c - c' mod t). Это простой способ получить ответ.
function modpow(p, z, b, c, m : integers) # (p^z)^(b^c) mod m
c' = 0
m' = m
while m' % p == 0 :
c' += 1
m' /= p
# now m' = m / gcd((p^z)^(b^c), m)
t = totient(m')
exponent = z*(b^c)-c' mod t
return p^c' * (p^exponent mod m')
и ниже Python рабочий пример :
def modpow(p, z, b, c, m) : # (p^z)^(b^c) mod m
cp = 0
while m % p == 0 :
cp += 1
m /= p # m = m' now
t = totient(m)
exponent = ((pow(b,c,t)*z)%t + t - (cp%t))%t
# exponent = z*(b^c)-cp mod t
return pow(p, cp)*pow(p, exponent, m)
Используя эту функцию, мы можем легко вычислить (p^z)^(b^c) mod m, после того, как нам просто нужно умножить все результаты (mod m), мы также можем вычислить все на постоянной основе. Пример ниже. (Надеюсь, я не ошибся, пишу.) Только предположение, b, c достаточно большие (b^c > log(m) ак. Каждый p^(z*b^k) не делит m), это простая проверка, и я не вижу указать, чтобы сделать беспорядок этим.
def solve(a,b,c,m) : # split and solve
result = 1
p = 2 # primes
while p**2 <= a :
z = 0
while a % p == 0 :
# calculate z
a /= p
z += 1
if z != 0 :
result *= modpow(p,z,b,c,m)
result %= m
p += 1
if a != 1 : # Possible last prime
result *= modpow(a, 1, b, c, m)
return result % m
Похоже, это работает.
DEMO и это правильно !