modulo power (지수가 지수형태일 때)

https://codefights.com/forum/kk5YnGxknN9MtD2kF

a, n 이
a, n <= 1000 인 정수일 때
((a ** a) ** (a ** a)) mod n
를 구하는 문제.

https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/fast-modular-exponentiation 의 Step 2: Calculate mod C of the powers of two ≤ B
에서 문제를 푸는데 결정적인 도움을 받았다.

https://www.mtholyoke.edu/courses/quenell/s2003/ma139/js/powermod.html
로 검증을 했다.
a 가 매우 작은 수일 때만 가능했지만 말이다.


a, n 은 멤버변수로 되어 있다.

a, n 이 모두 양의 정수라고 가정하고 있다.

public int find(){
    int aamn = 1;
    for (int i = 1; i <= a; i++){
        aamn = aamn*a % n;
    }
    // aamn == (a ** a) mod n

    // here it finds (aamn ** (a ** a)) mod n.
    int r = aamn % n;
    System.out.println("aamn = " + aamn);
    for (int i = 1; i <= a; i++){
        int newR = 1;
        for (int j = 1; j <= a; j++){
            newR = (newR * r) % n;
        }
        r = newR;
        // r has (aamn ** (a ** i)) mod n
    }

    return r;
}