累乗の中にmodを入れる操作

a^b = a^{b mod p-1} (mod p) が成り立つ.

proof.

フェルマーの小定理より a^p-1 = 1 (mod p)なので,mod pにおいて
a^b
= a^( (p-1)(floor(b/(p-1)) +(b mod (p-1)))
= ( (a^p-1)^{floor(b/(p-1))}) * a^{b mod (p-1)}
= a^{b mod (p-1)}