Cryptographic applications based on the discrete logarithm problem require a cyclic group (or subgroup) with large prime order.
The difficulty of computing discrete logarithms depends entirely on the representation of this group. If, for example, the group in
question is represented as the additive integers mod *p*, then discrete logarithms can be computed quite easily even when *p*
is very large (it suffices to find a multiplicative inverse mod *p*, easily accomplished with the Euclidean algorithm).
On the other hand, if the "same" group is represented by the points of an elliptic curve
or the Jacobian of a hyperelliptic curve, the discrete logarithm is believed to be very difficult to compute. Ideally, one would like a
group to be represented generically so that it is effectively a *black-box group*, one in which the only means of obtaining information is
by performing group operations and testing group elements for equality.

Under this idealized assumption, it can be proven that the discrete logarithm problem is hard, requiring &Omega(*N*^{1/2}) group
operations, where *N* is the size of the group (of prime order), as shown by Shoup [1]. In practice this assumption is never
realized. Any practical cryptographic system necessarily encodes information in the representation of group elements. For certain
representations, including many Jacobians, it is *believed* that this information does not make the discrete logarithm problem any easier and that a
&Omega(*N*^{1/2}) lower bound applies. There is not, and almost certainly never will be, any *proof* that this belief is justified.
It is a working assumption and should be regarded as such.

In several cases this assumption is actually known to be false, i.e., there are algorithms which can compute the discrete logarithm in certain Jacobians
using o(*N*^{1/2}) steps (group operations or arithmetic operations). The three main cases of interest are listed below.

**Genus***g*&ge 3- For a hyperelliptic curve C over F
_{q}with J(C) cyclic, the discrete logarithm program can be solved in soft-O(*q*^{2-2/g}) time [2]. This can be generalized to plane curves with J(C) of known structure, not necessarily cyclic [3].

**Non-prime fields F**_{pd}- For a genus 2 curve C, the discrete logarithm problem in J(C/F
_{pd}) can be transferred to the Jacobian of a genus 4 curve over F_{p}when*d*= 2, and when*d*= 3 the problem can be transferred to a genus 6 curve [4] (other transfers are known for larger*d*and*g*). Once transferred to a higher genus curve, the discrete logarithm problem can be solved more efficiently using the result above.

**Trace zero varieties**- The discrete logarithm problem in the trace zero variety T
_{3}(C) of a genus 2 curve C can be transferred to a genus 5 curve provided that #J_{2}(C) is divisible by 3. Otherwise, with high probability, the problem can transferred only to a curve of genus greater than 6 [4].

Note that for fixed *g* and *d*, these algorithms still require exponential time, O(exp(*c*log*N*)), but the constant *c* is less than 1/2.
We take as our "gold standard" a genus 2 Jacobian over a prime field with prime order *N*, which is unaffected by the results above. To assess the
"effective" security of any particular Jacobian (or trace zero variety), we determine how much larger the group would need to be to make the difficulty of the
discrete logarithm problem roughly equivalent, using currently known algorithms. If *n* = lg*N* is the size of our standard genus 2 Jacobian and *m*=lg*M*
is the size of the group in question, we are interested in the ratio *m*/*n*. Applying the results above, we then have
*
*

- For a genus 3 hyperelliptic curve over a prime field,
*m*/*n*= 9/8.

- For a genus 2 curve over F
_{p2}we have*m*/*n*= 4/3.

- For the trace zero variety of a genus 2 curve over F
_{p3}the ratio*m*/*n*is 5/4 when #J_{2}(C) is divisible by 3 and 6/5 otherwise.