Как вычислить ^^ b mod m?

Question

Я должен эффективно вычислить a ^^ b mod m при больших значениях a, b, m < 2^32
где ^^ - оператор тетации: 2 ^^ 4 = 2^(2^(2^2)))

m не является простым числом, а не десятью.

Вы можете помочь?

Answer 1

Чтобы быть ясным, 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) mod m = a^T (a, b-1) mod m, мы хотим вычислить мощность mod m с чрезвычайно большим показателем. То, что вы можете использовать, состоит в том, что модульное возведение в степень является препериодическим с длиной препериода, которая не превышает наибольшую степень простого числа в простой факторизации m, которая не превышает log_2 m, а длина периода делит phi (m), где phi (m) есть Euler's totient function. Фактически длина периода делит Carmichael's function м, лямбда (м). Так,

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

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

Если Т (а, б-1)> [log_2 м], а затем

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

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

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

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

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

Вы заканчиваете вычисление степеней mod phi (m), затем мощность mod phi (phi (m)), затем мощности mod 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.