nk_kolja

The runtime follows from a reduction to Boolean tensor contraction problem - recently claimed to be subexponential, and for now very impractical.

Do people not use AI this way in prod?

I was unaware of snfs algorithms for generic moduli and/or signatures. Very nice. The theoretical result is purely due to the 2007 Joux et al. paper. What’s new is the implementation and the 1024-bit rsa signature forgery.

Also no ai, so we can expect some speedups soon.

I really didn’t expect rsa to be targeted so much this year. Hope that these results will motivate people to pursue algorithmic improvements!

Reminds me of the windows fold phone. ‘‘Twas the best of phones, but out of my price range at the time. Now I have nostalgia of windows phone, the best phone os that never was.

Even though I like the form factor I doubt I’d cash out 2k for it, seems like a waste just to spend more time on another screen.

Of course years. Typo.

So RSA 260 is about 2-3 times harder than RSA 250, which was solved in 2700 core hours in 2020, so it’s probably no algorithmic improvements, just a tweak here and there plus faster hardware.

Impressive. I wonder the methodology. Algorithmic improvements? More probably just an implementational optimisation. Last RSA record was due to special q sieving methods if I recall well, some 3k core hours. I hope there’s a theoretical improvement behind the result.

Reducing the problem to a quadratic form is pretty natural, and the paper from 2009 (though i see 2015) is quite an overkill. The result is a fairly standard consequence of the theory of representation by quadratic forms, and follows from Legendre's three square's theorem after some massaging. There's a good couple of centuries of foundations behind it.

Impressive. Wonder if we'll get something earth-shattering, like factoring, or maybe it is already solved just not public yet.

What a nice comment. Indeed, it feels like it was just waiting for you to find it.

That is a rather nice ritual, I think I will use it now to motivate myself to learn Scala.

Nice! And what a beautiful website!

Below the surface it's all the division with constant trick.