Как вычислить a^^b по модулю m?

Чтобы было ясно, a^^b — это не то же самое, что a^b, это экспоненциальная башня a^(a^(a^...^a)) где есть b копий a, также известная как тетрация . Пусть T(a,b) = a^^b, поэтому T(a,1) = a и T(a,b) = a^T(a,b-1).

Чтобы вычислить T(a,b) по модулю m = a^T(a,b-1) по модулю m, мы хотим вычислить степень по модулю m с чрезвычайно большим показателем степени. Что вы можете использовать, так это то, что модульное возведение в степень является предпериодическим с длиной предпериода, не превышающей наибольшую степень простого числа в простой факторизации m, которая не превышает log_2 m, а длина периода делит phi (m), где phi (m) это функция Эйлера. На самом деле длина периода делит функцию Кармайкла от m, lambda(m). Так,

a^k mod m = a^(k+phi(m)) mod m as long as k>log_2 m.

Обратите внимание, что a не обязательно взаимно просто с m (или позднее с phi(m), phi(phi(m)) и т. д.). Если бы это было так, вы могли бы сказать, что a^k mod m = a^(k mod phi(m)) mod m. Однако это не всегда верно, когда a и m не взаимно просты. Например, phi(100) = 40, и 2^1 по модулю 100 = 2, но 2^41 по модулю 100 = 52. Вы можете уменьшить большие показатели степени до конгруэнтных чисел по модулю фи(m), которые составляют не менее log_2 m, так что вы можно сказать, что 2 ^ 10001 по модулю 100 = 2 ^ 41 по модулю 100, но вы не можете уменьшить это до 2 ^ 1 по модулю 100. Вы можете определить мод m [минимум x] или использовать min + mod (a-min, m) пока a>мин.

Если T(a,b-1) > [log_2 m], то

a^T(a,b-1) mod m = a^(T(a,b-1) mod phi(m) [minimum [log_2 m]])

в противном случае просто вычислите a ^ T (a, b-1) по модулю m.

Рекурсивно вычислите это. Вы можете заменить фи(м) на лямбда(м).

Вычисление простой факторизации числа меньше 2 ^ 32 не займет много времени, поскольку вы можете определить простые множители не более чем за 2 ^ 16 = 65 536 пробных делений. Теоретико-числовые функции, такие как фи и лямбда, легко выражаются в терминах простой факторизации.

На каждом этапе вам нужно будет уметь вычислять модульные степени с малыми показателями.

Вы в конечном итоге вычисляете мощность по модулю phi(m), затем мощность по модулю phi(phi(m)), затем мощность по модулю phi(phi(phi(m))) и т. д. Не требуется так много итераций, прежде чем повторяющийся phi функция равна 1, что означает, что вы сводите все к 0, и вы больше не получаете никаких изменений, увеличивая высоту башни.

Вот пример того типа, который включается в школьные математические соревнования, где участники должны заново открыть это и выполнить вручную. Какие две последние цифры числа 14^^2016?

14^^2016 mod 100 
= 14^T(14,2015) mod 100
= 14^(T(14,2015) mod lambda(100) [minimum 6]) mod 100
= 14^(T(14,2015 mod 20 [minimum 6]) mod 100

T(14,2015) mod 20 
= 14^T(14,2014) mod 20
= 14^(T(14,2014) mod 4 [minimum 4]) mod 20

T(14,2014) mod 4
= 14^T(14,2013) mod 4
= 14^(T(14,2013 mod 2 [minimum 2]) mod 4

T(14,2013) mod 2
= 14^T(14,2012) mod 2
= 14^(T(14,2012 mod 1 [minimum 1]) mod 2
= 14^(1) mod 2
= 14 mod 2
= 0

T(14,2014) mod 4 
= 14^(0 mod 2 [minimum 2]) mod 4
= 14^2 mod 4
= 0

T(14,2015) mod 20
= 14^(0 mod 4 [minimum 4]) mod 20 
= 14^4 mod 20
= 16

T(14,2016) mod 100
= 14^(16 mod 20 [minimum 6]) mod 100
= 14^16 mod 100
= 36

Итак, 14^14^14^...^14 оканчивается цифрами ...36.