On probable prime testing and the computation of square roots mod n

摘要

We will investigate two well-known square root finding algorithms which return the roots of some quadratic residue modulo a prime p. Instead of running the mechanisms modulo p we will investigate their behavior when applied modulo any integer n. In most cases the results will not be the square roots, when n is composite. Since the results obtained can easily be verified for correctness we obtain a very rapid probable prime test. Based on the square root finding mechanisms we will introduce two pseudoprimality tests which will be shown to be extremely fast and very efficient. Moreover, the proposed test for n ≡ 1 mod 4 will be proven to be even more efficient than Grantham's suggestion in [5].