We can represent elements of a finite field $F$ in various ways polynomial basis and normal basis. There is one other; generator-based representation and this is based on the fact that the multiplicative group of a finite field ($F^*$) is cyclic so there is a generator of this cyclic group, call $g$ and we write $\langle g \rangle = F^*$. Now every element of $F^*$ can be written as powers of the generator as $x = g^i \in F$ for some positive integer $i$. The identity is $g^0$. In this way, the multiplication is easy

$$\text{let } a,b\in F, \text{ and } a = g^x, b = g^y \text{ then } a\cdot b = g^{x+y}.$$ The bonus is the fact that the discrete log is easy since we tack the elements by the generator's power but the addition seems hard. $$a +b = g^x + g^y = g^z, \quad z =?$$ Questions;

  1. How hard the addition?
  2. Are there any cryptographic scheme that uses this hardness?

1 Answer 1


The term used for the function $Z(\cdot)$ defined by $$ g^{x}+g^{y}=g^{x}(1+g^{y-x})=g^x g^{Z(y-x)}, $$ in coding theory literature is Zech's logarithm. So for your formulation $$z=x+Z(y-x)=y+Z(x-y).$$ It is no more than the DL of $(1+g^{x-y})$ and is believed to be as hard as DL.

In coding theory it is normally considered for even characteristic groups $G=GF(2^m)^\ast$ in which case it is actually just the DL composed with a permutation $\pi$ of order 2 in the additive exponent group $\mathbb{Z}_{2^m-1}.$

I seem to recall Odlyzko mentioning it in a survey on DL in early 1990's. In any case, I don't know of it being directly used in cryptographic schemes, but others might.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.