如何計算^^ b mod m？

Question

對於a，b，m的大數值，我必須有效地計算a ^^ b mod m，其中^^是tetration運算符：2 ^^ 4 = 2 ^（2 ^（2^2 ））

m不是質數而不是十的冪。

你能幫忙嗎？

Answer 1

要清楚，a ^^ b與a^b不是一回事，它是指數塔a ^（a ^（a^...^a）），其中有b個副本，也被稱爲tetration。假設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_2m，週期長度除phi（m），其中phi（m）是Euler's totient function。實際上，週期長度除以m，lambda（m）的Carmichael's function。所以，

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

要小心，一個不一定相對素M（或更高版本，披（M），披（PHI（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.您可以將大指數減小爲至少log_2 m的全同數mod m（m）可以說2^10001 mod 100 = 2^41 mod 100，但是你不能把它減少到2^1 mod 100.你可以定義一個mod m [minimum x]或者使用min + mod（a-min，m）只要a> min。

如果T（A，B-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）模m。

遞歸地計算這個。你可以用lambda（m）替換phi（m）。

因爲您可以在至多2^16 = 65,536試驗分區中確定素數因子，所以計算2^32以下數字的素數因子分解不需要很長時間。像phi和lambda這樣的數論函數很容易用素因子分解來表示。

在每一步中，您都需要能夠計算具有小指數的模塊化功率。你最終計算功率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。