A completely new class of method for computing discrete logarithmsThis paper seems to be about a specific case
http://web.archive.org/web/20250725043122/https://cr.yp.to/dlog/cuberoot-20120919.pdf but in reality, the method is generic. They talk about small discrete logarithms in the same vein that pollard rho has a complexity too high to handle large discrete logarithms…
Victor Shoup theorized that no generic discrete logarithm solving method could perform better than x
½. This is indeed the complexity of Pollard Kangaroo and Pollard rho. But he also theorized than an algorithm with precomputation can yield at best a complexity of x
⅓ which means the lower bound to break full sized secp256k1 is far less than the 2
128 estimated security.
This paper is indeed diving in that class of faster speed at the expense of memory storage.
anyone to turn it’s mathematical description into implementation ? Yes. That paper is the very basis of everything I was talking about numerous times, when saying that the DLP can be solved much faster.
You can also see it in practice whenever you hear anyone talking about precomputed data.
Note that reaching the 1/3 exponent complexity also requires doing the 2/3 exponent pre-work, so for secp256k1, if you want to reach that lower bound, you first have to do 2**170 group operations.