In the paper Koblitz and Menezes say "it is conceivable that the NSA has found (or believes that there might exist) a similar algorithm that requires far less precomputation."
This made we wonder; are there any historic example(s) of an algorithm we have improved over time which lead to the side stepping of a previously unavoidable and large pre-computation?
>3.2. Does NSA have an $n^{1/3}$-algorithm for finding elliptic curve discrete logs? ...
In 2013 Bernstein and Lange described such an algorithm albeit with intractable pre-computation costs. [https://www.iacr.org/conferences/asiacrypt2013/slides/44.pdf]
In the paper Koblitz and Menezes say "it is conceivable that the NSA has found (or believes that there might exist) a similar algorithm that requires far less precomputation."
This made we wonder; are there any historic example(s) of an algorithm we have improved over time which lead to the side stepping of a previously unavoidable and large pre-computation?