Menu
I have to compute efficiently a^^b mod m for large values of a,b,m<2^32
where ^^ is the tetration operator: 2^^4=2^(2^(2^2))
m is not a prime number and not a power of ten.
Can you help?
206
mapvr3's blog. (a/b) (mod P) = (a * b^-1) (mod P) = (a (mod P) * b^-1 (mod P)) (mod P).
The first was defined in a previous lecture: a mod b denotes the remainder when we divide a by b. The "mod m" in a ≡ b (mod m) is a note on the side of the equation indicating what we mean when we say "≡" Fact: These two uses of "mod" are quite related: a ≡ b (mod m) if and only if a mod m = b mod m.
For a positive integer n, two integers a and b are said to be congruent modulo n (or a is congruent to b modulo n), if a and b have the same remainder when divided by n (or equivalently if a − b is divisible by n ). It can be expressed as a ≡ b mod n. n is called the modulus.
In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the modulus of the operation).
To be clear, a^^b is not the same thing as a^b, it is the exponential tower a^(a^(a^...^a)) where there are b copies of a, also known as tetration. Let T(a,b) = a^^b so T(a,1) = a and T(a,b) = a^T(a,b-1).
To compute T(a,b) mod m = a^T(a,b-1) mod m, we want to compute a power of a mod m with an extremely large exponent. What you can use is that modular exponentiation is preperiodic with preperiod length at most the greatest power of a prime in the prime factorization of m, which is at most log_2 m, and the period length divides phi(m), where phi(m) is Euler's totient function. In fact, the period length divides Carmichael's function of m, lambda(m). So,
a^k mod m = a^(k+phi(m)) mod m as long as k>log_2 m.
Be careful that a is not necessarily relatively prime to m (or later, to phi(m), phi(phi(m)), etc.). If it were, you could say that a^k mod m = a^(k mod phi(m)) mod m. However, this is not always true when a and m are not relatively prime. For example, phi(100) = 40, and 2^1 mod 100 = 2, but 2^41 mod 100 = 52. You can reduce large exponents to congruent numbers mod phi(m) that are at least log_2 m, so you can say that 2^10001 mod 100 = 2^41 mod 100 but you can't reduce that to 2^1 mod 100. You could define a mod m [minimum x] or use min + mod(a-min,m) as long as a>min.
If T(a,b-1) > [log_2 m], then
a^T(a,b-1) mod m = a^(T(a,b-1) mod phi(m) [minimum [log_2 m]])
otherwise just calculate a^T(a,b-1) mod m.
Recursively calculate this. You can replace phi(m) with lambda(m).
It doesn't take very long to compute the prime factorization of a number under 2^32 since you can determine the prime factors in at most 2^16 = 65,536 trial divisions. Number-theoretic function like phi and lambda are easily expressed in terms of the prime factorization.
At each step, you will need to be able to calculate modular powers with small exponents.
You end up calculating powers mod phi(m), then powers mod phi(phi(m)), then powers mod phi(phi(phi(m))), etc. It doesn't take that many iterations before the iterated phi function is 1, which means you reduce everything to 0, and you no longer get any change by increasing the height of the tower.
Here is an example, of a type that is included in high school math competitions where the competitors are supposed to rediscover this and execute it by hand. What are the last two digits of 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
So, 14^14^14^...^14 ends in the digits ...36.
57
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
