Is anyone aware of an in-depth study of algorithms using preprocessing to compute fixed-base exponentiations? Assuming I am willing to do arbitrary computation in the preprocessing phase (but not store an arbitrary amount of data afterward), what is the optimal time/storage tradeoff here?

Note: I have read this page on Wikipedia as well as this answer from 9+ years ago. (However, the link provided there to a paper that may help answer my question no longer works.)

  • 1
    $\begingroup$ The link in this answer should be fixed. $\endgroup$
    – fgrieu
    Aug 7, 2023 at 18:43
  • $\begingroup$ Thank you -- I think that pretty much answers my question, since the paper is exactly what I am looking for and google scholar doesn't show any improvements to that paper $\endgroup$
    – user432944
    Aug 7, 2023 at 20:27
  • 1
    $\begingroup$ Don't forget to vote up the earlier question / answer. Besides giving back recognition & higher score on e.g. search engines, it may also gain more interest of other cryptographers; maybe they know a better trick. $\endgroup$
    – Maarten Bodewes
    Aug 8, 2023 at 1:10


Browse other questions tagged or ask your own question.