Prime factorization of a number is the process if writing a number as a product of prime numbers. A Prime factorization algorithm is expected to list the general steps involved in finding the prime factorization of a number. A software program written based on such algorithm can thus be used by computer systems to determine the prime factorization of large numbers quickly.
Difficulty in writing a general algorithm
The fundamental theorem of arithmetic guarantees that every positive
integer has a unique prime factorization.But the complex way the prime numbers
are distributed in the set of real numbers does not make it easy to
find a general algorithm that can be used efficiently with very
large numbers. It is especially difficult to find algorithms to crack cryptographic applications which use product of very large prime numbers.
Hence an efficient algorithm can be written only by making use of some additional information about the number whose prime factorization is to be written.
Simplest algorithm to find the prime factorization.
The general method used for finding the prime factors of a number or trial divisions. If the given number consists of two or three digits this can be achieved in few steps. As this involved repeated trials this method is practical only for small numbers. We can write the steps for this direct trial factorization as follows:
- Test the divisibility of the number with the smallest prime number 2.
- If it is divisible by 2, then write the number as a product of 2 and the quotient obtained on division. If it is not divisible by 2 then step 4.
- If the quotient is divisible by 2 continue division. Continue division till you get a quotient which is not divisible by 2.
- Try doing the trials described in steps 1 to 3 for the next prime number.
- Stop the trials when the quotient obtained in a trial process is a prime number.
Let us see how the algorithm works with the number 3768.
1. 3768 is an even number. Hence it is divisible by 2.
2. On division by 2 we get the quotient as 1884. Hence the first factored form is 3768 = 2 x 1884
3. The quotient got in step 2 is again divisible by 2 and we get a quotient of 942 on dividing 1884 by 2. 3768 = 2 x 2 x 942
One more division with 2 is possible we get the factored form as 3768 = 2 x 2 x 2 x 471
4. We need to test the divisibility of 471 with 3. Since the sum of the digits 4 + 7 + 1 =12 is divisible by 3, the number is divisible by 3.
And the factored form now becomes 3768 = 2 x 2 x 2 x 3 x 157
5. As 157 is a prime number, the division has to be stopped.
Hence the prime factorization of 3768 is 3768 = 2 x 2 x 2 x 3 x 157
or using exponents, 157 = 23 x 3 x 157