ProofAtlas

Computational number theory and classical factoring algorithms

Improve classical semiprime factorization

Collaboration beta

Given a large number N known to equal two primes p and q, find the factors with a classical algorithm whose full bit complexity is asymptotically better than the general number field sieve for every allowed factor ratio.

Time(N)=LN[α,c]withα<13, orα=13andc<(64/9)1/3.
Known results and sources
A large semiprime N splits toward hidden primes p and q while a GNFS benchmark curve stands as the unresolved performance barrier.
The objective is a uniform classical factorization algorithm that strictly improves the GNFS benchmark.

Research problem

Exact mathematical statement

For an odd semiprime in the hard balanced regime

N=pq,2<p<q,p,q=N1/2+o(1),N=pq,\qquad 2<p<q,\qquad p,q=N^{1/2+o(1)},

design an implementable uniform classical factoring algorithm with expected bit complexity either

LN[α,c]for someα<13,L_N[\alpha,c]\quad\text{for some }\alpha<\tfrac13,

or

LN[13,c]for somec<(64/9)1/3.L_N[\tfrac13,c]\quad\text{for some }c<(64/9)^{1/3}.

The algorithm must cover general semiprimes, charge every bit operation and modulus lift, and handle every failure branch. The source reports that no such algorithm has been obtained.

Problem infographic

Problem at a glance

A landscape explainer shows N equals pq, the balanced regime, the GNFS target curve, the exact Wendt-frontier condition p at most 2k less than min of 2p and q for the displayed separator, and three open implementation gates.
Under the displayed Wendt-frontier hypothesis the exact separator narrows the search, but a full uniform bit-complexity improvement over GNFS is still missing.

Current mathematical picture

Where work on Improve classical semiprime factorization stands

Open problem

Selected route highlights from the mathematical source. This is not yet a complete mathematical inventory.

Useful failureStandard dense rectangular interval products

In the source's stated model, optimizing the block size leaves N^(1/4+o(1)) ring operations. A modulus-specific nonregular evaluator or arithmetic cancellation mechanism outside that dense model remains open.

Route status · Narrowed route
Main reductionCurrent reduction

The source reduces candidate improvements to a small set of non-ring-generic primitives rather than claiming that existing identities themselves beat GNFS.

Evidence posture · Source-reported route statement · dependencies incomplete
Priority open bridgeConstruct a one-output shifted-Stirling coefficient evaluator with sublinear state and a complete end-to-end bit-complexity bound.Task status · Ready to work on
Research-record correctionResearch-record correction

We corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Reader-facing record corrected; mathematics unchanged

Work mapped so far

Improve classical semiprime factorization in numbers

2.7kretained lines of mathematical investigation2,659 in the current working snapshot
Argument development
2,245 · 84%
Explored or eliminated routes
51 · 2%
Computational analysis
113 · 4%
Open obligations
122 · 5%
Definitions and setup
128 · 5%
7selected mapped statements2routes investigated5open questions5contribution-ready tasks
How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Status checkedAug 14, 2026
Source recordedAug 14, 2026

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

14 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

14 selected steps

Scroll horizontally to explore the route

Working route overview for Improve classical semiprime factorizationA selected map of recorded claims, active routes, useful failures, open questions, and their explicit relationships. Search, filter, zoom, or pan within this page.Can a fully analyzed classical algorithm beat GNFS on general semiprimes? — Depends on missing premiseCan a fully analyzedclassical algorithm beatGNFS…Conditional shifted-gap factorer — Depends on missing premiseConditional shifted-gapfactorerCurrent reduction — Depends on missing premiseCurrent reductionClosing target — Depends on missing premiseClosing targetDense rectangular floor — Depends on missing premiseDense rectangular floorMasked CRT separator — Depends on missing premiseMasked CRT separatorNo complete algorithm obtained — Depends on missing premiseNo complete algorithmobtainedStandard dense rectangular interval products — stoppedStandard dense rectangularinterval productsSymbolic denominator cancellation — stoppedSymbolic denominatorcancellationConstruct a one-output shifted-Stirling coefficient evaluator with sublinear state and a complete end-to-end bit-complexity bound. — OpenConstruct a one-outputshifted-Stirling coefficientevaluator…Compute arithmetic interval quotients normalized by powers of N without identifying the hidden p and q blocks or lifting one power too far. — OpenCompute arithmetic intervalquotients normalized bypowers…Evaluate the masked Chebyshev or Wendt probes without explicitly constructing the factor-revealing zero divisor or a unit multiple of it. — OpenEvaluate the maskedChebyshev or Wendt probeswithout…Strict GNFS improvement target — OpenStrict GNFS improvementtargetFour live primitives — OpenFour live primitives
Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Explored alternatives

Other routes

2 recorded
Narrowed routeStandard dense rectangular interval products

In the source's stated model, optimizing the block size leaves N^(1/4+o(1)) ring operations. A modulus-specific nonregular evaluator or arithmetic cancellation mechanism outside that dense model remains open.

Route status · Narrowed route
Narrowed routeSymbolic denominator cancellation

The normalized value reduces to public Taylor or Hasse data when the remaining factor is regular modulo N. Arithmetic simultaneous cancellation tied to different hidden p and q positions remains a distinct live primitive.

Route status · Narrowed route

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

5 featured tasks
01
Construct a one-output shifted-Stirling coefficient evaluator with sublinear state and a complete end-to-end bit-complexity bound.Suggested move: Analyze addition and doubling laws, transposed multiplication, diagonal extraction, and creative telescoping while measuring state and coefficient heights.
Ready to work on
02
Compute arithmetic interval quotients normalized by powers of N without identifying the hidden p and q blocks or lifting one power too far.Suggested move: Derive and audit quotient-preserving block composition across product trees, remainder trees, quotient rings, and modulus-specific nonfunctorial gates.
Ready to work on
03
Strict GNFS improvement target

The requested algorithm must achieve alpha below one third or improve the GNFS leading constant at alpha equal to one third.

Suggested move: Resolve the exact source-reported obligation without treating it as an established negative result.
Ready to work on
04
Four live primitives

Masked evaluation, arithmetic simultaneous cancellation, shifted-Stirling fast-forward, and a model-breaking NFS mechanism remain open research primitives.

Suggested move: Resolve the exact source-reported obligation without treating it as an established negative result.
Ready to work on
05
Evaluate the masked Chebyshev or Wendt probes without explicitly constructing the factor-revealing zero divisor or a unit multiple of it.Suggested move: Express the probes in original signed-binomial data, identify the minimum denominator profile, and isolate the exact nonregular operation required.
Ready to work on

Sourced mathematical context

The known mathematical landscape

Context collected Aug 14, 2026
Current statusOpen problem

The general number field sieve remains the externally identified best-known classical general-purpose factoring algorithm. No complete, uniformly analyzed classical algorithm beating its asymptotic benchmark was located in the bounded official search.

[2][1]
External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

  1. Peer reviewedThe number field sieve literature established the general-purpose framework that supplies the benchmark for this research objective.[1]
2 cited sources1 related results or reductionsReferences

Mathematical neighborhood

Related results and reusable starting points

Current focusImprove classical semiprime factorization
Dependency or reductionGeneral number field sieve

A claimed improvement must be compared against the general number field sieve with a complete uniform bit-complexity analysis.

[1][2]

Formalization opportunities

Lean work can make these reusable foundations precise without being presented as a proof of the core problem.

  • Formalization targetA complete implementable algorithm covering all promised semiprimes.
  • Formalization targetA full bit-complexity proof that strictly improves the GNFS asymptotic benchmark.

Research-record corrections

What changed in the research record

These notes describe corrections to cited passages, highlighted tasks, or connections between claims. The mathematical claims and their status did not change.

Research-record correctionWe corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details
Research-record correctionWe corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details
Research-record correctionWe corrected the cited passages. We removed a duplicate or outdated task or route step. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

The initial argument structure appears separately. Uploads, model runs, and presentation changes do not count as mathematical updates.

Detailed research inventory

Claims, milestones, and routes in the current map

This view highlights the mathematical statements most useful for following the current route.

5 standing statements2 proposed statements5 open questions2 narrowed routes
Statements by mathematical role7 selected mapped statements
  • theorem candidate1 of 71
  • reduction2 of 72
  • lemma2 of 72
  • negative result2 of 72
Selected mathematical clusters1 mathematical clusters
Current research mapThe conjecture, retained reductions, explored limitations, and open questions represented in this overview.23 displayed rows · 2 routes included
  • retained route statementCan a fully analyzed classical algorithm beat GNFS on general semiprimes?
  • retained route statementCurrent reductionintermediate
  • retained route statementClosing targetintermediate
  • retained route statementNo complete algorithm obtainedintermediate
  • retained route statementMasked CRT separatorintermediate
  • retained route statementConditional shifted-gap factorerintermediate
  • retained route statementDense rectangular floorintermediate
  • Recorded relationshipThe source reports this as a route toward the conjecture; missing or unaudited premises remain and the reduction does not itself prove the target.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • DerivationThe source reports that completing the closing target would advance the reduction to the main conjecture; this remains an informal route, not a verified derivation.proposed
  • Useful failureStandard dense rectangular interval productsreported failure
  • Useful failureSymbolic denominator cancellationreported failure
  • Research targetConstruct a one-output shifted-Stirling coefficient evaluator with sublinear state and a complete end-to-end bit-complexity bound.open
  • Research targetCompute arithmetic interval quotients normalized by powers of N without identifying the hidden p and q blocks or lifting one power too far.open
  • Research targetEvaluate the masked Chebyshev or Wendt probes without explicitly constructing the factor-revealing zero divisor or a unit multiple of it.open
  • Research targetStrict GNFS improvement targetopen
  • Research targetFour live primitivesopen
  • ComputationThe current work reports finite exact regression suites for algebraic identities and adversarial boundary examples, but those scripts were not executed during intake.Finite verification is source-reported evidence only and does not establish asymptotic complexity or a sub-GNFS algorithm. · reported unreproduced
  • Narrowed routeStandard dense rectangular interval productsIn the source's stated model, optimizing the block size leaves N^(1/4+o(1)) ring operations. A modulus-specific nonregular evaluator or arithmetic cancellation mechanism outside that dense model remains open.
  • Narrowed routeSymbolic denominator cancellationThe normalized value reduces to public Taylor or Hasse data when the remaining factor is regular modulo N. Arithmetic simultaneous cancellation tied to different hidden p and q positions remains a distinct live primitive.
How to interpret these counts

A statement may be a lemma, conditional reduction, special case, documented limitation, or open target. These counts describe the work's structure; they do not estimate distance to a proof.

Research outlook

Conditions that would advance the current route

Priority open bridgeConstruct a one-output shifted-Stirling coefficient evaluator with sublinear state and a complete end-to-end bit-complexity bound.

2 approaches have already been tested and narrowed. The task above is the current priority within the larger open route.

Evidence needed nextConcrete conditions for progress

A result can change the outlook by closing the bridge, narrowing its scope, or showing that the route cannot work.

  • Supply a complete argument with every imported premise identified.
  • Survive an independent attempt to falsify the proposed step.

Continue the mathematics

Contribute

ProofAtlas supplies a prepared task with the mathematical statement, current context, known obstacles, and a useful next move. Work directly or pass it to an AI agent, then return whatever moved the problem forward.

Read-only beta · actions unavailable
Prepared starting pointConstruct a one-output shifted-Stirling coefficient evaluator with sublinear state and a complete end-to-end bit-complexity bound.

Improve classical semiprime factorization · ready to start

Mathematical updatesFollow this problem

Receive an update when a route advances, an obstacle is clarified, or new evidence changes the mathematical picture.

Research contextPrepared context for any AI agent

Given a large number N known to equal two primes p and q, find the factors with a classical algorithm whose full bit complexity is asymptotically better than the general number field sieve for every allowed factor ratio.

  • Exact question and boundaries
  • Current routes and known obstacles
  • What a useful result should report
Return mathematical workReturn what you or your agent found

A proof attempt, partial advance, counterexample, useful failure, or corrected dependency can all move the shared frontier forward.

Proof attempt or partial resultSupporting notes or data
Hosted agentRun this task with a hosted agent

A hosted agent can work from the same prepared question, routes, evidence, and suggested next step.

Your own AI agentConnect an outside research agent

Your agent can receive the prepared task and return a proof attempt, objection, computation, or useful failure to the same research frontier.

Sources and references2 cited works · next context review by Nov 14, 2026

The mathematical context was checked on Aug 14, 2026. Status can be refreshed sooner after a material result or claim.

  1. 1
    The Development of the Number Field Sievesurvey or monograph · Arjen K. Lenstra, Hendrik W. Lenstra · Springer Berlin, Heidelberg · 1993 · DOI 10.1007/BFb0091534 · accessed Aug 14, 2026
  2. 2
    Cryptographic Standards in a Post-Quantum Eraauthoritative webpage · Dustin Moody, Angela Robinson · National Institute of Standards and Technology · 2022-07-11 · accessed Aug 14, 2026

Important qualifications

  • Bounded official and publisher search; not an exhaustive algorithm survey.
  • This research target is not treated as a historical named conjecture and no universal lower bound is asserted.

Continue exploring

Compare another research frontier

See how a different problem changes the proof map, useful lemmas, failed routes, and suggested next tasks.

Explore all research workspaces

Expanded visual

Open original image