Euler Certificates Of Compositeness EC n ={ a 2 Z * n | a (n-1)/2  § 1 } NOT-EC n ={ a 2 Z * n | a (n-1)/2  § 1 } Fancier agrument: NOT-EC n is a subgroup of Z * n Hence, by Lagrange's theorem, if NOT-EC n  Z * n, then the size of NOT-EC n is no more than half the size of Z * n.
{}