Integer factorization

In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. Prime factorization is achieved by limiting these factors to prime numbers.

Trial division

The trial division method can be used to determine whether a small integer is prime: just divide it by all the primes less than (or equal to) its square root. For example, to show 211 is prime, just divide by 2, 3, 5, 7, 11, and 13. Since none of these divides the number evenly, it is a prime.

The smallest divisor has to be a prime number. We remove the factor from the number, and repeat the process. If we cannot find any divisor in the range [2;√n], then the number itself has to be prime.

Wheel factorization

This is an optimization of the trial division. For wheel factorization, one starts from a small list of numbers, called the basis(first few prime numbers) then one generates the list, called the wheel, of the integers that are co-prime with all numbers of the basis. In order to find the smallest divisor of the number to be factorized, one divides it successively by the numbers on the basis, and in the wheel.

Wheel factorization

If we know that the number is not divisible by 2, we don’t need to check every other even number. This leaves us with only 50%50% of the numbers to check. After checking 2, we can simply start with 3 and skip every other number.

B-Smooth Numbers

The smooth numbers plays vital role in Cryptography. In Number Theory, an integer is known as B-Smooth if its prime factors are less than equals to B. Positive integer is said to be n-smooth if none of its prime factor is greater than n.

Example:

The Prime factors of 1620 are 22 × 34 × 5. So 1620 is said to be 5-smooth number because its prime factors are not greater than 5.

All 5-Smooth numbers are of the form of 2a × 3b × 5c, where a, b and c are positive integers.

• 2-Smmoth numbers are the power of 2.
• 5-Smooth numbers are called as regular numbers.
• 7-Smooth numbers are known as humble numbers.

Sieve of Eratosthenes

A Sieve of Eratosthenes is an algorithm for find out the prime numbers up to given natural number n. If size of n is comparatively small, then this method works well. It allows us to check whether any natural number less than or equal to n is composite or prime number.

How the Sieve of Eratosthenes can used to find out prime numbers up to given integer n number?

• Make a list of all integers from 2 to n. The first integer in the list is 2 because 2 is first prime number.
• Then remove every integer from the list which is multiple of 2 from the list. Then list contain numbers which are not multiple of 2, except 2.
• Then take next prime integer that is 3. Again cut every integer from list which are multiple of 3 and list all remaining numbers.
• Take next prime number which is 5. Remove every integer multiple of 5 and make list of all remaining integers.
• Continue with the same process until we find out list with all prime integers only.

Example: Find out all prime numbers up to 100. We found 25 prime numbers.

A special-purpose factoring algorithm’s running time depends on the properties of the number to be factored or on one of its unknown factors: size, special form, etc. The parameters which determine the running time vary among algorithms.

An important subclass of special-purpose factoring algorithms is the Category 1 or First Category algorithms, whose running time depends on the size of smallest prime factor. Given an integer of unknown form, these methods are usually applied before general-purpose methods to remove small factors.