Iranian Journal of Mathematical Sciences and Informatics

Vol. 4, No. 2 (2009), pp. 55-64

DOI: 10.7508/ijmsi.2009.02.006

Generalized Jacobian and Discrete Logarithm Problem on

Elliptic Curves

H. Daghigh∗ and M. Bahramian

Department of Mathematics, Faculty of Science, University of Kashan, I. R.
Iran
E-mail: [email protected]
E-mail: [email protected]

Abstract. Let E be an elliptic curve over the finite field Fq , P a point in

E(Fq ) of order n, and Q a point in the group generated by P . The discrete
logarithm problem on E is to find the number k such that Q = kP . In this
paper we reduce the discrete logarithm problem on E[n] to the discrete
logarithm on the group F∗q , the multiplicative group of nonzero elements
of Fq , in the case where n | q − 1, using generalized jacobian of E.

Keywords: Elliptic Curve, Discrete Logarithm Problem, Generalized Jaco-

bian.

2000 Mathematics subject classification: 14H22, 14H40, 14L35.

1. Introduction
Let G be an additive finite group, x ∈ G and y ∈ x. The discrete logarithm
problem (DLP ) on G is to find the number k such that y = kx. The integer k
is called the discrete logarithm of y to the base x. If G is the group of points
on an elliptic curve over a finite field, then the discrete logarithm problem on
G is called the elliptic curve discrete logarithm problem (ECDLP ).

∗ Corresponding Author

Received 21 July 2009; Accepted 26 September 2009

2009
c Academic Center for Education, Culture and Research TMU
55
56 H. Daghigh and M. Bahramian

Koblitz [6] and Miller [7] in 1985 independently proposed using the group of
points on an elliptic curve defined over a finite field to devise discrete logarithm
cryptographic schemes. The security of these cryptosystems is based upon the
presumed intractability of computing logarithms in the elliptic curve group.
Our main result is the following theorem which reduces the ECDLP to
DLP on the underlying field.
Theorem Let E be an elliptic curve over a finite field Fq and E(Fq ) be
the set of Fq rational points of E. Also let E[n](Fq ) be the group of n-torsion
points of E defined over Fq . If n | q − 1, then solving the discrete logarithm
problem on F∗q is at least as hard as solving the discrete logarithm problem on
E[n](Fq ).
The remainder of the paper is organized as follows. The next section provides
the definition of the usual and generalized jacobians and necessary results about
them. We will prove the above theorem in section 3 (Theorem 3.3) using the
theory of generalized jacobian of the elliptic curve E. Finally an example,
which shows how to apply our method is given in the last section.

2. Usual and Generalized Jacobians

Déchène [1, 2, 3] has proposed generalized jacobians as a source of groups
for public key cryptosystems based on the hardness of the Discrete Logarithm
Problem. We will obtain a relation that presents a way to reduce the discrete
logarithm in the n-torsion part of an elliptic curve E over the finite field Fq to
the multiplicative group F∗q where n | q − 1 using generalized jacobian. First
we need some definitions and properties.
let C be a smooth algebraic curve defined over an algebraically closed field
K. Also let Div(C) be the free abelian group of all divisors of C and P rinc(C)
be the group of all principal divisors. The quotient group Div(C)/P rinc(C)
is called the Picard group or the divisor class group of C and is denoted
by P ic(C). The degree zero part of the Picard group, P ic0 (C), is simply
Div 0 (C)/P rinc(C). For elliptic curves, we have the following result which
says that the class group of divisors of degree zero on E is simply isomorphic
to the group E.

Theorem 2.1. Let E be an elliptic curve over a field K. Then the map
P −→ [(P ) − (O)] is a group isomorphism between E and P ic0 (E)with well-
 
defined inverse [ P ∈E nP (P )] −→ P ∈E nP P .

Proof. See ([12] Proposition III.3.4) 

The following theorem introduces the (usual) jacobian.

Theorem 2.2. Let C be a smooth algebraic curve of genus g defined over

an algebraically closed field. Then, there exists an abelian variety J(C) of
 Generalized Jacobian and Discrete Logarithm Problem on Elliptic Curves 57

dimension g and an isomorphism of groups

P ic0 (C) −→ J(C).

The variety J(C) is called the jacobian of C.

Proof. The proof of this theorem can be found in ([13] Proposition III.2.6). For
a more complete treatment, one can see [16]. 

Now we present an overview of generalized jacobian varieties. For more

information see [9, 10, 11]. Generalized jacobians offer a natural generalization
of both torus-based and curve-based cryptography. Starting with a smooth
algebraic curve C defined over an algebraically closed field K, two divisors
 
D = P ∈C nP (P ) and D = P  ∈C nP  (P  ) are said to be linearly equivalent
if D − D is a principal divisor, i.e. D − D = div(f ) for some f in the
function field K(C) of C. In this case, we write D ∼ D . The quotient group
obtained is then the usual jacobian J(C). To define the generalized jacobian, let

m = P ∈C mP (P ) be an effective divisor on the curve C. For a given f ∈ K(C)
we write f ≡ 1 (mod m) as a shorthand for the requirement OrdP (1 − f ) ≥ mP
for each P in the support of m.

Definition 2.3. Let m be an effective divisor and let D and D be two divisors
with supports disjoint from the support of m. We say that D and D are m-
equivalent, and write D ∼m D , if there is a function f ∈ K(C)∗ such that
div(f ) = D − D and f ≡ 1 (mod m).

It is easy to see that the above definition defines an equivalence relation

on Div(C). Also if two divisors are m-equivalent, then they must be linearly
equivalent. Therefore, if we denote by [D] the class of the divisor D under
linear equivalence and by [D]m the class of the divisor D under m-equivalence,
then [D]m ⊆ [D].
Now let Divm (C) be the subgroup of Div(C) formed by all divisors of C
with supports disjoint from m. Let also Divm 0
(C) be the subgroup of Divm (C)
of divisors of degree zero. Moreover, let P rincm (C) be the subset of principal
divisors which are m-equivalent to the zero divisor. It is easy to see that
P rincm (C) is a subgroup of Divm 0
(C). Therefore, the set of m-equivalence
0 0
classes in Divm (C) is indeed the quotient group Divm (C)/P rincm (C), which
will be denoted by P icm (C). Since [D]m ⊆ [D] for all divisor D, there exists
0

an epimorphism σ : P ic0m (C) −→ P ic0 (C).

The following theorem is an analogue of Theorem (2.2).

Theorem 2.4. Let K be an algebraically closed field and C be a smooth alge-

braic curve of genus g defined over K. Then for every modulus m, there exists
58 H. Daghigh and M. Bahramian

a commutative algebraic group Jm isomorphic to the group P ic0m (C). The di-
mension π of Jm is given by

g if m = 0,
π=
g + deg(m) − 1 otherwise.
Proof. See [10] and ([11] chapter V. Proposition 2. and Theorem 1.) 
Definition 2.5. The algebraic group Jm is called the generalized jacobian of
the curve C with respect to the modulus m.
To obtain a representation of the elements of the generalized jacobian we
need the following theorem.
Theorem 2.6. Let (G, +) be a group and (A, ·) be an abelian group. Let also
p
1 −→ A −→ G −→ G −→ 0
be a short exact sequence defining a group extension G of G by A. Denote by
⊕ the group operation on G. Then,
1: Let s : G −→ G be a (set-theoretic) section for p (i.e. p ◦ s = 1G ).
Then the map
A × G −→ G
(a, σ)  a ⊕ s(σ)
is a bijection of sets. Hence, each element of G can be represented as
a pair (a, σ), where a ∈ A and σ ∈ G.
2: There is a well-defined natural action of G on A given by
A × G −→ A
(a, σ)  aσ := x ⊕ a x
where x is any element of G satisfying p(x) = σ and x denotes the
inverse of x in G.
3: In fact, the group operation ⊕ : G × G −→ G can be expressed in terms
of this action:
(a, σ) + (b, τ ) = (a · bσ · c(σ, τ ), σ + τ )
where c : G × G −→ A must satisfy the following condition
(2.1) c(σ, τ ) · c(σ + τ, ρ) = c(τ, ρ)σ · c(σ, τ + ρ).
(A function c satisfying (2.1) is called a 2-cocycle on G with values in A.)
Proof. see ([4] chapter III) and ([17] chapter 5) 
In the case that G is commutative, (2.1) can be rewritten as
c(σ, τ ) · c(σ + τ, ρ) = c(τ, ρ) · c(σ, τ + ρ).
Moreover we have the following Lemma.
 Generalized Jacobian and Discrete Logarithm Problem on Elliptic Curves 59

Lemma 2.7. With the notation of the above theorem

c(σ, τ ) · c(−σ, σ + τ ) = 1
for all σ, τ ∈ G.

Proof. See ([5] Lemma 7.1) and [14] for a more complete treatment. 
Theorems 2.2 and 2.4 and the epimorphism σ : P ic0m (C) −→ P ic0 (C) implies
that there exists an epimorphism τ : Jm −→ J. Let Lm be the kernel of τ , then
the short exact sequence
τ
1 −→ Lm −→ Jm −→ J −→ 0
defines the group extension Jm of J by Lm . It then follows from Theorem 2.6
that the elements of Jm could be seen as pairs (k, P ), where k ∈ Lm and P ∈ J.
Using this representation, the group law on Jm could be expressed in terms of
the group laws on Lm and on J, and also involves a 2-cocycle on J with values
in Lm .
Moreover the short exact sequence
ι ρ
1 −→ Lm −→ Lm × J −→ J −→ 0
with obvious maps ι and ρ also defines another group extension Lm × J of J
by Lm . But can Jm be the direct product Lm × J? Rosenlicht answers this
question in the following theorem.

Theorem 2.8. Let C be a smooth algebraic curve of genus g defined over

an algebraically closed field and let Jm be the generalized jacobian of C with
respect to a modulus m. If g ≥ 1 and deg(m) ≥ 2, then Jm is not a trivial direct
product.

Proof. This is a corollary of Theorem 13 in [10]. 

Theorem 2.9. Let C be a smooth algebraic curve defined over an algebraically

closed field, J be the jacobian of C and Jm be the generalized jacobian of C

with respect to a modulus m = P ∈C mP (P ) of support Sm . Let also Lm be
the kernel of the natural homomorphism τ from Jm onto J, and let Gm {x ∈
A1 |x = 0}. Then, Lm is an algebraic group isomorphic to the product of a

torus T = GmSm −1 by a unipotent group V of the form V = P ∈Sm V(mP )
where each V(mP ) is isomorphic to the group of matrices of the form
⎛ ⎞
1 a1 a2 . . . amP −1
⎜0 1 a . . . a ⎟
⎜ 1 mP −2 ⎟
⎜ ⎟
⎜0 0 1 . . . amP −3 ⎟ .
⎜. . .. ⎟
⎜. . .. . . ⎟
⎝. . . . . ⎠
0 0 0 ... 1
Proof. See ([11] Chapter V). 
60 H. Daghigh and M. Bahramian

Now let E be an elliptic curve defined over the finite field K = Fq with q
elements and let m = (M ) + (N ), where M and N are distinct nonzero points
of E(Fq ).
Finally, let Jm be the generalized jacobian of E with respect to m. In the light
of Theorems 2.8 and 2.9, this choice of parameters implies that this generalized
jacobian will be an extension of the elliptic curve E by the multiplicative group
Gm . We already know that there is a bijection of sets between Jm and Gm × E.
Hence, each element of Jm can be represented as a pair (k, P ), where k ∈ Gm
and P ∈ E Indeed, we have by construction that Jm is isomorphic to P ic0m (E),
and so an explicit bijection of sets ϕ : P ic0m (E) −→ Gm × E could be used to
transport the known group law on P ic0m (E) to Gm × E.
Déchène ([1] Chapter 5, Propositions 5.1 and 5.4) has proved the following
two theorems which represent the elements of Jm using the isomorphism be-
tween P ic0m (E) and Gm × E and obtaining a formula for the group operation
on Gm × E.

Theorem 2.10. Let E be an elliptic curve defined over Fq , m = (M ) + (N )

with M, N ∈ E\{O}, M = N and T ∈ E\{O, M, N, M − N, N − M }, be given.
Let also
ψ : P ic0m (E) −→ Gm × E
[D] −→ (k, S)

be such that the m-equivalence class of D = P ∈E nP (P ) corresponds to S =
 ∗
P ∈E nP P and k = f (M )/f (N ), where f ∈ K(E) is any function satisfying

D − (S) + (O) if S ∈
/ {M, N } ,
div(f ) =
D − (S + T ) − (T ) otherwise.
Then ψ is a well-defined bijection of sets.

Theorem 2.11. Let E be an elliptic curve defined over Fq and let m = (M ) +

(N ) be given such that M and N are distinct nonzero points of E. If (k1 , P1 )
and (k2 , P2 ) are elements of Jm fulfilling P1 , P2 , ±(P1 + P2 ) ∈ / {M, N } then
(k1 , P1 ) + (k2 , P2 ) = (k1 k2 cm (P1 , P2 ), P1 + P2 ) where cm : E × E −→ Gm is a
2-cocycle depending on the modulus m and
LP1 ,P2 (M )
cm (P1 , P2 ) =
LP1 ,P2 (N )
l ∗
where LP1 ,P2 (M ) = c · lP P+P
1 ,P2
for some c ∈ K (that we can suppose that
1 2 ,O
c = 1). Also lP,Q denotes the equation of the line passing through P and Q
(tangent at the curve if P = Q).

We here present a small collection of the basic properties of the group law
in these generalized jacobians, which are easily derived from Theorem (2.11).
 Generalized Jacobian and Discrete Logarithm Problem on Elliptic Curves 61

Corollary 2.12. Let E be an elliptic curve defined over Fq and let m = (M ) +

(N ) be given such that M and N are distinct nonzero points of E. Let also
(k, P ), (k1 , P1 ), (k2 , P2 ) ∈ Jm be given such that P1 , P2 , ±(P1 + P2 ) ∈
/ {M, N }.
Then,
1: cm (P1 , P2 ) = cm (P2 , P1 ) (This reflects the fact that Jm is abelian).
2: cm (O, P ) = 1 for all P ∈ / {M, N }. Hence, (k1 , O)+(k2 , P ) = (k1 k2 , P )
.
3: (1, O) is the identity element of Jm .
4: Furthermore, Jm contains a subgroup isomorphic to Gm , as (k1 , O) +
(k2 , O) = (k1 k2 , O) for all k1 , k2 ∈ Gm .

3. Discrete Logarithm Problem

Definition 3.1. (Discrete Logarithm Problem) Let G be a finite cyclic group
of order n generated by an element g . Given h ∈ G, determine the integer
k ∈ [0, n − 1] such that g k = h. This integer is called the discrete logarithm of
h (to the base g), and is denoted logg (h).
In this section we will reduce the discrete logarithm problem in the n-torsion
subgroup of an elliptic curve E over a finite field K with q elements, where
n | q − 1 to the discrete logarithm problem in multiplicative group of K.
Remark 3.2. Given a group G, an element g ∈ G and a natural number t, we
can compute g t very fast using the known (left-to-right) ”square-and-multiply”
algorithm. If t = (tm · · · t1 t0 )2 is the binary representation of t, then
m
tm +2m−1 tm−1 +···+2t1 +t0
gk = g2
= ((· · · ((g 2 g tm−1 )2 g tm−2 )2 · · · )2 g t1 )2 g t0 .
Theorem 3.3. Let E be an elliptic curve over a finite field Fq and E(Fq ) be
the set of Fq rational points of E. Also let E[n](Fq ) be the group of n-torsion
points of E defined over Fq . If n | q − 1, then solving the discrete logarithm
problem on F∗q is at least as hard as solving the discrete logarithm problem on
E[n](Fq ).
Proof. Let P ∈ E be a point of order n, and m = (M ) + (N ) be a divisor prime
to all prime divisors (rP ) for those 0 < r < n which occur in the ”square-
and-multiply” algorithm, as noted in Remark 3.2. Also let αt (P ) be the first
component of t(1, P ) where (1, P ) ∈ Jm . We prove that
q−1 q−1
(3.1) αn (kP ) n = (αn (P ) n )k
for all integer k.
The case k = 0 is clear. For k > 0, let Q = kP and calculate αnk (P ), the
first component of nk(1, P ) in two ways. From Theorem 2.11, we know
αt (P ) = cm (P, P )cm (P, 2P ) · · · cm (P, (t − 1)P ).
62 H. Daghigh and M. Bahramian

At first
nk(1, P ) = n(k(1, P )) = n(αk (P ), kP ) = n(αk (P ), Q)
= (αk (P )n αn (Q), nQ) = (αk (P )n αn (Q), O)
thus αnk (P ) = αk (P )n αn (Q). Also
nk(1, P ) = k(n(1, P )) = k(αn (P ), nP )
= k(αn (P ), O) = (αn (P )k , O)
thus αnk (P ) = αn (P )k . Comparing these two last equation implies that
(3.2) αk (P )n αn (Q) = αn (P )k
and from this we have
q−1 q−1
αn (Q) n = (αn (P ) n )k .
Now let k < 0. From Lemma 2.7 cm (R, S)cm (−R, R + S) = 1 for all R, S ∈ E
then
cm (Q, Q)cm (−Q, 2Q) = 1
cm (Q, 2Q)cm (−Q, 3Q) = 1
..
.
cm (Q, (n − 1)Q)cm (−Q, O) = 1
cm (Q, O)cm (−Q, Q) = 1.
Multiplying the above equations gives αn (Q)αn (−Q) = 1 that implies αn (−Q) =
(αn (Q))−1 and the proof is now complete. 

Remark 3.4. Using the above theorem, discrete logarithm on E is reduced to

discrete logarithm on Fq . Note that by the standard reduction of Pohlig and

Hellman [8] we can assume that n is prime. For, let n = i pei i be the prime
factorization of n. To find k from Q = kP , the idea of Pohlig-Hellman is to find
k (mod pei i ) for each i, then use the Chinese Remainder theorem to combine
these and obtain k (mod n) ([15], Section 5.2.3). Therefore we can assume that
q−1 q−1
n is prime. Now assuming αn (P ) n = 1, from (αn (P ) n )n = 1 we deduce
q−1
that OrdF∗q (αn (P ) n ) = n. Since k < n, if one can solve discrete logarithm
on F∗q then k will be obtained uniquely.

Remark 3.5. In the generalized jacobian Jm let (a, P ) and (b, Q) be the repre-
sentation of two elements of Jm such that (b, Q) = k(a, P ). Also let Ord(P ) =
n. In this case b = ak αk (P ) and therefore from (3.2)
bn αn (Q) = akn αk (P )n αn (Q) = akn αn (P )k = (an αn (P ))k . If an αn (P ) is a
primitive root of unity in F∗q , then the equation bn αn (Q) = (an αn (P ))k gives
a discrete logarithm problem in F∗q .
 Generalized Jacobian and Discrete Logarithm Problem on Elliptic Curves 63

4. An Example
With a simple PARI program we can calculate αn (P ) and αn (Q) very fast
(in logarithmic time).
Consider the elliptic curve
E : y 2 + xy + y = x3 + 2x2 + 6x + 7
defined over the finite field Fq with q = 152617819 elements. We reduce the
discrete logarithm problem on this elliptic curve to a discrete logarithm problem
in F∗q .
Consider P = (23658750, 133471885) ∈ E(Fq ) , Q = kP = (129045381, 133258769)
with k = 4276384. The order of P is Ord(P ) = 25436303. The points M = 4P and
N = 5P do not occur in the calculation αn (P ) and αn (Q) by repeated doubling
process. We get
q−1
αn (P ) n = αn (P )6 = 76904832,
q−1
αn (Q) n = αn (Q)6 = 95183794.
Hence in order to compute k we have to solve the discrete logarithm problem
(4.1) 95183794 ≡ 76904832k (mod q).
Of course one can check in this example that k is a solution of the equation (4.1).

References
[1] Isabelle Déchène, Generalized Jacobians in Cryptography, PhD thesis, McGill University,
2005.
[2] Isabelle Déchène, Arithmetic of generalized Jacobians, in ”Algorithmic Number Theory
Symposium ANTS VII” (eds. F. Hess, S. Pauli and M. Post), 4076, Springer-Verlag,
2006, 421-435.
[3] Isabelle Déchène, On the security of generalized jacobian cryptosystems, Advances in
Mathematics of Communications, 1 (4) (2007), 413-426.
[4] Peter Hilton and Urs Stammbach, Course in Homological Algebra, Number 4 in Grad-
uate Texts in Mathematics. Springer-Verlag, New York, 1971.
[5] J. Scott Carter, Daniel Jelsovsky, Seiichi Kamada, Laurel Langford and Masahico Saito,
Quandle Cohomology and State-sum Invariants of Knotted Curves and Surfaces, Trans.
Amer. Math. Soc., 355 (2003), 3947-3989.
[6] N. Koblitz, Elliptic curve cryptosystems, Mathematics of Computation, 48 (1987), 203-
209.
[7] V. Miller, Use of elliptic curves in cryptography, Advances in CryptologyCRYPTO, 85
(LNCS 218, [483]) (1986), 417-426.
[8] G. C. Pohlig and M. E. Hellman, An improved algorithm for computing logarithms
over GF (p) and its cryptographic significance, IEEE Trans. Info. Theory, 24 (1978),
106-110.
[9] Maxwell Rosenlicht, Equivalence relations on algebraic curves, Annals of Mathematics,
56 (1952), 169-191.
[10] Maxwell Rosenlicht, Generalized Jacobian varieties, Annals of Mathematics, 59 (1954),
505-530.
[11] Jean-Pierre Serre, Algebraic groups and class fields, Vol. 117 of Graduate texts in math-
ematics, Springer-Verlag, New-York, 1988.
64 H. Daghigh and M. Bahramian

[12] Joseph H. Silverman, The arithmetic of elliptic curves, Vol. 106 of Graduate Texts in
Mathematics, Springer-Verlag, New York, 1986.
[13] Joseph H. Silverman, Advanced topics in the arithmetic of elliptic curves, Vol. 151 of
Graduate Texts in Mathematics, Springer-Verlag, New York, 1994.
[14] M. Wakui, On Dijkgraaf-Witten invariant for 3-manifolds, Osaka J. Math., 29 (1992),
675-696.
[15] L. C. Washington, Elliptic Curves, Number Theory and Cryptography, Chapman and
Hall / CRC, 2003.
[16] André Weil, Variétés abéliennes et courbes algébriques, Vol. 1064 of Actualités Sci. Ind.
Hermann and Cie, Paris, 1948.
[17] Edwin Weiss, Cohomology of groups, Pure and Applied Mathematics, Vol. 34, Academic
Press, New York, 1969.