section_path: Computational methods/Integer factorization
section_name: Integer factorization
paragraph_text: Integer factorization
  
  Given a composite integer n {\displaystyle n}, the task of providing one (or all) prime factors is referred to as factorization of n {\displaystyle n}. It is significantly more difficult than primality testing, and although many factorization algorithms are known, they are slower than the fastest primality testing methods. Trial division and Pollard's rho algorithm can be used to find very small factors of n {\displaystyle n}, and elliptic curve factorization can be effective when n {\displaystyle n} has factors of moderate size. Methods suitable for arbitrary large numbers that do not depend on the size of its factors include the quadratic sieve and general number field sieve. As with primality testing, there are also factorization algorithms that require their input to have a special form, including the special number field sieve. As of December 2019 the largest number known to have been factored by a general-purpose algorithm is RSA-240, which has 240 decimal digits (795 bits) and is the product of two large primes.
  
  Shor's algorithm can factor any integer in a polynomial number of steps on a quantum computer. However, current technology can only run this algorithm for very small numbers. As of October 2012 the largest number that has been factored by a quantum computer running Shor's algorithm is 21.