Cách tính a ^^ b mod m?

Question

Tôi phải tính toán hiệu quả một^^ b mod m cho các giá trị lớn của a, b, m < 2^32
trong đó^^ là toán tử tetration: 2 ^^ 4 = 2^(2^(2^2))

m không phải là số nguyên tố và không phải là số mười.

Bạn có thể trợ giúp không?

Answer 1

Để rõ ràng,^b không giống với^b, nó là tháp lũy thừa a^(a^(a^...^a)) trong đó có b bản sao của a, còn được gọi là tetration. Gọi T (a, b) = a^^ b để T (a, 1) = a và T (a, b) = a^T (a, b-1).

Để tính T (a, b) mod m = a^T (a, b-1) mod m, chúng tôi muốn tính toán công suất của mod m với số mũ cực lớn. Những gì bạn có thể sử dụng là lũy thừa môđun là tiền định kỳ với độ dài tiền chu kỳ ở mức lớn nhất lũy thừa của nguyên tố trong hệ số nguyên tố m, lớn nhất là log_2 m và độ dài phân chia phi (m), trong đó phi (m) là Euler's totient function. Trong thực tế, độ dài khoảng thời gian chia cho Carmichael's function của m, lambda (m). Vì vậy,

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

Hãy cẩn thận rằng một không nhất thiết phải tố cùng nhau với m (hoặc mới hơn, để phi (m), phi (phi (m)), vv). Nếu có, bạn có thể nói rằng^k mod m = a^(k mod phi (m)) mod m. Tuy nhiên, điều này không phải lúc nào cũng đúng khi a và m không tương đối chính. Ví dụ: phi (100) = 40 và 2^1 mod 100 = 2, nhưng 2^41 mod 100 = 52. Bạn có thể giảm số mũ lớn thành số đồng dư mod phi (m) ít nhất log_2 m, vì vậy bạn có thể nói rằng 2^10001 mod 100 = 2^41 mod 100 nhưng bạn không thể giảm điều đó thành 2^1 mod 100. Bạn có thể xác định mod mod [minimum x] hoặc sử dụng min + mod (a-min, m) miễn là một> phút.

Nếu T (a, b-1)> [log_2 m], sau đó

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

nếu không chỉ cần tính toán a^T (a, b-1) mod m.

Tính toán đệ quy này. Bạn có thể thay thế phi (m) bằng lambda (m). Không cần phải mất nhiều thời gian để tính toán hệ số chính của một số dưới 2^32 vì bạn có thể xác định được các thừa số chính ở tối đa là 2^16 = 65,536 đơn vị thử nghiệm. Hàm số lý thuyết như phi và lambda dễ dàng được thể hiện dưới dạng hệ số nguyên tố.

Ở mỗi bước, bạn sẽ cần để có thể tính toán các lũy thừa mô-đun với số mũ nhỏ.

Bạn kết thúc tính toán quyền hạn mod phi (m), sau đó quyền hạn mod phi (phi (m)), sau đó quyền hạn mod phi (phi (m)), v.v. Không mất nhiều lần lặp lại trước hàm phi tuyến lặp lại là 1, nghĩa là bạn giảm mọi thứ xuống 0 và bạn không còn nhận được bất kỳ thay đổi nào bằng cách tăng chiều cao của tháp.

Dưới đây là ví dụ về một loại được bao gồm trong các cuộc thi toán trung học, nơi các đối thủ cạnh tranh được cho là phải khám phá lại và thực thi nó bằng tay. Hai chữ số cuối cùng của 14 ^^ 2016 là gì?

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 

Vì vậy, 14^14^14^...^14 kết thúc bằng các chữ số ... 36.