Bakana

$GCD(N^a-1,N^b-1)$
$= GCD(N^a-1-N^{a-b}(N^b-1), N^b-1)$
$= GCD(N^{a-b}-1, N^b-1)$

From here, we get the intuition (and this can be formally proved) that
$GCD(N^a-1,N^b-1) = N^{GCD(a,b)}-1$

So, using Bigmod, this problem can be solved in O(lgN) for every case.