Simple parallel algorithms for primality testing and integer factorization

Primality testing and integer factorization are two classic problems in number theory and are believed to be computationally intractable. At present, no one has found an efficient algorithm for factoring an integer or for proving its primality, nor has anyone proved that no such algorithm exists. Despite this, remarkable progress has been made in recent years. Many new algorithms, e.g. elliptic curve method (ECM), and number field sieve (NFS) have been proposed to approach these classic and difficult problems. But unfortunately, most of the modern algorithms require considerable mathematical sophistication, e.g. algebraic geometry and algebraic number theory to appreciate them. In this note, we present simple (particularly parallel) algorithms for primality testing and integer factorization based on naive elementary number theory and elementary algorithm design techniques, which is easy to understand for most undergraduate computer science and mathematics students.