Algorithms · Mathematical research

Factoring, with a proven bound.

Worst-case guarantees for factoring arbitrary integers, with a formal proof rather than just finite benchmarks.

Illustrated beads representing integer factorization
Deterministic factoring

The result

The algorithm takes an integer N in binary and outputs its smallest prime factor. For a bit length of n, the repository establishes a deterministic finite-alphabet Turing-machine running-time bound:

This is an asymptotic bound, not a measured speedup over practical factoring programs.

Lean verification

The Lean endpoint is IntegerFactoring.HalfAppendix.sqrtLogLog_factoring. Big O Speedrun independently rebuilt the formalization and accepted the saving exponent 1/2. The verification record and proof map document its scope.

Open work

A stronger uniform worst-case exponent is not established. Experimental successes on particular semiprimes and conditional reductions do not by themselves improve this theorem. The research checkpoint separates complete results from open steps.

The interactive trial-division calculator on the homepage illustrates factorization. It does not implement this research algorithm.

Read the evidence