We factor out all primes less than 1000, leaving m as resulting cofactor. If m < 10

If m passes Miller's test to all bases, then m is likely to be prime and we call m a

In the case that m is composite, we subject m to the Brent-Pollard algorithm and hope that a non-trivial factor is found. If successful, the procedure is repeated until a factor of m is found that is either < 10

We continue until m has been completely factored as a product of powers of primes q with 10

Each of the quasi-primes is now subjected to Selfridge's test to try to establish its primality. Thus we apply the above factorization procedure to each of r[i]-1 and again apply Selfridge's test and so on. Eventually we end up applying Selfridge's test to produce only genuine primes < 10^{6}. On backtracking, this means that all quasi-primes have been verified to be primes.

In the rare event that one of the quasi-primes is in fact composite, thus causing Selfridge's test to fail at some level, we add an extra base prime to Miller's test and refactor n.

In CALC, if Brent-Pollard fails, we use MPQS (the multiple polynomial quadratic sieve), Pollard's p-1 test and the elliptic curve method.

(See *A Course in Computational Number Theory*, D. Bressoud, S. Wagon, Springer 2000.)

An example: n=846973255413646627833691.

n is not divisible by any primes < 1000. Also n > 10^{6} and passes all the Miller's tests; so n=r[0] is the first quasi-prime produced.

Factoring r[0] - 1 gives

r[0] - 1 = 2 · 3^{2} ·5 · 47 · 65119 · r[1] · r[2],

Factoring r[1] - 1 gives

r[1] - 1 = 2 · 961283

and Selfridge's test shows that r[1] is a prime.Factoring r[2] - 1 gives

r[2] - 1 = 2 · 5 · r[3]

where r[3]=159933751 is a quasi-prime. Also Selfridge's test goes through.Factoring r[3] - 1 gives

r[3] - 1 = 2 · 3 · 5^{4} · 42649

Hence r[2] is prime and so r[0] is a prime.

This is a BCMATH conversion of a modification of a BC program.

*Last modified 20th May 2005*

Return to primes page

Return to number-theoretic functions page