Factoring algorithm

A factoring algorithm is an algorithm that finds the prime factorization of an integer.

There is currently no known efficient factoring algorithm. Every factoring algorithm so far has a time complexity that is higher order than \(O(n^k)\), polynomial time. The most widely used public-key encryption algorithm, the RSA algorithm, is completely dependent on the computational difficulty of finding the prime factorization of a large composite integer.

With that said, let's look at some inefficient factoring algorithms!

Trial division

By extending the trial division implementation of a primality test, you can generate the prime factorization of an integer as a sequence of prime factors:

algorithm factorize is
    input: one integer, n > 1
    output: its prime factorization, as a sequence of integers

    prime_factors ← []
    for f = 2 to (n - 1)
        while n mod f = 0
            append f to prime_factors
            n ← n div f
    if n > 1
        append n to prime_factors
    return prime_factors

A sequence is different from a set in that it allows duplicate elements. This means the multiplicities of each prime factor will be represented correctly in prime_factors when the algorithm is done running. With optimizations similar to what was done with primality tests, this algorithm can become twice as efficient:

algorithm factorize is
    input: one integer, n > 1
    output: its prime factorization, as a sequence of integers

    prime_factors ← []
    while n mod 2 = 0
        append 2 to prime_factors
        n ← n div 2
    f ← 3
    while f ≤ floor(√n) (floor function ensures √n is an integer)
        if n mod f = 0
            append f to prime_factors
            n ← n div f
        else
            f ← f + 2
    if n > 1
        append n to prime_factors
    return prime_factors

Even after optimization, the algorithm is still not efficient enough to find the prime factorization of a large composite integer in a reasonable amount of time... on a classical computer. With quantum computers, which are exponentially faster, this algorithm could hypothetically break RSA encryption.