0
$\begingroup$

In the equation $ a^x = a^y + 1$ over a finite field $\text{GF}(2^n)$, where '$a$' is the primitive element, can one calculate $x$ as a function of $y$ without having to resort to taking the logarithm of $(a^y + 1)$?

I.e. calculate $x$ as a function of $y$, without using "$\text{log}(k)$" as part of this function.

I need to implement this in hardware, and using the $\text{log}()$ function is very costly, so I was thinking if there is a smarter way to do it.

Regards,

-Dimitri

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ I don't believe that you can. this function is known as a Zech logarithm and, for carrying out fast computations in moderately small finite fields, it is standard to store their values in a lookup table. $\endgroup$
    – Derek Holt
    Commented May 30, 2014 at 10:58
  • $\begingroup$ Derek, thank you for your answer and for mentioning Zech logarithm. I had not heard of that before. $\endgroup$
    – Dimitri
    Commented May 30, 2014 at 13:12
  • 1
    $\begingroup$ This logarithm is a lot cheaper today than two years ago. arxiv.org/abs/1306.4244 $\endgroup$
    – Ben Wieland
    Commented Jun 2, 2014 at 17:03
  • 1
    $\begingroup$ If $n\le 16$ (or may be a bit larger?), then a look-up table will do this for you. If you work on crypto, and your $n$ is in the 3-digit range, then that won't do. Index calculus may help, but may be slower than you can stomach. But that is a generic method, and won't allow you to take advantage of the known $y$. $\endgroup$
    – Jyrki Lahtonen
    Commented Jun 15, 2014 at 19:47

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .