Degenerate discrete logarithm in binary field

Given a field $\mathbb{F}_{2^n}$, are there any choices of primitive element $g$ that make the discrete logarithm easier for that generator? That is, are there any degenerate cases?

For example, if I choose a small generator like $g = x$ in $\mathbb{F}_{2^{256}}$, can I quickly find $n$ such that $g^n = a$ for a given $a$? Or is this equally difficult for any $g$ picked in any $\mathbb{F}_{2^n}$ over any irreducible polynomial?

Suppose $g$ was your 'cheap' irreducible polynomial, that is, one for which, given $g^n$, you can rederive $n$ quickly. Then, given an arbitrary pair $h, h^x$, you can quickly find $a, b$, such that $h = g^a$ and $h^x = g^b$, and then immediately deduce that $x = a^{-1}b$
• Note that a full reduction would work as follows (and as you'll see it's not really a factor of 2). Assume that there exists a generator $g$ for which it's possible to find a discrete log of a random element with probability $\epsilon$. Then, given $h,h^x$ for a random $x$, you can compute $h^r$ for a random $r$ that you choose, and find $ar$ and $b$ such that $h^r=g^{ab}$ and $h^x=g^b$. Since you know $r$ you can deduce $a$ and then as you showed $x=a^{-1}b$. The probability of success is $\epsilon^2$ since you need to succeed on two independent instances of the discrete log problem. Jul 9 '15 at 6:25
• @YehudaLindell: actually, if the mechanism succeeds with probability $\epsilon$, then a randomized procedure can solve an arbitrary DL for generator $g$ with an expected $1/\epsilon$ random tries. Then, using that, you can then solve an arbitrary DL for generator $h$ with an expected $2/\epsilon$ random tries (by first applying the base random procedure to $h$ and then applying it to $h^x$) Jul 9 '15 at 13:41