A^X=1 mod N;
if X is even, we can find quickly A^(X/2) (watch problem 1134).
If X is odd, we have to solve A*A^(X-1)/2=1 mod N. Therefore we have to find inverse number for A. And so on. Well, now, it's a fast quick recursion checking two cases...
Gonna check that soon...