A prime factorization algorithm which can be implemented in a single-step or double-step form. In the single-step version, a prime factor p of a number n can be found if p - 1 is a product of small primes by finding an m such that m congruent c^q (mod n), where p - 1|q, with q a large number and (c, n) = 1. Then since p - 1|q, m congruent 1 (mod p), so p|m - 1. There is therefore a good chance that n not vertical bar m - 1, in which case GCD(m - 1, n) (where GCD is the greatest common divisor) will be a nontrivial divisor of n. In the double-step version, a prime factor p can be found if p - 1 is a product of small primes and a single larger prime.

prime factorization algorithms | Williams p+1 factorization method