Aufgabe

“Modulare Potenz”

a)

public int calc(int x, int p, int m){
    int y = 1;
    while (p > 0){
        while (p % 2 == 0){
            x = (x * x) % m;
            p /= 2;
        }
        y = (y * x) % m;
        p--;
    }
    return y;
}

b)

x	p	m	y
3	6	13	1
3	6	13	3
9	3	13	3
9	2	13	1
3	1	13	1
3	0	13	3