Semiprime factorization is Turing-computable (trial-division baseline)
OpenPolyTimeFactorization.trial_division_computablecomputabilityfactorizationnumber-theory
There is a total function , computable by a Turing machine with no time bound, that factors every semiprime: for all primes and (possibly equal), .
This is the computability baseline of the mission — the goal with the polynomial-time requirement removed. Trial division supplies such an , for instance , at exponential cost.
Formalization Note. Computability is Mathlib's Turing.TM2Computable with the binary input encoding encodeNat and the product output encoding encodingProd encodingNatBool encodingNatBool. Because TM2Computable is a bundled structure rather than a proposition, the existence of a machine is expressed with Nonempty.
Preamble
import Mathlib open Computability Turing
Formal statement
namespace PolyTimeFactorization
theorem trial_division_computable :
∃ f : ℕ → ℕ × ℕ,
Nonempty (TM2Computable encodeNat (encodingProd encodingNatBool encodingNatBool).encode f) ∧
∀ p q : ℕ, p.Prime → q.Prime → f (p * q) = (min p q, max p q) := by sorry
end PolyTimeFactorizationSource
Folklore (trial division); see https://en.wikipedia.org/wiki/Trial_division and R. Crandall & C. Pomerance, Prime Numbers: A Computational Perspective, 2nd ed., Springer (2005), https://doi.org/10.1007/0-387-28979-8
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.