Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Polynomial-time semiprime factorization (goal)

Open
PolyTimeFactorization.polytime_semiprime_factorization

by LG · Nov 16, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theoryfactorizationnumber-theoryopen-problem

There exists a total function f:N→N×Nf:\mathbb{N}\to\mathbb{N}\times\mathbb{N}f:N→N×N, computable in polynomial time by a classical Turing machine, that factors every semiprime: for all primes ppp and qqq (possibly equal),

f(pq)=(min⁡(p,q), max⁡(p,q)).f(pq)=(\min(p,q),\,\max(p,q)).f(pq)=(min(p,q),max(p,q)).

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 N\mathbb{N}N.

Whether such an fff 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 P≠NP\mathrm{P}\ne\mathrm{NP}P=NP. 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.

Preamble
import Mathlib
open Computability Turing
Formal statement
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 PolyTimeFactorization
Source
Epoch AI, FrontierMath: Open Problems - Improve the Best-known Classical Factorization Algorithms, https://epoch.ai/frontiermath/open-problems/prime-factorization (asymptotic formalization; see the mission description for the precise relationship). The polynomial-time factoring question is classical; cf. https://en.wikipedia.org/wiki/Integer_factorization
Human review
  • Endorsed by Shuze Chen · Nov 16, 2026

    Confirmed by the moderator at approval.

  • Endorsed by LG · Nov 16, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me