Successor to the RSA Factoring Challenge (1991-2007)
Before filing
Test your factoring claim first
Four kind questions, then the decisive gate for the class of claim actually being made. Attach the evidence; do not ask the register to infer it.
Four questions
1
Question 1
Can you exhibit the factors?
Give exact integers N,p,q. Check that 1<p,q<N and that exact multiplication gives pq=N. If you call them prime factors, attach checkable primality evidence.
A correct multiplication settles only this one factorization.
One-multiplication self-adjudication applies to instance claims only and never promotes a generality verdict.
2
Question 2
Does the complete method beat GNFS’s L[1/3] benchmark?
Count all the work, not just the fastest subroutine. Include preprocessing, relation search, failed runs, memory, storage, linear algebra, and postprocessing. Compare like with like on ordinary inputs and matched resources.
If you claim polynomial time, attach the proof. Timings on a few small examples cannot prove an asymptotic bound.
3
Question 3
Does it work on a fresh challenge number with no special structure?
Freeze the code, settings, and budget first. Then let an independent registrar reveal a fresh balanced semiprime. Do not choose a number with a tiny factor, nearly equal factors, known answer, or another helpful special form. Report failures and retries too.
One hand-picked success does not show a general method.
4
Question 4
For a quantum claim: is this a demonstration or an estimate, and is the answer compiled in?
Say plainly whether the evidence is an estimate, simulation, component test, logical experiment, or end-to-end physical-hardware factorization. Give the full logical, physical, error-correction, runtime, and classical costs.
The compiler and circuit generator must not know the factors, order, or any answer-derived hint. If the answer is baked into the circuit, the run is not evidence that the machine discovered it.
The four class gates
C1
C1
“I factored this specific N”
Minimum admissible submission
Exact integers N,p,q.
The asserted input class.
A statement of whether the claim is only “non-trivial factors” or specifically “prime factors.”
Decisive gate
Parse canonical integers.
Require 1<p<N and 1<q<N.
Compute one exact arbitrary-precision multiplication and require p× q=N.
If “prime factors” is asserted, also require independently checkable primality evidence for p and q.
What a failure kills
A product mismatch conclusively refutes the submitted factor identity.
If p or q is composite, that refutes the word “prime”; it need not refute the existence of a non-trivial decomposition.
What a success does not prove
It does not prove a general algorithm, novelty, priority, competitive speed, or any asymptotic result.
One-multiplication self-adjudication applies to instance claims only and never promotes a generality verdict. Exact multiplication proves nothing about novelty, speed, generality, or scaling.
“I have a polynomial-time classical factoring algorithm”
Minimum admissible submission
All C2 materials.
A mathematical specification of the algorithm.
A bit-complexity proof and success-probability analysis.
Complete accounting for every subroutine, oracle, precomputation, advice string, precision requirement, memory cost, and verification step.
Decisive gate
Specialist proof review and scaling experiments on post-freeze fresh challenges.
The analysis must compare the complete method with the general classical GNFS benchmark below; a hidden super-polynomial stage or target-dependent advice is not polynomial time.
What a failure kills
A correctness counterexample, an answer-dependent step, or a super-polynomial hidden subroutine refutes the theorem as written.
Missing fresh-target performance leaves the practical claim unsubstantiated.
Failure of one finite practical target can refute a frozen performance promise, but does not by itself disprove eventual polynomial asymptotics unless that promise is part of the theorem.
What a success does not prove
Passing any finite challenge suite cannot establish an asymptotic theorem.
An attractive fitted curve over small inputs is not a substitute for a reviewed proof.
One-multiplication self-adjudication applies to instance claims only and never promotes a generality verdict.
Declare the actuality level: analytic resource estimate, classical simulation, logical/component experiment, or physical-hardware execution.
Give logical and physical qubit counts, error model, connectivity, code and code distance, gate/cycle counts, runtime, decoding, feed-forward, retries, success probability, and all classical costs.
Disclose circuit generation, compilation, target-specific preprocessing, and whether any stage received p, q, the order, or an answer-derived hint.
Decisive gate
Match the gate to the claimed actuality:
audit assumptions for an estimate;
independently reproduce a simulation;
audit a logical/component experiment at that limited level; or
for a hardware factorization, require answer-independent device output that yields factors passing C1.
What a failure kills
Calling an estimate a demonstration, omitting material fault-tolerance overhead, or compiling with knowledge of the answer voids the claimed evidence level.
An answer-dependent compiled circuit is not factoring evidence even if its final bits encode the right factors.
What a success does not prove
A small compiled, simulated, annealing, or hybrid experiment does not demonstrate cryptographic-scale Shor factoring.
A valid resource estimate remains an estimate, not a factorization record.
One-multiplication self-adjudication applies to instance claims only and never promotes a generality verdict.
Freeze the claim first. Record the source/container hash, dependencies, code, parameters, libraries, hardware, timeout, memory, success probability, allowed preprocessing, retry policy, and supported input distribution.
Fix the target class. State size in bits. The default target is N=pq, with independently generated primes of comparable bit length and no advertised algebraic special form.
Only then generate and reveal the challenge. Use registrar-controlled randomness. Commit to the generation record and keep the factors sealed from the claimant and operator, or discard them after generation.
Run the frozen submission. Give it only N and the predeclared budget. Record every retry, timeout, failure, and parameter-change request.
Require a falsifiable output. Accept only an exhibited non-trivial factor. Re-multiply locally. Do not accept screenshots, decimal approximations, hashes of alleged factors, or “nearly converged” output.
Test generality as a distribution. Repeat across multiple fresh targets and increasing sizes before assigning a general-performance grade. Publish failures as well as successes.
This protocol makes “fast” gradeable only after “fast,” the distribution, the success probability, and the resource budget are fixed. Failure kills the frozen bounded claim, not every imaginable revision of the method. [Provenance: scout-c:S02, scout-c:S14, rsa-challenge-faq.html, zimmermann-rsa-records.html]
General classical benchmark
For integers without exploitable special structure, compare the complete workflow with the General Number Field Sieve heuristic expected-time benchmark:
Count polynomial selection, relation collection, filtering, linear algebra, square root, preprocessing, retries, precision, memory, storage, communication, and verification. This is a heuristic benchmark for a known algorithm, not a proved lower bound on every classical factoring algorithm.