Rational Base Descent: A Deterministic Algorithm for Factoring Structured Semiprimes
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.08846
curl -X POST /api/v1/records/arxiv/2605.08846/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.08846/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'