Almost Factoring RSA-260

Published September 9, 2026｜10 minute read

No AI was used in writing this post, or in writing any computational code involved in this project. All typography and mistakes are my own.

I recently heard about Eric Lu’s announcement that RSA-260 had been factored. Congratulations to Eric!

This is a bit of a non-post, minimally edited stream-of-conciousness. If that bothers you, no need to read it. I just wanted to write the following down somewhere.

This exact factorization is a project I had been working on, on-and-off, since mid-2023. Since November 2025, I had begun putting in serious effort. I don’t have institutional resources, so all work was self-funded, chugging away slowly. I was about one month away from finishing relation collection when I got wind of Eric’s work.

Why?

My goal was not to factor RSA-260 per se, but rather to gain a deep, hands-on understanding of the GNFS and every stage involved. In this sense, I’m not too disappointed, and did achieve my goal.

Some ground rules I set for myself, although this probably did slow me down:

• all computational code was handwritten^[1] (not that anything else was really possible in 2023), and
• I chose not to reference CADO-NFS or any other existing implementation, instead relying entirely on papers and first-principles.

My primary references were Emmanuel Thomé’s CSE291-14 lecture notes, Shi Bai’s thesis (particularly the exposition on Kleinjung II), and the original “Continued Fractions and Lattice Sieving” paper. I probably read a hundred or so various other papers as well.

How?

Over the past three years, I hand-wrote GPU-accelerated libraries for:

• Polynomial selection (at least 12 different times, with different algorithms),
• Polynomial optimization (at least 9 times),
• Line sieving (at least 11 times),
• Lattice sieving (at least 7 times),
• Big-integer arithmetic, including Newton-Raphson division and efficient modtree/remtree,
• Probably hundreds of various analysis scripts, plots, optimizers, etc.

Something I’m particularly happy with is an essentially optimal polynomial for line sieving (in the sense of coefficient norm/entropy), which required inventing a new algorithm to find:

1Y0: -96988802986078563409219509925977920729607921301935809972414350357
2Y1: 5089804878305910556882449747327730192583535
3c0: -773323273436825329405544403072390155467430782807207945206175353862512727655432976
4c1: 14092579858096468560603867976987395525858057537697400073654178
5c2: -153014691167106845715980915170004262238552
6c3: -1
7c4: 1

This is fairly useless once you have a lattice sieve. I was a bit lazy and wanted to avoid writing a lattice sieve if possible. The above polynomial is about the best you can theoretically do in 1D, but still not enough.

So, begrudgingly I wrote a lattice sieve and optimized for the standard degree 6/1 polynomials at this size. I probably went back-and-forth at least a dozen times between “finally finishing (at last!)” the polyselect stage, moving on to sieving, finding it not good enough, and going back. At the end of about a year, I found the following polynomial (whose MurphyE is only about 11% worse than Eric’s):

1Y0: -1595279796030492405163111210365411638589669
2Y1: 1692407251940247959407513
3c0: 6395485413706701965248800466129525241109176831996094720
4c1: 1099940081400193875359181142757117855994895271678
5c2: 41066341547916990474530329814068563094169
6c3: -675428664846098676148643289428648
7c4: -11170198458649567228814339
8c5: -11760567
9c6: 52322400
10skew: 69602000

The polynomial search and size optimization methods are completely different from CADO-NFS. (Possibly the root optimization as well; I still haven’t read the CADO source.) In particular, I completely ignored translations during size-opt/root-opt, and only applied them at the end. Morally speaking, translations just reshuffle sites around, and should not be relevant for the size-opt stage (my opinion).^[2]

Lattice sieving was your bog-standard two-level bucket sieve with Franke-Kleinjung enumeration, except written on the GPU. I played fast and loose with correctness in the name of total throughput (which is fine if you have excess relations in your sieve region, in principle).^[3]I chose semiprime special-q with one small and one large factor, as it performed the best. The final configuration sieved both algebraic and rational sides, maximizing the analytic Bayesian probability of joint smoothness (see my previous post), and filtering by threshold. This is, in the Bayesian sense, the optimal greedy strategy for maximizing relations per second.

Since all this work was self-funded, I had an incentive to squeeze every last dollar out of the GPUs I bought/rented. I put in decent effort to ensure that my code uses every last clock cycle well. All-in-all, the entire project probably cost me around 20k USD, and would have finished well under 30k.^[4]This is signficantly below the 400k USD estimated by Eric, probably because I used hand-me-down eBay GPUs, and maybe a bit due to improved algorithms.

What’s Next?

I would have liked to continue implementing the Krylov, block Wiedemann, square root stages (about half done). But the fact that the factorization is done, to be honest, significantly reduces my motivation to do so. I may come back to this some day.

For now, I’ve moved on to finding high-rank elliptic curves. I had previously tied the $\mathbb{Z}/4\mathbb{Z}$-torsion record at rank 13, without any AI assistance.^[5] At the time of writing, I also hold the records for the smallest-conductor elliptic curves for all ranks 20 through 28, the smallest-discriminant curve of rank 29, and one genuinely new curve of rank 30.^[6]

Again, the goal is not so much to break records (although fun), but to learn more about elliptic curves and their fascinating properties.

Such is life!

— Sam

---

Footnotes

1. [1]Much later on (mid-2026), I did make an exception for monitoring tools/web dashboards. I don’t want to waste my time debugging packet loss and Nagle’s algorithm.↩
2. [2]Translation is only “required” since the covered lattice-sieving site density is roughly elliptical, although you can always just skew the LLL cost function.↩
3. [3]I even got to throw in some cool intrinsics!↩
4. [4]If you count the appreciation of my computing hardware, the net cost was negative — can’t complain! The raw cost would probably have been $\sim 10^4$ USD if it weren’t for PG&E’s insane electric delivery charges.↩
5. [5]At the time of writing, this record still stands (Li 2026). It was mostly achieved by hand-writing insanely efficient GPU kernels, with arguably no new interesting mathematics.↩
6. [6]I found two “new” curves of rank 30, of which one had been hinted at (but not yet published) by Noam Elkies. That makes a total of four known to the world.↩