if (x^2)%n is 1 then x%n has to be 1 or -1. So isn’t it enough to check if (a^d)%n is 1 or -1 ? Because if it isn’t 1 or -1 then (a^(d2))%n , … , (a^(d2^s))%n i.e (a^n)%n can never be 1.
if (x^2)%n is 1 then x%n has to be 1 or -1. So isn’t it enough to check if (a^d)%n is 1 or -1 ? Because if it isn’t 1 or -1 then (a^(d2))%n , … , (a^(d2^s))%n i.e (a^n)%n can never be 1.