Factoring Big Integers

M. Gallant 12/21/2001

This Java applet implements a basic routine to factor an arbitrarily large integer using Java 1.1+ java.math.BigInteger class arithmetic. The routine starts by extracting any factors of 2. After this, only odd numbers are tested up to the limit=Sqrt(number) + 1. This upper limit is determined by a BigInteger arbitrary-precision square-root method BigInteger bigRoot(BigInteger number). Each prime factor found reduces the required limit which is recalculated. The prime factors are displayed and the result is verified by direct BigInteger multiplication of the factors.

A similar standalone Java application version is available.

Primes by Java

64-bit factorization in C