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 < 106. 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 > 106 and passes all the Miller's tests; so n=r is the first quasi-prime produced.
Factoring r - 1 gives
r - 1 = 2 · 32 ·5 · 47 · 65119 · r · r,where r=1922567 and r=1599337511 are quasi-primes. Also Selfridge's test goes through.
r - 1 = 2 · 961283and Selfridge's test shows that r is a prime.
r - 1 = 2 · 5 · rwhere r=159933751 is a quasi-prime. Also Selfridge's test goes through.
r - 1 = 2 · 3 · 54 · 42649and Selfridge's test shows that r 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