Polynomial-time semiprime factorization (goal)
OpenPolyTimeFactorization.polytime_semiprime_factorizationThere exists a total function , computable in polynomial time by a classical Turing machine, that factors every semiprime: for all primes and (possibly equal),
Polynomial time is measured in the bit-length of the input: one machine and one fixed polynomial bound must serve every input, under the standard binary encoding of .
Whether such an exists is a central open problem of computational number theory. No classical polynomial-time factoring algorithm is known, and no superpolynomial lower bound is known either. A proof of existence would break RSA; a proof of nonexistence would imply . This is the asymptotic, theorem-shaped core of Epoch AI's FrontierMath problem on improving the best-known classical factorization algorithms.
Formalization Note. Polynomial-time computability is Mathlib's Turing.TM2ComputableInPolyTime with input encoding encodeNat (binary) and output encoding encodingProd encodingNatBool encodingNatBool; because that notion is a bundled structure rather than a proposition, its existence is expressed with Nonempty. Fixing the binary encoding rules out machines whose time bound is polynomial in the value of the input rather than its bit-length.
import Mathlib open Computability Turing
namespace PolyTimeFactorization
theorem polytime_semiprime_factorization :
∃ f : ℕ → ℕ × ℕ,
Nonempty (TM2ComputableInPolyTime encodeNat (encodingProd encodingNatBool encodingNatBool).encode f) ∧
∀ p q : ℕ, p.Prime → q.Prime → f (p * q) = (min p q, max p q) := by sorry
end PolyTimeFactorizationConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.