A completely new class of method for computing discrete logarithms

This 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¹²⁸ estimated security. Though in the case of this paper, the required memory or storage would be 2⁶⁴×256bits

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 an implementation ?

A completely new class of method for computing discrete logarithms

This 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 2128 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 an implementation ?

A completely new class of method for computing discrete logarithms

This 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 2128 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 an implementation ?