[n, t, t2]=[415681338623, 2106331569, 9028142873] is a counterexample to the complex test (CT above). Hmm. I will try to find one for which gcd(a^3-a,n)==1.

Well that did not take long to fool: [n, a, t, t2]=[166827943, 3, 26368204, 65867518].

Next up, just test [n,a,2,4]. This is however 2 sub-tests with one parameter