A note on cyclic groups, finite fields, and the discrete logarithm problem (Q1196516)

Let \(F_ q\) denote the finite field of order \(q\) and \(E(F_ q)\) and elliptic curve over \(F_ q\). Previous work showed how the discrete logarithm problem in the additive group of \(E(F_ q)\) can be reduced to the discrete logarithm problem in \(F_{q^ k}\) for some integer \(k\) in the case \(gcd(\# E(F_ q),q)=1\). It is shown here how the logarithm problem in the curve of the Pell equation \(x^ 2-Dy^ 2=1\) can be reduced to the logarithm problem \(F_ q\) or \(F_{q^ 2}\), \(q\) odd. It is also shown that the logarithm problem in certain cyclic subgroups of \(GL(n,q)\), the group of nonsingular \(n\times n\) matrices over \(F_ q\), can be reduced to the logarithm problem in an extension of \(F_ q\). The results indicate the group \(G\) must be carefully chosen for cryptographic purposes.