Math 2.0

Number theory Finite fields and computational number theory Problem

Integer factorization

Builds on Composite numberPrime factorizationPrime numberExistence of prime factorizationRSA cryptosystemFundamental theorem of arithmeticAKS primality test

Problem

Given a composite number nn, written in binary, find integers aa and bb with 1<a,b<n1 < a, b < n and n=abn = ab. Repeating this step gives the prime factorization of nn. The open question is whether there is a classical algorithm that does this in a number of bit operations bounded by a polynomial in log⁡n\log n.

Remarks

The prime factorization exists and is unique by the existence of prime factorization and the fundamental theorem of arithmetic, so the problem is about the cost of finding it. Trial division by all integers up to n\sqrt n always works, but it needs about n\sqrt n steps, which is exponential in the number of digits. No polynomial-time classical algorithm is known. The fastest known general method for large numbers is the general number field sieve, whose heuristic running time is exp⁡((64/93+o(1))(ln⁡n)1/3(ln⁡ln⁡n)2/3).\exp\left( \left( \sqrt[3]{64/9} + o(1) \right) (\ln n)^{1/3} (\ln \ln n)^{2/3} \right). The decision version, which asks whether nn has a factor dd with 1<d<k1 < d < k for a given kk, lies in both NP and co-NP. For this reason it is not expected to be NP-complete, but this is not proved. On a quantum computer, Shor's algorithm factors nn in polynomial time. Deciding whether nn is prime is easier: the AKS primality test does it in deterministic polynomial time, without finding any factor.

Reading path

To understand this page from the ground up, read these 32 pages in order. The foundations come first.

Show the path as a graph
Composite number, concept, no evidence levelComposite numberconceptDivisibility, definition, no evidence levelDivisibilitydefinitionEuler's totient function, concept, no evidence levelEuler's totient funct…conceptGroup, concept, no evidence levelGroupconceptModular exponentiation, concept, no evidence levelModular exponentiationconceptMultiplicative order, concept, no evidence levelMultiplicative orderconceptPolynomial ring, concept, no evidence levelPolynomial ringconceptPrime factorization, concept, no evidence levelPrime factorizationconceptPrime number, concept, no evidence levelPrime numberconceptQuotient ring, concept, no evidence levelQuotient ringconceptCongruence modulo n, definition, no evidence levelCongruence modulo ndefinitionGreatest common divisor, definition, no evidence levelGreatest common divis…definitionPrime number, definition, no evidence levelPrime numberdefinitionRing, definition, no evidence levelRingdefinitionModular multiplicative inverse, definition, no evidence levelModular multiplicativ…definitionCoprime integers, definition, no evidence levelCoprime integersdefinitionFermat's little theorem, statement, no evidence levelFermat's little theor…statementEuclid's lemma, statement, no evidence levelEuclid's lemmastatementExistence of a prime divisor, statement, no evidence levelExistence of a prime …statementPrimality test, concept, no evidence levelPrimality testconceptPrime factorization, definition, no evidence levelPrime factorizationdefinitionCharacteristic of a ring, definition, no evidence levelCharacteristic of a r…definitionCommutative ring, definition, no evidence levelCommutative ringdefinitionEuler's totient function, definition, no evidence levelEuler's totient funct…definitionMiller–Rabin primality test, concept, no evidence levelMiller–Rabin primalit…conceptExistence of prime factorization, statement, no evidence levelExistence of prime fa…statementFreshman's dream, statement, no evidence levelFreshman's dreamstatementEuler's theorem, statement, no evidence levelEuler's theoremstatementFundamental theorem of arithmetic, statement, no evidence levelFundamental theorem o…statementAKS primality test, statement, no evidence levelAKS primality teststatementRSA cryptosystem, example, no evidence levelRSA cryptosystemexampleInteger factorization, problem, no evidence levelInteger factorizationproblem
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Composite number concept
  2. Divisibility definition
  3. Euler's totient function concept
  4. Group concept
  5. Modular exponentiation concept
  6. Multiplicative order concept
  7. Polynomial ring concept
  8. Prime factorization concept
  9. Prime number concept
  10. Quotient ring concept
  11. Congruence modulo n definition
  12. Greatest common divisor definition
  13. Prime number definition
  14. Ring definition
  15. Modular multiplicative inverse definition
  16. Coprime integers definition
  17. Fermat's little theorem statement
  18. Euclid's lemma statement
  19. Existence of a prime divisor statement
  20. Primality test concept
  21. Prime factorization definition
  22. Characteristic of a ring definition
  23. Commutative ring definition
  24. Euler's totient function definition
  25. Miller–Rabin primality test concept
  26. Existence of prime factorization statement
  27. Freshman's dream statement
  28. Euler's theorem statement
  29. Fundamental theorem of arithmetic statement
  30. AKS primality test statement
  31. RSA cryptosystem example
  32. Integer factorization problem

Further reading

  1. Web https://en.wikipedia.org/wiki/Integer_factorization
About this page
TagYPE65X5HJ4
URIm2://YPE65X5HJ4
Kindproblem
WritingW0 stub
MSC11Y05, 11A51, 68Q25
StatusThis copy of the site has no build data. Run m2 status YPE65X5HJ4.
AboutPrime factorization
UsesComposite number, Prime factorization, Prime number, Existence of prime factorization, RSA cryptosystem, Fundamental theorem of arithmetic, AKS primality test
Same as
Changed2 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.