pith. machine review for the scientific record. sign in

arxiv: 2605.08846 · v1 · submitted 2026-05-09 · 🧮 math.NT

Recognition: no theorem link

Rational Base Descent: A Deterministic Algorithm for Factoring Structured Semiprimes

Sam Blake

Pith reviewed 2026-05-12 00:51 UTC · model grok-4.3

classification 🧮 math.NT
keywords factoringsemiprimesrational base descentspecial-purpose algorithmsRSA securitynumber theorydeterministic methodsprimitivity filters
0
0 comments X

The pith

A deterministic algorithm factors semiprimes where one prime approximates c times a rational base to an integer power in cubic logarithmic time.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces Rational Base Descent, a special-purpose deterministic algorithm for factoring semiprimes N = p q in which one prime satisfies p approximately equal to c times (a over b) to the power n, for positive integers a, b, c, n with a greater than b and gcd of a and b equal to 1. Given the correct pair (a, b), the method isolates a factor in time cubic in the logarithm of N whenever the ratio a over b stays bounded away from 1, while the second prime q faces only a mild size restriction. The work also supplies a search procedure over candidate pairs (a, b) that applies primitivity filters and includes a complexity analysis confirming the method leaves ordinary balanced RSA semiprimes unaffected. A working Python implementation based on gmpy2 is provided for practical use.

Core claim

The central claim is that when one prime factor of a semiprime obeys the rational-power form p approximately c (a/b)^n, the rational base descent procedure recovers that factor deterministically in O(log cubed N) steps once the integers a and b are supplied, with the second factor subject only to a mild size bound and with a/b bounded away from 1.

What carries the argument

Rational base descent, the iterative procedure that exploits the geometric relation induced by the rational exponent (a/b)^n to isolate one prime factor from the product N.

Load-bearing premise

One prime factor must be sufficiently close to c times (a/b) raised to an integer power for some integers a, b, c, n, and the search over candidate pairs must locate the correct a and b.

What would settle it

Construct a semiprime N = p q by choosing integers a, b, c, n with a greater than b, set p to the integer nearest c times (a/b) to the n, choose q of suitable size, then run the algorithm with the known (a, b) and observe whether it recovers p within O(log cubed N) steps.

read the original abstract

We present a special-purpose algorithm for factoring semiprimes $N = pq$ in which one prime factor satisfies $p \approx c\,(a/b)^n$ for positive integers $a, b, c, n$ with $a > b$ and $\gcd(a,b) = 1$. Given the correct parameters $(a, b)$, the algorithm isolates a factor in ${O}(\log^3 N)$ time when $a/b$ is bounded away from $1$, and the cofactor $q$ is unconstrained beyond a mild size bound. We describe a search strategy over $(a, b)$ using primitivity filters, give a complexity analysis showing that the method poses no threat to balanced RSA semiprimes, and provide a gmpy2-based Python implementation.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript presents Rational Base Descent, a deterministic special-purpose algorithm for factoring semiprimes N = p q in which one prime satisfies p ≈ c (a/b)^n for positive integers a > b, gcd(a,b)=1, c, n. Given the correct base pair (a,b) with a/b bounded away from 1, the procedure isolates a factor in O(log^3 N) time while the cofactor q is subject only to a mild size bound. The paper supplies an explicit search strategy over candidate (a,b) pairs that employs primitivity filters, a complexity argument establishing that the overall method remains exponential (and thus harmless) for balanced unstructured RSA moduli, and a gmpy2-based Python implementation.

Significance. If the stated runtime and search strategy hold, the work supplies a new, fully deterministic tool for a well-defined class of structured semiprimes. This is useful for cryptanalysis of weak or specially constructed keys and for number-theoretic experiments. The separation of the O(log^3 N) core procedure from the (necessarily slower) search, together with the explicit complexity analysis showing no threat to generic RSA, is a clear strength; the availability of reproducible code further supports verification.

major comments (2)
  1. [§3 and §4] §3 (algorithm description) and §4 (complexity): the O(log^3 N) bound is asserted for the core descent once (a,b) are supplied, yet the step-by-step operation count—number of modular exponentiations, gcds, or bit-length reductions—is not exhibited explicitly. Without this accounting it is impossible to confirm that the cubic dependence on log N is achieved rather than hidden by an unstated assumption on arithmetic cost.
  2. [§5] §5 (search strategy): the primitivity filters are described at a high level, but the precise criterion (e.g., an equation or predicate on the continued-fraction convergents or on the order of a modulo N) is not formalized. Consequently the claimed pruning of the (a,b) search space cannot be independently verified or bounded.
minor comments (2)
  1. [Abstract and §1] The abstract and introduction should cite the classical special-purpose factoring methods (Fermat, Pollard's rho, CFRAC) to situate the new technique.
  2. [Throughout] Notation for the rational base (a/b) and the exponent n should be introduced once and used consistently; occasional switches between “base” and “ratio” are distracting.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation and the insightful comments on the manuscript. We provide point-by-point responses to the major comments and will update the paper in a revised version to address the concerns raised.

read point-by-point responses

  1. Referee: [§3 and §4] §3 (algorithm description) and §4 (complexity): the O(log^3 N) bound is asserted for the core descent once (a,b) are supplied, yet the step-by-step operation count—number of modular exponentiations, gcds, or bit-length reductions—is not exhibited explicitly. Without this accounting it is impossible to confirm that the cubic dependence on log N is achieved rather than hidden by an unstated assumption on arithmetic cost.

    Authors: We agree with the referee that an explicit step-by-step operation count is necessary to rigorously establish the O(log^3 N) bound. The algorithm in §3 performs a fixed number of arithmetic operations per iteration of the descent, specifically involving modular exponentiations and gcds whose costs are polynomial in log N. In the revision, we will expand §4 to include a precise accounting: there are O(log N) descent steps, each requiring O(1) modular exponentiations of cost O((log N)^2) and O(1) gcds of cost O(log N), resulting in the cubic bound. This will be presented without relying on unstated assumptions. revision: yes

  2. Referee: [§5] §5 (search strategy): the primitivity filters are described at a high level, but the precise criterion (e.g., an equation or predicate on the continued-fraction convergents or on the order of a modulo N) is not formalized. Consequently the claimed pruning of the (a,b) search space cannot be independently verified or bounded.

    Authors: We acknowledge that the description of the primitivity filters in §5 is at a high level and would benefit from formalization. The filters rely on a predicate checking the consistency of the candidate base a with the multiplicative order modulo N, specifically by testing whether certain powers of a modulo N yield trivial gcds with N or satisfy a primitivity condition derived from the rational base approximation. In the revised manuscript, we will provide the exact mathematical definition of the filter as a predicate on (a, b, N), along with a brief complexity analysis of the pruning effect on the search space. This will enable independent verification and bounding. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper presents a deterministic algorithm whose O(log^3 N) runtime claim is derived from an explicit analysis of the procedure once the structural parameters (a, b) are supplied, together with a separate search strategy over candidate bases and primitivity filters. No equations, fitted parameters, or self-citations are shown that reduce the claimed complexity or the isolation step to a tautology or to the input data by construction. The complexity argument for unstructured RSA moduli is likewise presented as an independent bound rather than a re-labeling of the target instances. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The method rests on the domain assumption that the target semiprime belongs to the structured class; no free parameters are fitted inside the algorithm itself, and no new entities are postulated.

axioms (1)
  • standard math Unique factorization in the integers
    Implicit background fact used whenever a factor is isolated.

pith-pipeline@v0.9.0 · 5427 in / 1247 out tokens · 43108 ms · 2026-05-12T00:51:39.648191+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

  1. [1]

    A method for obtaining digital sig- natures and public-key cryptosystems

    Rivest, R. L., Shamir, A., Adleman, L. (1978). “A method for obtaining digital sig- natures and public-key cryptosystems”.Communications of the ACM. vol. 21. no. 2. pp. 120–126

    work page 1978

  2. [2]

    Factoring

    Cohn, H. “Factoring”.https://cohn.mit.edu/factoring

    work page

  3. [3]

    Lehmer, D. N. (1909).Factor Table for the First Ten Millions, Containing the Small- est Factor of Every Number Not Divisible by 2, 3, 5, or 7 Between the Limits 0 and 10,017,000.Carnegie Institution of Washington, Publication No. 105

    work page 1909

  4. [4]

    A method of factoring and the factorization of F7

    Morrison, M. A. & Brillhart, J. (1975). “A method of factoring and the factorization of F7”.Mathematics of Computation. vol. 29. no. 129. pp. 183–205

    work page 1975

  5. [5]

    Factoring integers with the number field sieve

    Buhler, J. P., Lenstra, H. W., Jr., & Pomerance, C. (1993). “Factoring integers with the number field sieve”. In: A. K. Lenstra & H. W. Lenstra, Jr. (eds.)The Development of the Number Field Sieve. Lecture Notes in Mathematics, vol. 1554. Springer-Verlag, Berlin. pp. 50–94. †Hint: once the public-key modulusnhas been factored asn=p q, compute Euler’s toti...

    work page 1993

  6. [6]

    Factoring large integers

    Lehman, R. (1974). “Factoring large integers”.Mathematics of Computation. vol. 28. no. 126. pp. 637–646

    work page 1974

  7. [7]

    Factorisation of Numbers

    Lawrence, F. (1895). “Factorisation of Numbers”.Messenger of Mathematics. vol. 24. pp. 100–109

    work page

  8. [8]

    A one line factoring algorithm

    Hart, W. (2012). “A one line factoring algorithm”.Journal of the Australian Mathe- matical Society. vol. 92. no. 1. pp. 61–69. [9]https://gmplib.org/

    work page 2012

  9. [9]

    Factorisation ofy n ∓1,y= 2,3,5,6,7,10,11,12 Up To Higher Powers

    Cunningham, A. J. C. & Woodall, H. J. (1925). “Factorisation ofy n ∓1,y= 2,3,5,6,7,10,11,12 Up To Higher Powers.” Francis Hodgson, London

    work page 1925

  10. [10]

    Factorizations ofb n ±1,b= 2,3,5,6,7,10,11,12 Up to High Powers

    Brillhart, J., Lehmer, D. H., Selfridge, J. L., Tuckerman, B., & Wagstaff Jr, S. S. (1988). “Factorizations ofb n ±1,b= 2,3,5,6,7,10,11,12 Up to High Powers.”

    work page 1988

  11. [11]

    The Cunningham project. High Primes and Misdemeanours: Lec- tures in Honour of the 60th Birthday of Hugh Cowie Williams

    Wagstaff, S. (2016). “The Cunningham project. High Primes and Misdemeanours: Lec- tures in Honour of the 60th Birthday of Hugh Cowie Williams”. pp. 367–378

    work page 2016

  12. [12]

    Recreations in the theory of numbers: The queen of mathematics entertains

    Beiler, A. H. (1964). “Recreations in the theory of numbers: The queen of mathematics entertains.” Courier Corporation

    work page 1964

  13. [13]

    The search for Aurifeuillian-like factorizations

    Wagstaff Jr, S. S. (2012). “The search for Aurifeuillian-like factorizations.”Integers, vol. 12. no. 6. pp. 1449–1462

    work page 2012

  14. [14]

    Factoring integers with elliptic curves

    Lenstra Jr, H. W. (1987). “Factoring integers with elliptic curves.”Annals of Mathe- matics. pp. 649–673. A GMP-Based Python Implementation of the Ratio- nal Base Descent Algorithm The arithmetic underlying the algorithm routinely involves integers of more than 1000 bits, so a fixed-precision implementation is unworkable. The Python 3 implementation below...

    work page 1987