MATHEMATICSOFCOMPUTATION Volume66,Number220,October1997,Pages1663–1687 S0025-5718(97)00880-6 ON SOME COMPUTATIONAL PROBLEMS IN FINITE ABELIAN GROUPS JOHANNES BUCHMANN, MICHAEL J. JACOBSON, JR., AND EDLYN TESKE Abstract. Wepresentnewalgorithmsforcomputingordersofelements,dis- crete logarithms, and structures of (cid:12)nite abelian groups. We estimate the computational complexity and storage requirements, and we explicitly deter- mine the O-constants and Ω-constants. We implemented the algorithms for class groups of imaginary quadratic orders and present a selection of our ex- perimentalresults. Our algorithms are based on a modi(cid:12)cation of Shanks’ baby-step giant- step strategy, and have the advantage that their computational complexity and storage requirements are relative to the actual order, discrete logarithm, orsizeofthegroup,ratherthanrelativetoanupperboundonthegrouporder. 1. Introduction Let G be a (cid:12)nite abelian group, written multiplicatively, in which we assume that the following are possible: (cid:15) for a,b2G we can compute c=a(cid:3)b (cid:15) for a2G we can compute a−1 (cid:15) for a,b2G we can test whether a=b We call these the group operations. Note that from every group element a we can determine the neutral element 1 = a(cid:3)a−1. As an example, we will consider class groupsofimaginaryquadratic(cid:12)elds. Anotherexampleisthe groupofpoints onan elliptic curve over a (cid:12)nite (cid:12)eld. For any subset S of G, denote by hSi the subgroup of G generated by S. If hSi=G, then S is called a generating set of G. If S =fgg, then write hgi instead of hSi. Three common computational problems in such groups are: (cid:15) Given g 2G compute jhgij, the order of g in G, i.e., the least positive integer x such that gx =1. (cid:15) Given g,d 2 G decide whether d belongs to the cyclic subgroup hgi of G generated by g. If d2hgi, (cid:12)nd log d, the discrete logarithm of d to the base g g, i.e., the least non-negative integer x such that gx =d. (cid:15) Given a generating set of G compute the structure of G. By computing the structureofGwemeancomputingpositiveintegersm1,... ,mk withm1 >1, ReceivedbytheeditorApril1,1996and,inrevisedform,July19,1996. 1991 Mathematics Subject Classi(cid:12)cation. Primary11Y16. Thesecondauthor was supportedbytheNaturalSciences andEngineeringResearchCouncil ofCanada. ThethirdauthorwassupportedbytheDeutscheForschungsgemeinschaft. (cid:13)c1997 American Mathematical Society 1663 1664 JOHANNES BUCHMANN, MICHAEL J. JACOBSON, JR., AND EDLYN TESKE mijmi+1,1(cid:20)i<k,andanisomorphismφ:G!Z/m1Z(cid:2)(cid:1)(cid:1)(cid:1)(cid:2)Z/mkZ.This isomorphism is given in terms of the images of the generators. The integers m are the uniquely determined invariants of G. i In this paper we present improved versions of Shanks’ algorithms for solving these problems. As in Shanks’ original method [10] (see also [4], [8]), operations in G and table look-ups are used in our algorithms. The table entries are pairs (Sz,z), whereQS isasetofgroupelements,z belongstothesetZS ofallmapsS −!Z,and Sz = gz(g). When we estimate the complexity of our algorithms, we count g2S the number of group operations, the number of table look-ups, and we determine bounds on the table sizes, i.e., the number of group elements which have to be stored. We ignore the time and space for doing index calculations. If hashing on thegroupelementsispossible,thetablesofgroupelementsarehashtablesandthe timeforonetablelook-upiscomparabletothetimerequiredforagroupoperation. Here are our main results. Theorem 1.1. There is an algorithm for computing the order x of an element g 2G which executes one inversion and at most (cid:24) p (cid:25) (cid:6)p (cid:7) x 4 x + log 2 multiplications in G. It uses a table of at most (cid:6)p (cid:7) 2 x p pairs (g,r) 2 G(cid:2)f1,... ,2d xeg. The total number of table look-ups is bounded by (cid:6)p (cid:7) 2 x . Theorem 1.2. There is an algorithm that decides for g,d 2 G, d 6= 1, whether d2hgi and if so computes log d. Let g (cid:26) jhgij if d62hgi, x= log d if d2hgi. g The algorithm executes at most (cid:6)p (cid:7) (cid:6) p (cid:7) 6 x + log x multiplications in G. It uses a table of at most (cid:6)p (cid:7) 2 x p pairs (g,r) 2 G(cid:2)f1,... ,2d xeg. The total number of table look-ups is bounded by (cid:6)p (cid:7) 4 x . Our algorithm for computing the structure of G may behave di(cid:11)erently if the generators are input in di(cid:11)erent orders. Therefore, the algorithm receives as input agenerating sequence,i.e.,a(cid:12)nitesequenceS =(g1,... ,gl)ofgroupelementssuch that fg1,... ,glg is a generating set of G. Set (1) Gj =hg1,... ,gji, 0(cid:20)j (cid:20)l, and (2) l(S)=jfj 2f1,... ,lg : Gj−1 6=Gjgj. ON SOME COMPUTATIONAL PROBLEMS IN FINITE ABELIAN GROUPS 1665 In other words, if we generate G by using g1,g2,g3,..., l(S) is the number of generators which enlarge the group. Note that l(S) is at least as large as the number of invariants of G. We will prove the following result. Theorem 1.3. There is an algorithm that computes the structure of G from a generating sequence S of G which executes jSj inversions and at most p p 2l(2S)(jSj+5) jGj+4l(S) jGj+logjGj multiplications in G, with l(S) from (2). It uses two tables of at most p p 2l(2S) jGj and 2l(2S)+1 jGj p pairs (g,(cid:126)q)2G(cid:2)f0,... ,2 jGjgjSj. The total number of table look-ups is bounded by p 2l(2S)(jSj+l(S)+2) jGj. The upper bound for the complexity of the group structure algorithm is expo- nentialinthenumberl(S)ofgeneratorsthatarereallyusedtodeterminethepgroup structure. If that number is (cid:12)xed, the complexity of the algorithm is O(jSj jGj). On the other hand, our analysis shows that if G=(Z/2Z)l for some positive integer l, the complexity of our algorithm is Ω(jGj), where the symbolΩ(f(n))standsforthesetofallfunctionsgsuchthatthereexistsaconstant M with jg(n)j (cid:21) Mjf(n)j for all large n. This lower bound also holds for Shanks’ original algorithm and its variations. Hence, for (cid:12)nite abelian groups with a large number of small invariants our algorithm is not appropriate. The basic idea ofthis paper is to use baby-stepgiant-stepalgorithmswith some initial step-width v 22N and to double that step-width as long as the resultof the computationhasnotbeenfound. Asimilarideahasbeenusedin[2]buttheresults obtained there are weaker than ours. For v = 2 we obtain the above theorems. If v is chosen such that L = v2 is an upper bound on the groupporder, we obtain Shanks’ original algorithms. Our analysis shows that for v = L the number of mupltiplications and the table size in the order and discrete logarithm algorithms is Ω( L). Also,forthatchoiceofvthenumberpofmultiplicationsandthetablesizein the group structure algorithm is Ω(2l(S)/2jSj jLj). Thus, if the upper bound L is muchlargerthantheactualorder,discretelogarithmorgrouporder,thealgorithm wastes a lot of time and space. We implemented our algorithms for class groups of imaginary quadratic orders using the computer algebra system LiDIA [7]. We present experimental results which yield good choices for the initial step-width v for these groups. Thepaperisorganizedasfollows. InSection2wedescribeandanalyzetheorder algorithm. That section also contains the basic idea of the paper. In Section 3 we discuss the algorithm for computing discrete logarithms, and Section 4 is devoted to the group structure algorithm. 1666 JOHANNES BUCHMANN, MICHAEL J. JACOBSON, JR., AND EDLYN TESKE 2. Computing the order of an element Givenanelementg 2Gwe wishto computex=jhgij. Ourimprovedalgorithm, a modi(cid:12)cation of Shanks’ baby-step giant-step method, is based on the following statement: Lemma 2.1. Let v be an even positive integer. For every positive integer x there are uniquely determined integers k, q and r with k (cid:21) 0, b4k−1cv2 (cid:20) 2kvq < 4kv2 and 1(cid:20)r (cid:20)2kv such that x=y+r, y =2kvq. Proof. Let x 2 N. We (cid:12)rst show the existence of such k, q and r. We choose k such that b4k−1cv2 < x (cid:20) 4kv2, and write x = 2kvq+r with 1 (cid:20) r (cid:20) 2kv. Then b4k−1cv2−2kv < 2kvq (cid:20) 4kv2−1, which implies that 2kvq < 4kv2. Moreover, if k =0, we have −v <vq, so 0(cid:20)vq. If k (cid:21)1, we have 4k−1v2−2kv <2kvq; hence 2k−1(v/2)−1 < q. Since v/2 is integral, this implies that 2k−1(v/2) (cid:20) q, so that 4k−1v2 (cid:20)2kvq. To show the uniqueness of this representation, let x = 2kvq+r with k, q and r as stated above. Then b4k−1cv2 (cid:20) 2kvq < 4kv2, which implies q (cid:20) 2kv−1, so that x = 2kvq+r (cid:20) 2kv(2kv−1)+2kv = 4kv2. Moreover, we have b4k−1cv2 < 2kvq+r =x. These inequalities determine k uniquely. The uniqueness of q and r is due to the uniqueness statement for division with remainder. We explain the method for computing x = jhgij. We select an even positive integer v which is used as the initial step-width in the algorithm. Then there is a unique non-negative integer k such that x belongs to the interval I =fb4k−1cv2+1,... ,4kv2g. k We search those intervals for k = 0,1,2,... until x is found. By Lemma 2.1, each numberinI canbewrittenasy+rwithy =2kvqandr,qasstatedinLemma2.1. k Also, each integer that can be written in this way belongs to the interval I . To k check whether x is in I we test whether gy+r = 1 with y = 2kvq and r and q as k stated in Lemma 2.1. This means that we test whether gy =g−r, 1(cid:20)r(cid:20)2kv, y =2kvq, b4k−1cv2 (cid:20)y <4kv2. For this purpose, we compute the set R =f(g−r,r):1(cid:20)r(cid:20)2kvg, k andforallvaluesofq suchthatb4k−1cv2 (cid:20)y <4kv2 wecheckwhetherthereexists (gy,r) 2 R for some r. If so, jhgij = y +r. Otherwise, we increase k by 1. If k x (cid:20) v, the set R0 contains at least one pair (1,r), and jhgij = r for the smallest such r. Therefore, before adding a pair (g−r,r), 1 (cid:20) r (cid:20) v, to R0 in the course of the computation of R0, we always check whether g−r = 1, and we break if the answer is \yes", since then jhgij is already found. The e(cid:14)ciency of the algorithm can be improved if we know a lower bound B of jhgij. Writing C = B−1, we then work with the set R = f(g−(r+C),r) : 1 (cid:20) r (cid:20) k 2kvg, and if we (cid:12)nd (gy,r) 2 R , jhgij = y+r+C. If no lower bound for jhgij is k known, we set C =0. We now present the algorithm. ON SOME COMPUTATIONAL PROBLEMS IN FINITE ABELIAN GROUPS 1667 Algorithm 2.2. This algorithm computes the order of the group element g in G. Input: g 2G, lower bound C+1 for jhgij, initial step-width v (v 22N) Output: x=jhgij (1) x=0 (2) s=1; y =v; u=v (3) h=g−1 (4) a=hC; b=gv; c=b /(cid:3) a=g−C−r; (5) R=; b=gy; c=gu (cid:3)/ (6) while (x==0) do (7) for (r =s,s+1... ,u) do /(cid:3) new baby steps (cid:3)/ (8) a=a(cid:3)h (9) if ( s==1 ) then /(cid:3) check if 1(cid:20)x(cid:20)v (cid:3)/ (10) if (a==1 ) then (11) x=r+C (12) return (x) (13) break while (14) else (15) R=R[f(a,r)g (16) fi (17) else (18) R=R[f(a,r)g (19) fi (20) od (21) while (x==0 and y <u2) do /(cid:3) giant steps (cid:3)/ (22) if (there is a number r such that (b,r)2R ) then (23) x=y+r+C (24) return (x) (25) else (26) y =y+u (27) b=b(cid:3)c (28) fi (29) od (30) s=u+1; u=2u /(cid:3) double (31) c=c2 step-width (cid:3)/ (32) od Theorem 2.3. Let C = 0. Let x = jhgij. For every choice of v, Algorithm 2.2 executes one inversion and at most 2blogvc+1 multiplications in G and requires space for three group elements. On further group multiplications, space required, and table look-ups, we have the following estimates. 1668 JOHANNES BUCHMANN, MICHAEL J. JACOBSON, JR., AND EDLYN TESKE 1. If x (cid:20) v, Algorithm 2.2 executes x additional multiplications in G. It uses a table of x−1 pairs (g,r) 2 G(cid:2)f1,... ,x−1g and it performs x equality chepcks. 2. If x(cid:20)v <x, the number M of additional multiplications in G satisfies (cid:6)p (cid:7) v (cid:20)M (cid:20) x +v−2. The algorithm uses a table of v pairs (g,r)2G(cid:2)f1,... ,vg, and it performs v equality checks. The total number TL of table look-ups satisfies (cid:6)p (cid:7) 1(cid:20)TL(cid:20) x −1. p 3. If x>v, the number M of additional multiplications in G satisfies (cid:24) p (cid:25) (cid:24) p (cid:25) 5(cid:6)p (cid:7) x (cid:6)p (cid:7) v x x + log −1(cid:20)M (cid:20)4 x − + log −5. 4 v 2 v p It pperforms v equality checks. It uses aptable of at least d xe and at most 2d xe−2 pairs (g,r)2G(cid:2)f1,... ,2d xeg. The total number TL of table look-ups satisfies p d xe (cid:6)p (cid:7) v (cid:20)TL(cid:20)2 x − −2. 4 2 Proof. For the initialization, Algorithm 2.2 requires one inversion and at most 2blogvc+1 multiplications to compute g−1 and b = c = gv. It must store g−1, b and c. If x (cid:20) v, we (cid:12)nd x = jhgij during the (cid:12)rst iteration of the outer while loop, in the course of the computation of the set R (= R0). This requires x group multipplications and x equality checks, and the set R contains x−1 pairs (g−r,r). If x(cid:20)v <x, we also (cid:12)nd x=jhgij during the (cid:12)rst iterationofthe outer while loop. ThesetRcontainsvpairs(g−r,r),whichalsomeansthatthealgorithmmust performv multiplications inG to compute R. Itperforms v equality checksto test whether g−r = 1. In the iterations of the inner while loop, the algorithm checks whether (gqv,r)2Rpwhile v (cid:20)qv (cid:20)x−r (r 2f1,... ,vg), i.e., 1(cid:20)q (cid:20)(x−1p)/v, so we have 1(cid:20)q < x. It compputes gqv while 2v (cid:20)qv (cid:20)x−r, thups 2(cid:20)q < x. This requiresbetween1 and d xe−1 table look-ups,andatmostd xe−2 group multiplications. Hence,pthe total nupmber of multiplications in the outer while loop is betweenpv and v+d xe−2, if x(cid:20)v <x. Ifv < x,thealgorithmperformskadditionaliterationsoftheouterwhileloop, where (3) 4k−1v2 <x(cid:20)4kv2 l m p p i.e., k −1 < log x (cid:20) k, hence k = log x . After the last iteration, the set v v R contains 2kv pairs (g−r,r). Thus, to compute R the algorithm performs 2kv multiplicaptions in G, and it must store a table of 2kv pairs. From (3) we see that 2k−1v < x(cid:20)2kv, so (cid:6)p (cid:7) (cid:6)p (cid:7) (4) x (cid:20)2kv (cid:20)2 x −2. In the (cid:12)rst inner while loop, the algorithm computes gqv for 2 (cid:20) q (cid:20) v, which requires v−1 multiplications. In all of the following inner while loops except the ON SOME COMPUTATIONAL PROBLEMS IN FINITE ABELIAN GROUPS 1669 last, it computes gq2iv while 4i−1v2 <q2iv (cid:20)4iv2, i.e., v 2i−1 <q (cid:20)2iv, 2 where 1(cid:20)i(cid:20)k−1. This requires v v 2iv−2i−1 =3(cid:1)2i−1 2 2 multiplications in each loop, which can be summed to kX−1 v v 3(cid:1)2i−1 =3(cid:1)(2k−1−1) 2 2 i=1 multiplications. In the last loop, the algorithm computes gq2kv while 4k−1v2 <q2kv (cid:20)x−r, r 2f1,... ,2kvg, p p so 2k−1v <q (cid:20) x−1. Since x(cid:20)2kv, we have x−1 (cid:20) xp−1 < x, and this requires 2 2kv 2kv x at most (cid:6)p (cid:7) v x −1−2k−1 2 multiplications. Thus, the total number of multiplications in the inner while loops is at least v v v v−1+3(cid:1)(2k−1−1) = 3(cid:1)2k−1 − −1 2 2 2 p p (4) 3(cid:6)p (cid:7) x d xe (cid:21) x − −1(cid:21) −1, 4 2 4 and at most v (cid:6)p (cid:7) v v (cid:6)p (cid:7) v−1+3(cid:1)(2k−1−1) + x −1−2k−1 = 2k−1v− + x −2 2 2 2 (4) (cid:6)p (cid:7) v (cid:20) 2 x − −3, 2 p Thpe total number of table look-ups is bounded below by d xe/4 and above by 2d xe−v−2,whichisthemaximumnumberofiterationsoftheinnerwhileloops. 2 Finally, note that in k outer while loops the algorithmperforms one multiplication to compute c2. Together with (4) we get that Algorithm 2.2 performs at least (cid:24) p (cid:25) x 5(cid:6)p (cid:7) log + x −1 v 4 and at most (cid:24) p (cid:25) x (cid:6)p (cid:7) v log +4 x − −5 v 2 p additional multiplications in G to (cid:12)nd jhgij, if v < x. Remark 2.4. ToadaptTheorem2.3tothecaseC (cid:21)1,wejusthavetoreplaceeach xbyx−C andaddtothetotalnumberofgroupmultiplicationsthemultiplications required to compute a=(g−1)C, i.e., at most 2blogCc+1 multiplications. 1670 JOHANNES BUCHMANN, MICHAEL J. JACOBSON, JR., AND EDLYN TESKE In practice, the most e(cid:14)cient way to handle the set R is by means of a hash table. This is possible as long as the group elements are represented as sequences of integers. Then, each look-up in the table R requires just one computation of a hash value and usually one equality test for group elements. As we see from Theorem 2.3, the e(cid:14)ciency of Algorithm 2.2 depends largely on the appropriatechoiceopfthe initialstep-width v. As npotedby Shanks [10],the op- timalchoiceofv is v = jhgij.This results inabout2 jhgij gropupmultiplications in our algorithm. If v is chosen too large (in comparison with jhgij), we waste spaceandtime becausethe setR istoobig. Ifv ischosentoosmall,wewastetime because of superfluous iterations of the outer while loop. In order to test our algorithm,we implemented it using the LiDIA system [7] to computeordersofelementsinidealclassgroupsofimaginaryquadraticorders. For three discriminants of sizes ten, (cid:12)fteen, and twenty decimal digits, we computed the orders of the ideal classes of four prime ideals that we knew from previous computationshaddi(cid:11)erentorders. InTables1,2,and3weshowtheactualnumbers of group multiplications and table look-ups, denoted by GM and TL respectively, that were required to compute the order of each prime ideal class, together with thelowerandupperboundspredictedbyTheorem2.3. (cid:1)denotesthediscriminant of the quadratic orderand I denotes the ideal class of which the prime ideal lying p overtheprimepisthereducedrepresentative. Wecomputetheorderofeachprime ideal class three times, using a di(cid:11)erent value of v eachtime. The simplest version of our algorithm uses v = 2, v = (cid:1)1/4 is equivalent to Shanks’ original algorithm [10], and v = (cid:1)1/4/2 is half-way between the other two and has been shown to yield the best overall run times in our tests. Table 4 gives the run times for these computations on a SPARCstation 20. Table 1. Order algorithm | group multiplications and table look-ups (v =2) Lower Computed Upper ∆ p jhI ij GM TL GM TL GM TL p −4(1010+1) 5 4033 85 16 164 94 258 125 3 16132 166 32 324 189 515 253 13 24198 202 39 485 221 628 309 7 48396 282 55 580 316 884 437 −4(1015+1) 7 2 0 0 4 0 5 0 29 42908 267 52 558 294 836 413 17 128724 456 89 1027 506 1441 715 3 257448 643 127 1278 757 2037 1013 −4(1020+1) 13 232024638 19054 3808 38750 22352 60942 30463 5 464049276 26941 5385 63327 30544 86179 43081 37 928098552 38095 7616 77489 44706 121871 60927 7 1856197104 53870 10771 126642 61090 172348 86165 For(cid:1)=−4(1010+1),ouralgorithmusingv =2isfasterthanShanks’algorithm (i.e. v = (cid:1)1/4) for I5, the class with the smallest order. It is slower for I3 and I13, even though it executes fewer total group operations,because it performs four ON SOME COMPUTATIONAL PROBLEMS IN FINITE ABELIAN GROUPS 1671 Table 2. Order algorithm | group multiplications and table look-ups (v =(cid:1)1/4/2) Lower Computed Upper ∆ p jhI ij GM TL GM TL GM TL p −4(1010+1) 5 4033 224 1 251 18 297 63 3 16132 224 1 305 72 361 127 13 24198 224 1 341 108 389 155 7 48396 224 1 449 216 453 219 −4(1015+1) 7 2 0 0 19 0 19 0 29 42908 3976 1 4002 10 4199 207 17 128724 3976 1 4024 32 4350 358 3 257448 3976 1 4056 64 4499 507 −4(1020+1) 13 232024638 70711 1 74014 3281 85965 15232 5 464049276 70711 1 77295 6562 92274 21541 37 928098552 70711 1 83858 13125 101197 30464 7 1856197104 70711 1 96983 26250 113816 43083 Table 3. Order algorithm | group multiplications and table look-ups (v =(cid:1)1/4) Lower Computed Upper ∆ p jhI ij GM TL GM TL GM TL p −4(1010+1) 5 4033 448 1 467 9 523 63 3 16132 448 1 494 36 587 127 13 24198 448 1 512 54 615 155 7 48396 448 1 566 108 679 219 −4(1015+1) 7 2 0 0 21 0 21 0 29 42908 7953 1 7977 5 8178 207 17 128724 7953 1 7988 16 8329 358 3 257448 7953 1 8004 32 8478 507 −4(1020+1) 13 232024638 141422 1 143086 1640 156678 15232 5 464049276 141422 1 144727 3281 162987 21541 37 928098552 141422 1 148008 6562 171910 30464 7 1856197104 141422 1 154571 13125 184529 43083 times as many giant steps than Shanks’ algorithm, which rpequires additional table look-ups. In the case of I7, the optimal value of v is v = 48396 (cid:25) 220, and the initial step-width v = (cid:1)1/4 (cid:25) 447 that is used in Shanks’ algorithm is su(cid:14)ciently accuratethattheextragiantstepstakenbyouralgorithmcauseittoexecutemore group operations in total. v = (cid:1)1/4/2 (cid:25) 223 is closer to the optimal value than v =(cid:1)1/4, and this choice of v does result in the best overallperformance for three of the four ideals. For (cid:1) = −4(1015 +1), our algorithm using v = 2 is the fastest for three of the four prime ideals. The orders of the ideals are su(cid:14)ciently small that selecting v = (cid:1)1/4 or (cid:1)1/4/2 results in too many extra baby steps. For (cid:1) = −4(1020+1), 1672 JOHANNES BUCHMANN, MICHAEL J. JACOBSON, JR., AND EDLYN TESKE Table 4. Order Algorithm | run times (cid:1) p jhI ij v =2 v =(cid:1)1/4/2 v =(cid:1)1/4 p −4(1010+1) 5 4033 0.19 sec 0.16 sec 0.27 sec 3 16132 0.31 sec 0.22 sec 0.27 sec 13 24198 0.44 sec 0.30 sec 0.37 sec 7 48396 0.60 sec 0.44 sec 0.41 sec −4(1015+1) 7 2 0.13 sec 0.09 sec 0.10 sec 29 42908 0.86 sec 2.83 sec 4.87 sec 17 128724 1.20 sec 2.39 sec 4.60 sec 3 257448 1.74 sec 1.95 sec 3.26 sec −4(1020+1) 13 232024638 61.40 sec 51.80 sec 92.22 sec 5 464049276 81.68 sec 52.72 sec 78.71 sec 37 928098552 128.06 sec 78.76 sec 116.60 sec 7 1856197104 172.86 sec 102.08 sec 111.14 sec ouralgorithmusingv =2isfasterthanShanks’algorithmforoneofthefourideals. In this case, (cid:1)1/4 is closer to the optimal value of v than for (cid:1) = −4(1015+1). Using v =(cid:1)1/4/2, as in the case of (cid:1)=−4(1010+1), actually results in the best overallperformance. Our results suggest that Algorithm 2.2 has two main advantages over Shanks’ original algorithm. The (cid:12)rst and most obvious advantage is that it is faster when theorderoftheelementismuchsmallerthantheorderofthegroup. Inthesecases, Shanks’algorithmexecutestoomanybabysteps,andalthoughouralgorithmusing v = 2 will execute some unnecessary giant steps, it will still execute fewer group operationsoverall. The secondadvantageis when the upper bound onthe order of the group is too large. Shanks’ algorithm will execute too many baby steps in this case as well. Our algorithm allows one to select an initial step-width that is much smaller than the pestimated order of the group, in the hope of attaining a better approximationof jhgij.UsingShanks’algorithm,aninitialstep-widththatistoo smallresultsinfartoomanygiantsteps,butouralgorithmwilldetectifthe initial step-width is too small and enlarge it if necessary. 3. Computing discrete logarithms Given g,d2G, we wish to decide whether d belongs to the group hgi generated by g. If the answer is \yes," we want to compute x=log d. We use the following g modi(cid:12)cation of Algorithm 2.2 to solve this problem. We compute the order of g in G as in Algorithm 2.2, i.e., we try to (cid:12)nd integers y and r such that gy+r = 1. However,foreachy,beforecheckingwhethergy+r =1,wecheckwhethergy+r =d. For this, we work with the same set R as in Algorithm 2.2. We (cid:12)rst check whether (d−1 (cid:3)gy,r) 2 R, with R as in Algorithm 2.2. If this is the case, log d = y+r. g Otherwise,we check whether (gy,r)2R. As soon as we have found jhgij, we know that there is no discrete logarithm of d for base g, since log d < jhgij. Just as in g Algorithm 2.2, during the computation of R0 = f(g−r,r) : 1 (cid:20)r (cid:20) vg we always check whether log d or jhgij is already found before we include a pair (g−r,r). g