Factorizing n and calculating φ(n), d(n), ω(n), σ(n), λ(n) and μ(n)

This is based on a primitive factoring program which uses the Brent-Pollard algorithm and Pollard's p-1 algorithm. It should work on integers with no more than 25 digits.
We factor out all primes less than 1000, leaving m as resulting cofactor. If m < 106, then m is prime and the factorization is complete. If m > 106, we subject m to Miller's test to bases 2,3,5,7. If m fails Miller's test to one of these bases, then m is composite. (Calc uses a superior Lucas-Lehmer test.)
If m passes Miller's test to all bases, then m is likely to be prime and we call m a quasi-prime.
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 < 106 and hence prime, or is a quasi-prime.
We continue until m has been completely factored as a product of powers of primes q with 103 < q < 106 and powers of quasi-primes r[0],...,r[c-1], each > 106.

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[0] is the first quasi-prime produced.
Factoring r[0] - 1 gives

r[0] - 1 = 2 · 32 ·5 · 47 · 65119 · r[1] · r[2],

where r[1]=1922567 and r[2]=1599337511 are quasi-primes. Also Selfridge's test goes through.
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 · 54 · 42649

and Selfridge's test shows that r[3] is a prime.

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

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

Enter n (1 > n < 1025):

Last modified 20th May 2005
Return to primes page
Return to number-theoretic functions page