Ответ 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) Функция подобия Эйлера.

Предположение 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)

Обратите внимание на простые факты:

• 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!

Ответ 2

a ^{b c} mod m = a ^{b c mod n} mod m, где n = φ ( m) Функция подобия Эйлера.

Если m простое, то n = m-1.

Изменить: как указывал Nabb, это выполняется только в том случае, если a взаимно прост в m. Поэтому сначала вам нужно проверить это.

Ответ 3

• Так как для любого отношения a=x^y, отношение инвариантно относительно используемой числовой базы (основание 2, основание 6, база 16 и т.д.).

• Так как операция mod N эквивалентна извлечению младшей значащей цифры (LSD) в базе N

• Поскольку LSD результата A в базе N может быть затронуто только LSD X в базе N, а не цифры в более высоких местах. (например, 34 * 56 = 30 * 50 + 30 * 6 + 50 * 4 + 4 * 5 = 10 * (3 + 50 + 3 * 6 + 5 * 4) + 4 * 6)

Следовательно, из LSD(A)=LSD(X^Y) можно вывести

LSD(A)=LSD(LSD(X)^Y)

Поэтому

A mod N = ((X mod N) ^ Y) mod N

и

(X ^ Y) mod N = ((X mod N) ^ Y) mod N)

Поэтому вы можете сделать mod перед каждым шагом мощности, который сохраняет ваш результат в диапазоне целых чисел.

Это предполагает, что a не отрицательно, и для любого x ^ y, a ^ y < MAXINT

Этот ответ отвечает на неправильный вопрос. (Alex)

Ответ 4

Модульное возведение в степень - это правильный способ решить эту проблему, здесь немного намека:

Чтобы найти a ^{b c d}% m Вы должны начать с расчета a% m, то a ^b% m, то a ^{b c}% m, а затем a ^{b c d}% m... (вы получаете идею)

Чтобы найти a ^b% m, вам в основном нужны две идеи: [Пусть B = пол (b/2)]

Таким образом,
, если b четно
a ^b% m = (a ^B% m) ²% m или если b нечетно
a ^b% m = ((a ^B% m) ²) * (a% m))% m

Итак, если вы знаете значение ^B вы можете рассчитать это значение.

Чтобы найти a ^B примените аналогичный подход, разделив B, пока не достигнете 1.

например. Для вычисления 16 ¹³% 11:

16 ¹³% 11 = (16% 11) ¹³% 11 = 5 ¹³% 11 = (5 ⁶% 11) * (5 ⁶% 11) * (5% 11) < ---- (I)

Найти 5 ⁶% 11:
5 ⁶% 11 = ((5 ³% 11) * (5 ³% 11))% 11 < ---- ( II)
Найти 5 ³% 11:
5 ³% 11 = ((5 ¹% 11) * (5 ¹% 11) * (5% 11))% 11 < ш >= (((5 * 5)% 11) * 5)% 11 = ((25% 11) * 5)% 11 = (3 * 5)% 11 = 15% 11 = 4
Включение этого значения в (II) дает 5 ⁶% 11 = ((4 * 4)% 11) * 5)% 11 = ((16% 11) * 5)% 11 = (5 * 5)% 11 = 25% 11 = 3
Подключение этого значения к (I) дает 5 ¹³% 11 = ((3% 11) * (3% 11) * 5)% 11 = ((9% 11) * 5)% 11 = 45% 11 = 4

Таким образом, 5 ¹³% 11 = 4
С этим вы можете вычислить что угодно: ^{5 13}% 11 и т.д.

Ответ 5

Посмотрите на поведение A^X mod M по мере увеличения X. Он должен в конечном итоге перейти в цикл. Предположим, что цикл имеет длину P и начинается после шагов N. Тогда X >= N следует A^X = A^(X+P) = A^(X%P + (-N)%P + N) (mod M). Поэтому мы можем вычислить A^B^C, вычислив y=B^C, z = y < N ? y : y%P + (-N)%P + N, return A^z (mod m).

Обратите внимание, что мы можем рекурсивно применить эту стратегию к дереву власти, потому что производное уравнение либо имеет показатель < M или экспонента, включающая меньшую экспоненциальную башню с меньшим дивидендом.

Вопрос только в том, что вы можете эффективно вычислить N и P с учетом A и M. Обратите внимание, что переоценка N прекрасна. Мы можем просто установить N на M, и все будет работать. P немного сложнее. Если A и M - разные простые числа, то P=M-1. Если A имеет все M простые множители, то мы застреваем в 0 и P=1. Я оставлю это как упражнение, чтобы понять это, потому что я не знаю, как это сделать.

///Returns equivalent to list.reverse().aggregate(1, acc,item => item^acc) % M
func PowerTowerMod(Link<int> list, int M, int upperB = M)
    requires M > 0, upperB >= M
    var X = list.Item
    if list.Next == null: return X
    var P = GetPeriodSomehow(base: X, mod: M)
    var e = PowerTowerMod(list.Next, P, M)
    if e^X < upperB then return e^X //todo: rewrite e^X < upperB so it doesn't blowup for large x
    return ModPow(X, M + (e-M) % P, M)

Ответ 6

Ответ на Tacet хорош, но возможны существенные упрощения.

Силы x, mod m являются перпериодическими. Если x взаимно просто с m, то степени x являются периодическими, но даже без этого предположения часть до периода не длинна, максимум максимум показателей в простой факторизации m, которая не превышает log_2 m, Длина периода делит phi (m), а на самом деле лямбда (m), где lambda функция Кармайкл, максимальный мультипликативный порядок mod m, Это может быть значительно меньше, чем phi (m). Lambda (m) можно быстро вычислить из простой факторизации m, точно так же, как phi (m). Lambda (m) - GCD лямбда (p_i ^ e_i) по всем простым степеням p_i ^ e_i в простой факторизации m, а для нечетных простых степеней lambda (p_i ^ e_i) = phi (p_i ^ e ^ i). lambda (2) = 1, lamnda (4) = 2, lambda (2 ^ n) = 2 ^ (n-2) для больших степеней 2.

Определите modPos (a, n) как представитель класса конгруэнции a в {0,1,.., n-1}. Для неотрицательного a это просто% n. Для отрицательного значения, по какой-либо причине,% n определяется как отрицательный, поэтому modPos (a, n) является (a% n) + n.

Определите modMin (a, n, min) как наименьшее положительное целое, совпадающее с mod n, которое не менее min. Для положительного значения вы можете вычислить это как min + modPos (a-min, n).

Если b ^ c ^... меньше log_2 m (и мы можем проверить, выполняется ли это неравенство рекурсивно, беря логарифмы), то мы можем просто вычислить a ^ b ^ c ^... В противном случае a ^ b ^ c ^... mod m = a ^ modMin (b ^ c ^..., lambda (m), [log_2 m])) mod m = a ^ modMin (b ^ c ^... mod lambda (m), lambda (m), [log_2 m]).

Например, предположим, что мы хотим вычислить 2 ^ 3 ^ 4 ^ 5 mod 100. Заметим, что 3 ^ 4 ^ 5 имеет только 489 цифр, поэтому это можно сделать другими способами, но оно достаточно велико, чтобы вы не хотите вычислить его напрямую. Однако по методам, которые я привел здесь, вы можете вручную вычислить 2 ^ 3 ^ 4 ^ 5 мод 100.

Так как 3 ^ 4 ^ 5 > log_2 100,

2^3^4^5 mod 100 
= 2^modMin(3^4^5,lambda(100),6) mod 100 
= 2^modMin(3^4^5 mod lambda(100), lambda(100),6) mod 100
= 2^modMin(3^4^5 mod 20, 20,6) mod 100.

Пусть вычисляется 3 ^ 4 ^ 5 mod 20. Поскольку 4 ^ 5 > log_2 20,

3^4^5 mod 20 
= 3^modMin(4^5,lambda(20),4) mod 20 
= 3^modMin(4^5 mod lambda(20),lambda(20),4) mod 20
= 3^modMin(4^5 mod 4, 4, 4) mod 20
= 3^modMin(0,4,4) mod 20
= 3^4 mod 20
= 81 mod 20
= 1

Мы можем подключить это к предыдущему вычислению:

2^3^4^5 mod 100 
= 2^modMin(3^4^5 mod 20, 20,6) mod 100
= 2^modMin(1,20,6) mod 100
= 2^21 mod 100
= 2097152 mod 100
= 52.

Заметим, что 2 ^ (3 ^ 4 ^ 5 mod 20) mod 100 = 2 ^ 1 mod 100 = 2, что неверно. Вы не можете свести к допериодической части полномочий базы.