Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.08846 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915997497163776 |
|---|---|
| author | Blake, Sam |
| author_facet | Blake, Sam |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_08846 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Rational Base Descent: A Deterministic Algorithm for Factoring Structured Semiprimes Blake, Sam Number Theory 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. |
| title | Rational Base Descent: A Deterministic Algorithm for Factoring Structured Semiprimes |
| topic | Number Theory |
| url | https://arxiv.org/abs/2605.08846 |