Andreas Enge
email: enge@math.uniaugsburg.degaudry@lix.polytechnique.fr

Pierrick Gaudry

A General Framework for Subexponential Discrete Logarithm Algorithms

Keywords: discrete logarithm, index calculus, class groups, subexponentiality. R esum e logarithme discret, calcul d'index, groupes de classes, sous-exponentialit e. 1

We describe a generic algorithm for computing discrete logarithms in groups of known order in which a smoothness concept is available. The running time of the algorithm can be proved without using any heuristics and leads to a subexponential complexity in particular for nite elds and class groups of number and function elds which were proposed for use in cryptography. In class groups, our algorithm is substantially faster than previously suggested ones. The subexponential complexity is obtained for cyclic groups in which a certain smoothness assumption is satis ed. We also show how to modify the algorithm for cyclic subgroups of arbitrary groups when the smoothness assumption can only be veri ed for the full group.

Introduction

Every nite abelian group is isomorphic to a direct sum of cyclic groups Z=e i Z, where the e i are unique provided that e i+1 divides e i . Given such a group a natural task is to make this isomorphism explicit, hence two fundamental computational problems arise. The rst one is to determine the order of the group and its structure (i.e. the e i ), and the second one is to compute discrete logarithms in it. When those two tasks are feasible, most of the questions concerning the group can be transferred to the simpler representation. In this paper we assume that the group order is known and we concentrate on the discrete logarithm computation: Given an additively written abelian group G, an element g 1 2 G and another element g 2 2 hg 1 i, the problem consists of nding an integer l such that g 2 = lg 1 . Obviously, the di culty of the problem depends on the representation of the group. In (Z=NZ; +), for instance, the problem reduces to taking an inverse modulo N and can be solved in polynomial time by the Euclidean algorithm. In general the problem is hard and, following Di e and Hellman's and ElGamal's constructions [START_REF] Cohen | A course in algorithmic algebraic number theory[END_REF][START_REF] Eberly | On randomized Lanczos algorithms[END_REF], it is possible to base a cryptosystem on it.

The rst examples of such groups were the multiplicative groups of nite elds; it turned out that in this case the discrete logarithm problem can be solved in expected subexponential time by so-called \index calculus algorithms" (see Odl99] and the references therein), so that the key size in a secure system based on such a group must be relatively large.

Other important examples are class groups of number elds [START_REF] Lenstra | A hyperelliptic smoothness test[END_REF][START_REF] Buchmann | A subexponential algorithm for the determination of class groups and regulators of algebraic number elds[END_REF] and Jacobians, i.e. divisor class groups, of elliptic Mil86, Kob87] and hyperelliptic curves Kob89] over nite elds. Extending the \index calculus" method for nite elds, algorithms with conjectured or rigorously proven subexponential running time for the discrete logarithm problem in class groups of number elds Buc90, D ul91] and high-genus hyperelliptic Jacobians ADH94, Eng99] and related structures MST99] were devised. However, the constants of the running time bounds for these algorithms are substantially weaker than for the nite eld case. This is due to the fact that the index calculus algorithms for class groups proceed by solving both computational tasks mentioned in the rst paragraph: In a rst step, the structure of the group under consideration is determined as a product of cyclic groups, in a second step, the actual discrete logarithm is computed. For the multiplicative groups of nite elds, which are cyclic and of known order, the rst phase can be omitted.

In the present article we close the gap between the running times of discrete logarithm algorithms for nite elds and class groups. We provide a general framework for solving the discrete logarithm problem in nite abelian groups which possess an analogue to the unique prime decomposition of integers. Our basic additional assumption is that the group be cyclic and of known order, which closely follows the special case of nite elds. If a certain smoothness assumption is satis ed, our algorithm has a provable subexponential expected running time. Examining how the well-studied discrete logarithm problem in nite elds ts into our framework, we recover the same running time as for the fastest rigorously analysed algorithms known so far. We obtain corresponding running time results for class groups, which constitute a major improvement compared to the above mentioned algorithms. The main result of this paper is the following:

Theorem 1 There exists a probabilistic algorithm that solves a discrete logarithm problem in the Jacobian of a hyperelliptic curve of genus g over the nite eld F q when the group is cyclic of known order and g= log q tends to in nity. It takes expected time L q g ( p 2 + o(1)):

Assuming the extended Riemann hypothesis, there exists a probabilistic algorithm that solves a discrete logarithm problem in the class group of an imaginary quadratic eld of discriminant D when the group is cyclic of known order N. It takes expected time L N ( p 2 + o(1)) = L D (1 + o(1)): (Here L x (c) stands for exp(c p log x p log log x).)

Note that we are interested in algorithms with a provable running time only (possibly under the Riemann hypothesis in the number eld case), whence we do not take into account algorithms of the number eld sieve type. Such algorithms are conjectured to be asymptotically faster than ours (and there are both plausible theoretical considerations and numerical evidence to support this conjecture). In any case, they are only available for nite elds and not for class groups.

The assumption that the group is cyclic and of known order is no restriction from a cryptographic point of view, as knowledge of the group order is required for digital signatures and to prove resistance against the Pohlig{Hellman attack. However, the discrete logarithm problem often has to be solved in a cyclic subgroup, whereas the smoothness assumption can only be veri ed for the full group, which itself may not be cyclic. We show that a variant of the algorithm applies to cryptographically suitable subgroups. Moreover, the modi cations allow to detect the case that no discrete logarithm exists, in which the original algorithm would run forever. We proceed as follows. In Section 2 we introduce the general setting in which the algorithm described in Section 3 can be used to compute discrete logarithms. The subsequent sections are devoted to the analysis of the algorithm. We extend some results on sparse linear algebra to evaluate the probability that the algorithm succeeds and verify its subexponential running time. Along the way, the general considerations are specialised to classical examples. Finally, in Section 7 we explain how to adapt the algorithm for the cases where the group is not cyclic.

Notations and prerequisites

Throughout the paper, we denote by Z the set of integers, by N the set of positive integers, by log the natural and by log 2 the dual logarithm. Let G be an additively written cyclic group of known order N, and let Z N denote Z=N Z. In general, one would expect that the elements of G are represented by O(log N) bits and measure algorithmic complexities as functions of N. It is, however, possible to construct groups whose elements are naturally represented by bit strings of length in O(log N 0 ) for some value N 0 considerably larger than N. For instance, Jacobian groups of curves of genus g over F 2 are given by (log N 0 ) bits for N 0 = 2 g , whereas the only known lower bound on N in this case is the Hasse{Weil bound ( p 2 1) g 1. While this situation results in a waste of bandwidth for cryptographic applications and is thus unlikely to occur, for preserving as much generality as possible we henceforth denote by log N 0 the input size of the problem and measure all complexities by functions in log N 0 . It turns out that factors polynomial in log N 0 do not a ect the subexponential running time. Hence to simplify the analysis we follow GG99] and for some positive function f of N 0 denote by O (f) the class of functions which are in O(f) up to a factor bounded by some power of log N 0 .

To apply the index calculus idea, G must behave similarly to the natural integers or the polynomials over a nite eld in that each element of G admits a unique decomposition into a \sum of primes". To model this behaviour, assume that there is a free abelian monoid M over a countable set P, whose elements are called primes, together with an equivalence relation on M which is compatible with its composition law, such that G ' M = . Thus, each element of M has a unique decomposition into a sum of primes. Let each element of G be represented by a unique element of M of bit size in O (1), then G inherits the unique decomposition property. We assume that the arithmetic in G (addition, negation and test for equality) is performed by manipulating these unique representatives in time polynomial in log N 0 . Furthermore, we assume that there is a homomorphism of monoids deg : M ! R + , which to each element of M (and thus of G) associates its \size". As M is free over P, any such homomorphism is given by assigning a non-negative size to each prime and extending additively. Usually the \size" deg(m) and the bit size of m are closely related in the sense that the latter is in (deg(m)). The setting above was introduced by Knopfmacher in Kno75], who calls M an additive arithmetical semigroup and G an arithmetical formation. In addition we require that deg(p) 1 for p 2 P and deg(g) 2 O (1) for any g 2 G. This ensures that the number of primes in the decomposition of a group element, counting multiplicities, is bounded above by O (1).

For a smoothness bound S 2 N denote by P S the set of primes of size at most S, by n S the cardinality of P S and by n 0 S the number of elements of M of size at most S. From an algorithmic point of view, we demand that n 0 S be nite, that the elements of size at most S can be enumerated in time polynomial in S and linear in n 0 S and that an element m 2 M can be tested for being prime in time polynomial in deg(m) and linear in n 0 deg(m) (by trial division by all elements of size smaller than deg m, for instance). Thus, P S can be constructed in time polynomial in S and quadratic in n 0 S . In practice, Eratosthenes's sieve could be used to lower the complexity in n 0 S ; however, the algorithms studied below are at least quadratic in n 0 S . An element of G is called S{smooth if its decomposition involves only primes of P S . As the size of the elements of G is in O (1), a distinction into smooth and non-smooth elements arises only for S 2 O (1). For technical reasons we assume furthermore that log n S 2 O (1). We require that elements of G can be tested for S{smoothness and, if possible, be decomposed into a sum of primes from P S in O (n S ), which usually amounts to trial division by the elements of P S . In all cases considered below, the smoothness test and the decomposition are even in O ( p n 0 S ) or O (1), which results in better running times. The most e cient smoothness test available for integers to date, which is subexponential in log n 0 S , is non-deterministic and not completely reliable in that it may not recognise a smooth element. Thus, we extend our model as follows: The smoothness test rejects all non-smooth elements; it recognises a smooth element up to a certain error probability, which may depend on the element tested, but does not exceed 1=2. It should be noted that we could work with a more general de nition of smoothness, which does not involve the notion of the size of an element. Also, unique decomposability could be de ned in an abstract way, not involving the notion of a free abelian monoid. However, the more intuitive de nitions apply to all groups considered in the literature so far.

Examples.

Finite prime elds G = F p

Then G can be represented as (N; )= , where m 1 m 2 if and only if pjm 1 m 2 , and P is the set of natural prime numbers. The size of an element is given by its logarithm to the base 2, deg(m) = log 2 m, and N 0 = N = p 1.

Finite elds of characteristic 2, G = F 2 k

Then G can be represented as (F 2 X]nf0g; )= , where f 1 f 2 if and only if fjf 1 f 2 for some xed irreducible polynomial f of degree k in F 2 X], and P is the set of irreducible polynomials over F 2 . The size of an element is given by its usual degree, and N 0 = N = 2 k 1. 3. Finite elds of the form G = F p k , p prime Then G can be represented by the polynomials of degree less than k over F p . Denote by F p X] 0 the set of monic polynomials over F p . Noticing that any polynomial is the unique product of its leading coe cient and a monic polynomial, G can be represented as (N; ) (F p X] 0 ; )= , where (m 1 ; f 1 ) (m 2 ; f 2 ) if and only if pjm 1 m 2 and fjf 1 f 2 for some xed irreducible polynomial f of degree k over F p . The set of primes P is given by the union of the set of natural primes and the set of monic irreducible polynomials over F p , each embedded into the cartesian product. The size of an element is deg(m 1 ; f 1 ) = log 2 m 1 + deg f 1 , and N 0 = N = p k 1.

Notice that these de nitions are compatible with Examples 1. and 2.

Class groups of number elds

Let K be a number eld and O its ring of integers. Then the class group G of K is de ned as M = , where M is the set of ideals of O (a free abelian monoid over the set P of prime ideals), and is induced by the submonoid of principal ideals. The size of an ideal is given by the logarithm of its norm. If K has unit rank 0, then each ideal class contains a unique so-called reduced ideal, which can be computed in polynomial time from any representative of the class as long as (K : Q ) is xed. This reduced ideal then constitutes the canonic representative for the class. In particular, the case of imaginary quadratic elds

Q ( p D) of discriminant D < 0 is covered. Let ! = D+ p D 2 with minimal polynomial X 2 DX + D 2 D
4 be an element generating an integral power basis. Then P S can be constructed by enumerating all rational primes p 2 S and solving the equation y 2 p Dy p + D 2 D 4 0 (mod p), which can be done in expected polynomial time by a probabilistic algorithm. If this equation does not have a solution, then p is inert and pO is a principal prime ideal, whence it may be omitted from the factor base.

If the equation has the double solution y p = 0, then p is rami ed and (p; !) is the only prime ideal above p in O. Finally, if the equation has two solutions y p and y p , then p is splitting and p = (p; ! y p ) and p = (p; ! y p ) are the two prime ideals above p in O.

A reduced ideal a = (a; ! b) with ajb 2 Db + D 2 D 4 is S{smooth if and only if all prime divisors of a are bounded above by 2 S . Let p be a prime divisor of a and the exponent of p in a. Then, as the ideal is reduced, it can be shown that p is not inert, so there is an ideal of the form p = (p; ! y p ) above p in O. If y p b (mod p), then the ideal occurs with multiplicity in the decomposition of a, otherwise, p occurs with multiplicity . Thus, the smoothness test and the decomposition of class group elements into primes is completely reduced to the same problems over the rational integers. Again, we let N 0 = N.

Jacobians of curves over nite elds

Let C 2 F q X; Y ] be a plane irreducible projective curve, and G its Jacobian. Fix a divisor O of degree 1, and let P denote the set of all P (deg P) O with a prime divisor P. The size of such an element of P is given by deg P. Then G ' M = , where M is the free monoid over P and is induced by the submonoid of principal divisors. If the prime at in nity of F q X] is totally rami ed in the function eld of the curve, we may choose O as the prime divisor at in nity, and the Jacobian is isomorphic to the ideal class group of the integral closure of F q X; Y ] in the function eld. Of particular interest is the case of hyperelliptic curves, which constitute the function eld analogue of quadratic number elds. A hyperelliptic curve of genus g over F q is the smooth projective model of a plane curve of the form H = Y 2 + hY f with h 2 F q X] of degree at most g and f 2 F q X] monic of degree 2g + 1 or 2g + 2.

If deg f = 2g + 1, the prime at in nity is rami ed and the representation of the hyperelliptic curve by H is called imaginary. The use of such curves in cryptography has been suggested

by Koblitz in Kob89]. Each divisor class of a hyperelliptic Jacobian in imaginary representation contains a unique reduced divisor div(a; b) which corresponds to the ideal (a; Y b) of F q X; Y ]=(H) and satis es a, b 2 F q X], deg b < deg a g and ajb 2 + bh f. Its size is deg a. So the input size of the problem is O(log N 0 ) for N 0 = q g . The assumption that N 2 O (N 0 ) holds since N (2g + 1)q g . For q a prime, this bound is due to Artin ( Art24], x24, Formula (8)), whose arguments are easily extended to the general case replacing the Artin character by the general quadratic character. Given a divisor div(a 0 ; b 0 ), the canonical reduced representative in its class can be computed in time polynomial in N 0 . The set P S can be constructed by enumerating all irreducible polynomials p 2 F q X] of degree at most S and solving the equation y 2 p + hy p f 0 (mod p) in expected polynomial time by a probabilistic algorithm. All further steps are completely analogous to the case of imaginary quadratic number elds. The only di erence is that testing for smoothness and decomposing a group element into primes is reduced to the corresponding problems over the univariate polynomials instead of the rational integers.

For deg f = 2g + 2, the prime at in nity is splitting and H is called a real representation of the curve. Its Jacobian is no longer isomorphic to the ideal class group of F q X; Y ]=(H).

Instead of working in the Jacobian, it has been suggested to base cryptosystems on discrete logarithms in the so called infrastructure of the curve SSW96, MVZ98]. It has been observed in PR99] that at least in odd characteristic a constant eld extension of degree at most 2g +2 allows to transform a real into an equivalent imaginary representation. Thus we restrict our presentation to imaginary curves.

Algorithm

We describe the algorithm for a cyclic group whose order is known and not necessarily prime. Unlike in the Pohlig{Hellman method we do not split the discrete logarithm problem into a series of problems in subgroups of prime order. In fact, we need to work in the full group to guarantee a provable proportion of smooth elements, and the generalisation of the algorithm to subgroups poses challenges which are discussed in Section 7. However, we factor the group order to facilitate the linear algebra step.

The algorithm takes as input a generator g 1 of a cyclic group G of order N and another element g 2 2 G. It outputs log g 1 g 2 , i.e. an integer l 2 f0; : : : ; N 1g such that g 2 = lg 1 .

1) Choose a smoothness bound S and construct the factor base P S = fp 1 ; : : : ; p n g with n = n S . Set k = dlog 2 n + log 2 log 2 Ne + 1.

2) Construct a matrix A = (a ij ) 2 Z n (2kn) N as follows: For j = 1; : : : ; kn, select randomly and uniformly j , j 2 Z N until j g 1 + j g 2 is S{smooth, and write j g 1 + j g 2 = n X i=1 a ij p i :

(1)

For j = kn + 1; : : : ; 2kn, write j = (k + l)n + m with 0 l k 1, 1 m n, and select randomly and uniformly j , j 2 Z N until j g 1 + j g 2 p m is S{smooth; then write

j g 1 + j g 2 = p m + n X i=1 b ij p i = n X i=1
a ij p i :

(2) (In practice, one would only create a few more than n columns of the rst type, see Gau99].

The second type of columns and the constant k are merely needed to make a rigorous proof of the running time possible.) 3) By the randomised procedure described in Section 4, try to nd a non-zero vector = ( 1 ; : : : ; 2kn ) 2 Ker(A). (During this step N is factored.) If the procedure fails, return to 2). 4) If P 2kn j=1 j j is invertible in Z N , then output P 2kn j=1 j j 1 P 2kn j=1 j j ; otherwise return to 2).

If the algorithm halts in

Step 4), then it outputs the correct discrete logarithm of g 2 to the base g 1 . The fact that 2 Ker(A) means that 0 = 2kn X j=1 a ij j 8i = 1; : : : ; n; multiplying these equations by p i and summing them up yields

0 = 2kn X j=1 n X i=1 a ij p i ! j = 0 @ 2kn X j=1 j j 1 A g 1 + 0 @ 2kn X j=1 j j 1 A g 2 :
As g 1 and g 2 are both of N{torsion, multiplying by the inverse of P 2kn j=1 j j in Z N , if it exists,

shows the correctness of the result.

Linear algebra

As rank A n, it is possible to nd a non-zero vector 2 Ker(A). How this is done, however, needs further explication. On one hand, it is desirable to exploit the sparse structure of the matrix, which has only O (1) entries per column, and the corresponding algorithms are prone to failure with a certain probability. On the other hand, a complication is introduced by the fact that N need not be prime, so that Z N may not be a eld.

To exploit the matrix sparseness, one may use a randomised Lanczos algorithm; we rely on the following trivial corollary of Theorem 6.2 in EK97].

Theorem 2 Let F q be the nite eld with q elements and let A 2 F n d q be a matrix of rank r with ! non-zero entries and b 2 F n q . There is a probabilistic algorithm which either returns a vector x 2 F d q such that Ax = b or reports failure. The algorithm requires O(r(! + d)) operations in F q and has a failure probability of at most 11d 2 d 2(q 1) . Moreover, the solution vector returned by the algorithm can be made to vary uniformly over all possible solutions by randomising the right hand side in the following way (in fact, this randomisation is already part of the algorithm in EK97]): Choose y 2 F d q according to a uniform distribution, solve Ax = b + Ay and let x = x y. If y varied over a xed class of F d q = Ker A, then x would not depend on y, and x would be distributed uniformly over the solution space x + Ker A of the equation. Hence, the same assertion holds when y does not belong to a xed class. When q is small compared to d, it is not possible to apply the theorem directly. Instead, one may switch to a eld extension. While this idea does not seem to be new | it was used, for instance, in the implementation of LO90], see also KS91] | we did not nd it detailed in the literature and thus expand on the topic. In particular, it is possible to maintain the uniform distribution over the solution vectors. In the situation of Theorem 2, let p be the characteristic of F q , = minfl : q l > 11d 2 ; plg and q 0 = q . Then q 2 11d 2 , so that q 0 2 O(d 2 q 2 ). We would like to solve a matrix equation over F q 0 and project the solution onto a solution x 2 F d q of Ax = b. For projection, one may use the trace function Tr : F q 0 ! F q , which is a homomorphism of F q -vector spaces and acts on F q as multiplication by . Let b 0 = 0 b 2 F d q with 0 1 (mod p), so that b 0 = b. The value 0 exists because gcd( ; p) = 1 and can be computed by the extended Euclidean algorithm in time O(log log p), which as well as the multiplication of b by 0 is negligible compared to the following linear algebra step. Solve Ax 0 = b 0 by the algorithm in EK97]. The success probability for this step is at least 1 11d 2 d 2(q 0 1) 1 2 . Let x = Tr(x 0 ). Then from the linearity of the trace we deduce that Ax = Tr(Ax 0 ) = Tr(b 0 ) = b 0 = b. Moreover, any solution x 2 F d q of Ax = b can be obtained in this way, and all of them have the same probability of occurring. Namely, for a given solution x, the set of solutions to Ax 0 = b 0 over F d q 0 which map to x under the trace function is given by 0 x + (Ker A \ Ker Tr), whose cardinality (q 0 ) dim(Ker A\Ker Tr) is independent of

x. Thus, we have shown the following result:

Theorem 3 Let A 2 F n d q be a matrix of rank r with ! non-zero entries and b 2 F n q . There is a probabilistic algorithm which either returns a vector x 2 F d q such that Ax = b or reports failure.

The running time of the algorithm is in O(r(! + d) log 2 (dq)), and its failure probability is at most 1 2 . Moreover, the resulting vector is uniformly distributed over all possible solutions. This solves the linear algebra step if N is prime. Otherwise, one factors N, computes modulo p for all p kN and combines the results by the Chinese Remainder Theorem. The computations modulo p may be broken up into iterations modulo p via a lifting procedure: Suppose that a non-zero solution 1 2 f0; : : : ; p e 1g 2kn is known to the equation Ax 0 (mod p e ), for instance A 1 = p e with 2 Z 2kn . Assume that there is a solution 2 of Ax (mod p). Then p e 2 1 is a non-zero solution of Ax 0 (mod p e+1 ). If all computations modulo a prime return a random vector according to a uniform distribution over all possible solutions, then the combined result varies uniformly over the kernel of A. Considering the elementary divisor form of the matrix A, however, it is easily seen that the lifting procedure may fail if (and only if) rank Q A 6 = rank Zp A because then the matrix equation Ax (mod p) need not have a solution. This is the reason why, following Pom87], we create the matrix A in a special way, generating many more than the n + 1 columns one would expect to need in practice and introducing the canonical basis elements p m into the matrix. Indeed, it is proved in Lemma 4.1 and the subsequent remark of Pom87] that with high probability the matrix has full rank over Z p . We recall this lemma with our notations.

Lemma 4 Let V be a vector space over a eld F with dim V = n < 1. Let S be a nite set of vectors in V and b 1 ; : : : ; b n a basis for V . Let k 2 N . We make 2kn independent choices of elements from S with an arbitrary probability distribution over S, labelling the chosen vectors v 1 ; : : : ; v kn ; w 1 ; : : : ; w kn , and we denote by V 0 the subspace of V spanned by v 1 ; : : : ; v kn , and the vectors b j + w (j 1)k+i for j = 1; : : : ; n and i = 1; : : : ; k. Then with probability at least 1 n 2 k 1 we have V = V 0 .

In our case, the vector space V is the space of column vectors of size n with coe cients in Z p , the basis is the canonical basis, and the set S is the set of all column vectors representing a smooth element of G. We see that the vectors generating V 0 correspond precisely to the vectors forming the matrix A. Hence the probability that the lifting is possible on Z p is at least 1 n 2 k 1 . There are at most log 2 N 2 distinct primes p whose squares divide N, thus the probability that the lifting is possible for all of them is at least 1 nlog 2 N 2 k 1 2 for our choice of k. In this case, repeating log 2 (2log 2 N) times the algorithm of Theorem 3, we obtain a solution of one problem modulo a prime with probability at least 1 1 2 log 2 (2log 2 N) = 1 1 2log 2 N . As at most log 2 N single problems have to be solved, we get a solution modulo N with probability at least 1 2 . Altogether, Step 3) is thus successful with a probability of at least 1 4 , in which case the output vector is uniformly distributed over the kernel.

Success probability and running time

To estimate the success probability of the algorithm during one run of Steps 2) to 4), we assume that Step 2) has been accomplished successfully, the study of this step being postponed to the running time analysis below. As shown above, Step 3) succeeds with probability at least 1 4 . The algorithm may also fail if P 2kn j=1 j j is not invertible in Z N in Step 4). However, this happens with a su ciently low proba- bility. For given j kn and any j , as g 1 is a generator of G and j is uniformly distributed, the element j g 1 + j g 2 is uniformly distributed over all group elements. The same holds for j > kn and j g 1 + j g 2 p m . Consequently, the matrix A and the vector are independent random variables, so that and are also independent. Let p be a prime divisor of N. As is uniformly distributed over all vectors of the kernel, the probability that 6 0 (mod p) is at least 1 1 p . Then the orthogonal space of mod p in Z 2kn has dimension 2kn 1, and the conditional probability that mod p is not orthogonal to mod p is at least 1 1 p . Hence P 2kn j=1 j j is invertible in Z N with probability at least Q pjN 1 1 p 2 = '(N) N 2 . From (3.41) in RS62] we have '(N) N 2 (1= log log N).

Thus, the total success probability for one run of Steps 2) to 4) is in 1 (log log N) 2 :

In accordance with Section 2, denote by n 0 = n 0 S the number of elements of the monoid M whose sizes are bounded above by S. With the assumptions set forth in Section 2, P S can be constructed in time O (n 0 2 ). Denote by N S the number of S{smooth elements of G, and let t s and t d be upper bounds on the expected time needed for a smoothness test and the decomposition of a smooth group element into a sum of primes, respectively. The time needed for computing one linear combination of g 1 and g 2 and testing for smoothness is in O (t s ); this has to be repeated an expected N N S times until a smooth element is obtained. This smooth element is recognised with a probability of at least 1=2, so that no more than two repetitions of the previous procedure are needed on average until a column of the matrix can be lled. (3) (In all cases under consideration, n and n 0 di er only by polynomial factors in log N 0 , i.e. O (n) = O (n 0 ), so that we do not lose anything when replacing n by n 0 .)

Examples.

1. G = F p , p prime With deterministic algorithms due to Pollard and Strassen Pol74, Str76] we have t s 2 O ( p n 0 ). A more e cient probabilistic method has been proved using hyperelliptic curves.

The test of LPP93] recognises (and decomposes) a smooth number with probability at least 1=2 in time t s 2 O (L n 0(2=3; c)), where L is the subexponential function as de ned in Sec- tion 6 and c some positive constant. Thus, the total running time is in

O t f + n 0 2 + n 0 L n 0(2=3; c) N N S : 2. G = F 2 k
Now t s 2 O (1), as a smoothness test can be performed in deterministic polynomial time by computing the distinct degree factorisation of the polynomial representing the group element.

Precisely, let f 2 F 2 X] 0 be the element to be tested, and g = f gcd(f;f 0 ) its square-free part.

Then f is S{smooth if and only if g is. As X 2 i X is the product of all irreducible polynomials of degree dividing i in F 2 X] 0 , the latter is the case if and only if g = lcm n gcd(g; X 2 i X) : i = 1; : : : ; S o : Computing X 2 i X mod g by successive squaring and reduction modulo g, this can be tested in time polynomial in S and deg f 2 O(log N). Thus, the total running time of the algorithm is in O t f + n 0 2 + n 0 N N S :

3. G = F p k , p prime An element (m; f) 2 N F p X] 0 is S{smooth if and only if m and f are S{smooth. The smoothness of m can be tested in time in O (L p (2=3; c)) as mentioned in Example 1. The smoothness of f can again be checked by distinct degree factorisation in time O (1). Thus, the total running time of the algorithm is in O t f + n 0 2 + n 0 L p (2=3; c) N N S :

4. Class groups of imaginary quadratic number elds As the smoothness test and the decomposition into primes are reduced to the case of natural integers, the analysis of Example 1. shows that the running time is in O t f + n 0 2 + n 0 L n 0(2=3; c) N N S :

5. Jacobians of hyperelliptic curves Now the smoothness test and the decomposition are reduced to the case of monic polynomials, and the analysis of Example 2. carries over and shows that the running time is in O t f + n 0 2 + n 0 N N S :

6 Subexponentiality

Recall the de nition of the subexponential function with respect to the input size log N 0 and parameters 2 (0; 1) and c > 0:

L N 0( ; c) = e c(log N 0 ) (log log N 0 ) 1 :

The smaller , the closer this function is to the polynomial L N 0(0; dce) = (log N 0 ) dce in log N 0 . All rigorously proven subexponential algorithms for discrete logarithms, and also the algorithm of this article, have = 1=2. Thus we simplify the notation by omitting the rst parameter when it is 1=2. We state the simple relations L N 0(c 1 ) L N 0(c 2 ) = L N 0(c 1 + c 2 ) and L N 0(c 1 ) + L N 0(c 2 ) 2 (L N 0(max(c 1 ; c 2 ))):

Furthermore, functions in O (1) or O(L N 0( ; c)) for < 1=2 are in L N 0(o(1)), where o(1) stands for the set of real valued functions tending to zero as N 0 ! 1.

Assume that we have a smoothness result of the following form:

The bound S can be chosen such that n 0 2 O(L N 0( + o(1)))

and

N N S 2 O(L N 0( + o(1)))
for some constants , > 0.

The assumption N 2 O (N 0 ) implies that L N (c) 2 O(L N 0(c) + o(1)). Taking into account that N can be factored in expected time in O(L N (1+o(1))) O(L N 0(1+o(1))) by the algorithm presented in LP92] and introducing an exponent such that t s 2 O (n 0 ), we can specialise (3) to obtain O (L N 0 (max(1; 2 ; (1 + ) + ) + o(1))) :

In fact, the constants for all examples presented below are worse than 1 anyway, so that the need for factoring N has no in uence on our running time bounds.

Examples.

1. G = F p , p prime; N 0 = N = p 1 With the usual notation (x; y) for the number of integers between 1 and x all prime factors of which are not larger than y, we have N This is precisely the complexity of the fastest known algorithm described in Pom87].

2. G = F 2 k ; N 0 = N = 2 k 1 Denote by N q (d; m) the number of monic polynomials of degree d over F q all prime factors of which have degree at most m. Then N N S 2 k N 2 (k 1;S) . Let S = dlog(L N ( ))e, so that n 0 2 (L N ( )). Theorem 2.1 in BP98] shows that N 2 (k 1; S) 2 2 k 1 u (1+o(1))u for u = k 1 S 1 q log N log log N 1 p log N. Thus, a few computations reveal that N N S 2 O(L N ( + o(1))) for = 1 2 , and the running time of the algorithm is in O L N max 2 ; + 1 2 ; 1 + o(1) for any > 0. The optimal choice = 1= p k 1 is exponential in N. If S 1, then all p monic linear polynomials are contained in the factor base, which is thus of exponential size. Hence, we must restrict our attention to instances in which p is su ciently small compared to k. The optimal choice for is o(1))) of the algorithm described in HM89] for determining the class group structure without any previous information.

Jacobians of hyperelliptic curves

Recall that N 0 = q g . Letting S = dlog q L q g ( )e, we have n 2qL q g ( ). Again, we follow Eng99] and consider only instances with g # log q for some positive constant #, so that q L q g 1 p # . It is shown in ES00] that then N S q g L q g 1 2 , so that N !!

in Eng99], and asymptotically for # ! 1 (e.g., for q constant), the constant of the subexponential function is again the same as in Example 2. Hence, our algorithm shows that cryptosystems based on high-genus hyperelliptic Jacobians are signi cantly weaker than expected so far, in particular they o er no security gain when compared to cryptosystems in nite elds of comparable size.

7 Cyclic subgroups Unlike nite elds, many groups of cryptographic interest do not have a cyclic structure. For instance the number of cyclic factors of hyperelliptic Jacobians can be up to twice as large as the genus. Hence it is an important task to compute discrete logarithms in a cyclic subgroup H = hg 1 i of a given abelian group G. From a heuristic point of view, this does not pose any problems:

The algorithm in its formulation of Section 3 remains applicable. With the usual assumption that smoothness and membership in a subgroup are independent concepts, i.e. the proportion of smooth elements is the same in H as in G, the running time analysis carries over from the group to its subgroup. However, we are concerned with provable running times in this article, and the smoothness results presented so far apply exclusively to the full groups under consideration. In this section, we discuss a few approaches to deal with this situation.

Perturbing with elements of the complement

The simplest situation arises when gcd jHj; jGj jHj = 1; then H admits a complement H 0 in G, i.e., G = H H 0 . Assume that it is possible to select independently elements h j of H 0 according to a uniform distribution in time polynomial in log N 0 . This is for instance the case if we can select random elements in G, because multiplying a uniformly distributed element of G by jGj jHj yields a uniformly distributed element of H 0 . Another favourable situation is the case where we know a basis of H 0 . (In this context, we understand by a basis of H 0 a set fb 1 ; : : : ; b r g such that H 0 is equal to the direct sum hb 1 i hb r i. The cardinality r of a basis is not an invariant of H 0 , but it is bounded above by log 2 jH 0 j.) Then j g 1 + j g 2 +h j is uniformly and independently of distributed over G, so that the algorithm may be carried out with these group elements instead of j g 1 + j g 2 . If it is successful, then 0 @ 2kn X j=1 j j

1 A g 1 + 0 @ 2kn X j=1 j j 1 A g 2 = 2kn X j=1 j h j 2 H \ H 0 = f0g; so that log g 1 g 2 = 0 @ 2kn X j=1 j j 1 A 1 0 @ 2kn X j=1 j j 1 A
as before. Also, the running time analysis remains unchanged. While this situation seems to be very special, it is typical for cryptographic applications in which H is supposed to have large prime order and the cofactor jGj jHj is small, so that jHj and jGj jHj are automatically coprime. Moreover, for jGj jHj polynomial in log N 0 , the structure and, in particular, a basis of H 0 ' G=H can be determined in polynomial time (see, for instance, Coh93]), and the assumptions of this subsection are satis ed.

Using a basis for G

Assume that a basis fb 1 ; : : : ; b r g of G along with the orders e 1 ; : : : ; e r of its elements are known.

Then the discrete logarithm problem can be solved in two steps. Instead of directly writing g 2 as a multiple of g 1 we rst express g 1 as a linear combination of the basis elements and then proceed in the same way for g 2 . The discrete logarithm can be computed by a few operations modulo the e i . In order to write g 1 in terms of the b i , a slight variation of the algorithm allows to use the smoothness properties. For given j kn, pick random elements ij and j until P ij b i + j g 1 is S{smooth and write this element as P a ij p i . Similarly, for j > kn pick random elements until P ij b i + j g 1 p m is S{smooth. Here again, the elements of G which are tested for smoothness are distributed uniformly and independently of , so that the same analysis as in Section 5 can be carried out.

Hence with high probability a non-zero vector of the kernel is obtained and g 1 is expressed as a linear combination g 1 = P i b i . The same process yields g 2 = P i b i . Now try to solve the system of modular equations i l i (mod e i ). If this is possible, then l is the correct discrete logarithm of g 2 with respect to g 1 . Otherwise, g 2 does not lie in the cyclic subgroup generated by g 1 . In this case, which does not occur in the cryptographic setting, the original algorithm of Section 3 would run forever without giving proof of the non-existence of the discrete logarithm. Thus, the ability to detect this case is an additional advantage of the modi ed algorithm.

Conclusions

We have presented a generic probabilistic algorithm for computing discrete logarithm in cyclic groups of known order in which a notion of smoothness is available. Many groups suggested for cryptosystems t into this context. The running time of the algorithm can be analysed rigorously without any heuristic assumptions. The analysis leads to a subexponential complexity as soon as a certain smoothness assumption is veri ed. In particular, we recover the running time bounds of the fastest algorithms with proven complexity for nite elds and obtain substantial improvements over the previously known algorithms for class groups. This theoretical result is backed by a recent implementation of the algorithm for hyperelliptic Jacobians, which shows that even curves of a rather small genus are insecure in a cryptographic context Gau99]. When examining subexponential algorithms, it is common to distinguish between ine cient methods with a provable running time and practical methods with a conjectured running time. Our algorithm breaks with this tradition. It is the fastest known algorithm for the discrete logarithm problem in hyperelliptic Jacobians both in theory and in practice. In fact, the implementation of Gau99] was the starting point of our study, and while the modi cations described in this article are necessary to prove the running time, they do not alter the nature of the algorithm fundamentally. In general, the groups we are concerned with are not cyclic, but we have shown that suitable modi cations allow to apply the algorithm to a wide class of non-cyclic groups, preserving the subexponential running time. Among these are all groups of cryptographic interest. In particular, the analysis of the algorithm remains valid when a basis of G is known. It is thus an interesting question whether a basis can be built if only the group order and its factorisation are known. In the case that the order is square-free, an obvious probabilistic method constructs a basis. If the primes which occur with multiplicity are of polynomial size, they can be dealt with by an exhaustive construction. Considering the remaining case of a power of a large prime, it seems plausible that the notion of smoothness available in the group should allow to construct a probabilistic algorithm for determining the basis.

N

  2 S ) . Let S = dlog(L N ( ))e, so that n 0 = 2 S 2 L N ( ); 2L N ( )]. Then Lemma 3.1 in Pom87] shows that N N S 2 O(L N ( + o(1))) with = 1 2 . Moreover from n 0 2 O(L N ( )) we deduce L n 0(2=3; c) 2 L N (o(1)). The running time of the algorithm is thus in O L N max 2 ;

  p 2 again yields a running time in O(L N ( p 2 + o(1))); which corresponds to the fastest known algorithms described in Pom87] and BP98].

  3. G = F p k , p prime; N 0 = N = p k 1 Notice rst that in the polynomial representation we have chosen, it is impossible to obtain a subexponential running time for xed k 2 and p ! 1. If we let S = 0, then only the constants have a chance of being smooth, and N

  Letting S = dlog p (L N ( ))e, we obtain the estimate as in Example 2, which introduces an unwanted factor of p. Moreover, since we have to round up S, it need not be true any more that n 0 2 O(L N ( )). In fact, 0 p X] : deg f = ig jfm 2 f1; : : : ; p 1g : log 2 m S igj N ( )):For a rst special result we consider the case p 2 O(log N) or more generally p 2 O (1), which implies n 0 2 O (L N ( )) and L p (2=3; c) 2 L N (o(1)). So the running time analysis of Example 2. carries over without modi cation.More generally, we must ensure that p is subexponential in log N = k log p. Following the ideas in Eng99], we consider the case k # log p for some positive constant #, in which p (1) for the same value of S as above, L p (2=3; c) 2 L N (o(1)) and the total running time is in O

  for # ! 1 (e.g., for p xed), we recover the running time of Example 2.In AD93], Adleman and DeMarrais describe an algorithm with conjectured subexponential running time for p > k. They represent the eld as the ring of integers of a number eld modulo a prime ideal. See also Sem95]. It is an interesting open question whether there is a provably subexponential algorithm for all nite elds using possibly such a representation. 4. Class groups of imaginary quadratic number elds Let D denote the discriminant of the number eld. It is shown in Sey87], Proposition 4.4, that assuming the generalised Riemann hypothesis, N N S 2 O L jDj 1 4c + o(1) for S = dlog L jDj (c)e. Due to a theorem of Siegel's Sie36], log jDj 2 (2 + o(1)) log N so that L jDj (c + o(1)) = L N ( p 2c + o(1)). Letting S = dlog L N ( )e, we deduce n 2 O(L N ( )) and N N S 2 O L N 1 2 + o(1) . Repeating the analysis of Example 1 shows that our algorithm has a running time in O L N p 2 + o(1) = O L jDj (1 + o(1)) under the generalised Riemann hypothesis. This improves the running time of O(L jDj ( p 2 +

N

  as that of Example 3. shows that the optimal choice of is minf ; (#)g = min

  So the total time used in Step 2) is in

	O n N N S	t s + t d	O n N N S	t s + n 2
	as 2kn, t d 2 O (n).
	Let t f be a time bound for factoring N. As explained in Section 4, log 2 (2log 2 N)log 2 N 2 O (1) executions of the algorithm behind Theorem 3 are required for Step 3). The number of entries in each column of A is in O (1), so that Step 3) needs time in O (t f + n 2 ).
	Finally, Step 4) can be performed in O (n).
	As only O((log log N) 2 ) O (1) repetitions of Steps 2) to 4) are needed on average and n n 0 , the total running time of the algorithm is in
	O t f + n 0 2 + n 0 N N S	t s :

Acknowledgements

The results of this paper form part of the authors' doctoral theses; we thank our respective supervisors, Dieter Jungnickel and Fran cois Morain, for their continuous support and useful suggestions.