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

$\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
    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
    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$ 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$ Jun 15, 2014 at 19:47

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.