Integer factorization
ID: integer-factorization
Integer factorization is the process of decomposing an integer into a product of smaller integers, specifically into prime numbers. For example, the integer 28 can be factored into prime numbers as \(2^2 \times 7\), where 2 and 7 are prime numbers. The goal of factorization is to find these prime factors. The significance of integer factorization lies in its applications, particularly in number theory and cryptography.
Complexity: NP-intermediate as of 2020:
- expected not to be NP-complete because it would imply NP != Co-NP: cstheory.stackexchange.com/questions/167/what-are-the-consequences-of-factoring-being-np-complete#comment104849_169
- expected not to be in P because "could we be that dumb that we haven't found a solution after having tried for that long?
New to topics? Read the docs here!