Ответ 1
Ответ не содержит полного формального математического доказательства правильности. Я предположил, что здесь нет необходимости. Кроме того, на 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 и return modulo m
Здесь pow должен выглядеть как python pow.
Основная проблема:
Поскольку текущий лучший ответ касается только особого случая gcd(a,m) = 1, и ОП не рассматривал это предположение, я решил написать этот ответ. Я также буду использовать теорему Эйлера для верного пользователя. Цитирование википедии:
Теорема об эквиваленте Эйлера:
ЕслиnиAявляются взаимно простыми целыми числами, тогде φ (n) Функция подобия Эйлера.
где φ (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 является предложением
.
, тогда 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)
Обратите внимание на простые факты:
- if
gcd(a,b)=1, тогдаφ(ab) = φ(a)*φ(b) - если
pявляется простымφ(p^k)=(p-1)*p^(k-1)
Поэтому мы можем факторизовать n (ak. 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))
Случай: A b cmod m
Потому что это на самом деле делает то же самое много раз, я считаю, что этот случай покажет вам, как это решить в целом.
Во-первых, мы должны разделить A на простые степени. Лучшим представлением будет пара <number,
exponent>.
С++ 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;
}
После split мы должны вычислить (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) ak. Each 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 и it correct!