The smoothness barrier `L[1/3,1]` is subexponential.
ProvedFactoringBarriers.smoothness_barrier_subexpaether-catalogcryptography
The smoothness barrier L[1/3,1] is subexponential.
theorem FactoringBarriers.smoothness_barrier_subexp: Subexp (barrierCost .smoothness) := by sorry
Formalization Note Transplanted verbatim from the Aether Catalog source Cryptography/FactoringBarriers/ResourceClassification.lean; the statement is byte-identical to the source declaration, elaborated with autoImplicit disabled in the platform environment.
Preamble
-- Thm stub generated from Cryptography/FactoringBarriers/ResourceClassification.lean
import Mathlib
import Definitions.Def_Cryptography_FactoringBarriers_AsymptoticLadder
import Definitions.Def_Cryptography_FactoringBarriers_ResourceClassification
/-!
# Classification of Classical Factoring Resources and Their Barriers
Every *known* classical resource for attacking integer factorization comes with
a documented running-time barrier:
| resource | representative algorithm | barrier (in `x = log N`) |
|---------------|--------------------------|----------------------------------|
| randomness | Pollard rho | `exp (x/4)` (i.e. `Θ(N^{1/4})`) |
| smoothness | CFRAC / QS / GNFS | `L[1/3, c]` |
| iteration | Williams `p+1` / ECM | `L[1/2, √2]` in `log p ≈ x/2` |
| analog/chaos | analog dynamics | no structural gain: `L[1/3, c]` |
This file formalises the classification as a finite type `ClassicalResource`
with an assigned `barrierCost`, and proves the two facts that make the
conditional-impossibility schema work:
* `barrierCost_superpoly` — **every** classified barrier is superpolynomial;
* `barrier_hierarchy` — the classification is non-degenerate: the randomness
barrier is genuinely exponential while the smoothness/analog barriers are
strictly subexponential, so the four entries are not a repackaging of one bound.
Note the honest scope: these are *definitions recording the known state of the
art*, together with real theorems about the growth of the recorded bounds.
Nothing here asserts that the table is exhaustive of all conceivable resources;
that is exactly the gap the capstone keeps explicit.
-/
open FactoringBarriers
open Filter Real
open scoped Topology
/-! ## Stability of superpolynomiality under linear rescaling of the input -/
/-! ## The four classified resources -/
/-! ## Every classified barrier is superpolynomial -/
/-! ## The classification is non-degenerate -/Formal statement
theorem FactoringBarriers.smoothness_barrier_subexp: Subexp (barrierCost .smoothness) := by sorry
Source