COMPUTING LOGARlTHMS IN GF (2")'

I.F. make'. R.C. ~ u l l i n 2 S.A

, van~tonj

'Department of El#kical Engintcring

University of Waterloo
Waterloo, Ontario. Canada
NZL 3G1

2Department of Gnnbinatoics and Optimization

University of Waterloo
Waterloo. Ontario, Canada
N2L 3G1

1. TheProblcm.
Consider the finite field having q elements and denote it by G F ( q ) . Let a k a generator for the
nonzero elemena of CF(q). Hence. for MY element b+O there exisa an integer J. Osrsq-2. sauh that
b=a'. We call x the discrete logarithm of b to the base a md we &note it by x = bg,b and more rimply
by log b when the base is fued for the dircrudon. Ibc k e t e logarithm problan is stated as folluws:
F i d a camputationally feasible algorithm to compute &gab for any bCGF(q). b+O.
Several cryptographic schemes have been proposed whicb basc their d t y 0x1the intraaability of tbc
discrete logarithm problem for large q.
In 1976 Diffie and HcIlman [Aproposed tbe following public key passing scheme. Let A and B be two
parties who wish to share a mmmm key E. 'Ibe f ~ t field
e GF(q) and a generator a are 5tored in a public
file. Party A generates a random integer u and computes a'. Party B generates a random integer b and
oornputes ab. A rends to E the field element 'a and B sends to A the field element a6. A computes
(a*)'=a& and B computes A and B now h e the commun key K=a*.

Recently, ElGamel [8] has proposed a public key cryptosystem and an authentication scheme whicb b
based on discrete exponentiation. We describe only the public key ayatem here.
consider GF(9) generated by a. Ibe mesaage 5 p e a M w i l l &t of aLl nonzero field clcmtntr. Par-
ty A generates a random integer u and stores a " h a public file. S q p n c parry B wisher to rend a message
m to A . E generates B random integer k and computes (b a" is made public this b possible), a'
md m a d . B sends A the pair ( a k , a d m ) . sina A knows a he can compute (av=ad, and. hence, obtain
m from a d m . Tbis d t m e and the I)iffic-&llman method appcar to have tbe same degree of d t y . It
remains an open problem as to whether or not the security of these systems is entirely dependent oil comput-
TRMardlrupporredinpanby& # 2G5T W1-4-0853
Depamax ofbmmrna'cadmUDder cunrr~~

G.R. Blakley and D. Chaum (Eds.): Advances in Cryptology - CRYPT0 '84, LNCS 196, pp. 73-82, 1985.
0 Spnnger-Verlag Berlln Heidelberg 1985
 74

ing discrete logarithms.

A number of sp&ial plrpow algorithms for computing discrete bga have appeared in the litushut
(sec, for example. [ 2 ] , [9], [ll]. [l4]). In this utide we address only ti^ most general methods amcntly
available.
In the next three Kctionr we deraibe three rubexponential algorithrm for mmputing lop. Thc algo-
nthnu of Sections 3 and 4 are variana of the one presented in section 2. 'Ihese algorithm JUC referred to u
the index-calculw a l g O r i W in an ualht and in-depth d d e 011 t h ~
r
u b
w by O~I*O [13].
For the purposes of this paper we restrict ow discusion to GF(2"). (The algorithm of & o m 2 md
3 apply more generally.) We t b k of the elemma in GF(2') u polynomhh of degree at most n-1 over
GF(2) and multipljcatim is performed modulo lome fixed irredudble polynomial of degree n o v a GF(2).
) btcn of
he examples attd in this paper refer to ~ ~ ( 2 'u2 it~has lomt interest rcantly. (see,for uam-
ple, [IS], D71).

2. AdlrmlnAlparithm

The basic idea\ involved in the following aubexponcntial algorithm for amputing discrete logarithm
are due to Western and Miller [16]. Ameman [l] independmtly dimvncd the algorithm and partially
analysed its computational complexity.
The algorithm consists of two pertr. Tke fint part repuira the QmstNEtion of n Inrge database of loga-
rithms. This databare only m d to
~ be wtruacd OIKT for GF(2"). Part 2 of the algorithm computes indi-
vidual logarithms.

P u t 1 @.tabalw).
Find the logarithms of all irreducible polynomials of degree at most b where b is a fued positive in-
teger determined by GF(2").

P u t 2.
TO find the log of an clement g(x)€GF(2"). g ( x ) # O , generate a random integer u and compute
h ( r ) = g ( x ) a " ( x ) where a
(.) generates GF(2'). Now, factor

h(1) = IiP l l ( 4 .
1-1

If each irreduable factor p i ( r ) has d q p i ( x ) s b then

I
g(x) = BI ci b g P i ( x ) - a
1-

which can easily be evaluated by looking up b g p i ( r ) , lsisr, in the database. If not all pi(.) have
dcg p i ( r ) s b then generate another random integer and repeat.
 75

We define p ( n , b ) to be the probability that a randomly chosen polynomial of degree exactly n har all of
its irredudble factors with degrees of at most b . If N(n.b) h the number of polynomialr of degrcu exactly
n such that cach has all of it, irreducible fenon with degree at most b then

and the erpeaed runtime of the d part of the algorithm rbould bc lpprodmately p(n,b)-'. Odlyzko
[l] shows that

and that the asymptotic mmhg time of the entire algorithm is u7, (cl(n bg n)").
Let S be the set of all irreducible polynomials of degree at most b . In order to find the logarithms of
dl elementi in S we set up a system of IS1 lineax equations in IS1 unknowns w h a e the unknuwnm are the
logarithms. We can fiid this system of cguations by applying part 2 of the algorithm to & elanent of S.
The resulting system must be solved o v a the intcgm modulo 2"- 1. The number of iterations of part 2 to
produce the neccsEary equations is approximntcly ISlp(n,b)-'. For GF(21n) this quantity is m i n i m i d by
b=23. Since there are 766,150 irreducible polynomids of degree at most 23 then we r@ tbh many
equations. A random polynomial of degree at most 126 will factor intn the databasc with b=23 with probe-
bility .000138. This means that to produce the desired set of equations will require abut 5,549X106 itera-
tions of part 2 of the algorithm.

he next section gives a variant of the mem man algorithm which improves the situation for G F ( P ~ ) .

3. The Waterloo Algorithm

This algorithm (see [3]) differs from the formu algorithm in two ways. In part 2 w h a e the polyxlomial
h(x)=g(x)a'(x) is factored this algorithm applies the extended Eudidean algorithm to the polynomiab h(x)
and f ( x ) cf(r)is the irreducible polynomial of degree n which defimes GF(Z").) so that we cau write

h(x) = dil

where (s(.z),r(x))=land deg s(x),deg r ( x ) s E . One o h a t i o n we can auke at this point is that every p-
2
lynomial h(r) of degree at most n (n odd) can bc wrinm uniquely as a quotient of polynomials where each
has degree at most !!and which are relatively prime. If both S(X) and r(x) factor into S then log g(x) is
2
readily computed by table lookup.
The advantage to this algorithm over the previous one is that it ia more probable for two polynomials of
degrees at most
2
=
to fectur into the database than it is for one polynomial of devte n. Let N ( b , i , j ) be the
number of pain of relatively prime polynomials ( A ( x ) , B ( x ) ) such that &g A(x)=i,&g B ( x ) = j and both are
smooth with rcspact to 6 . @y smooth we mean that the polynomial fecton into irredudblcs all of whose de-
grees are at most b . ) For each irredudble polynomial b(x) with degree i s b & f i e the enumerator of b(x)
by
 76

(l+yk+y2+ * * * +#+P+
. * - ).
Letting Ik be the number of irredudble polynomialr of degree It we obtain the generating function for the
N ( b , i d as

where ECy) is the generating function for one mmth polynomial. T b probability that an ordcred pair of
relatively prime polynomia~s( A ( x ) . E ( ~ ) )tam of degree at most 2 are both smooth with rwpact to b is
2

p * ( n d ~ )= (-5; W A A ~ .

In the case of GF(ZE7) Coppmmith [a] har evaluated ibi.~expression for b=17 nnd found
p*(127,17) P 7000. In order to simplify calculationswe approximatcp*(n,b) by [P(n,b)]*. For GF(ZU7).
1
b(127,lq’ a -
5OOo‘
In the following table we list these probabilities for b rsnginll ktwtm 1 md 30 md d m we list the
probabilities assodated with t&e Amanan algorithm. Ihe table also indudtr the erpccted number of itera-
tions to product enough equations to oms- the database for cad^ value of b in the given range.
We see from the table that the number of iteratiom for the database is minimized by b=U). For our
implementationwe sel#ttd b= 17 in orQ to kcep the r y w m of equations mnnageable.
The second difference in the Waterloo algorithm is in producing the equations for the database. We
did not rely entirely on Part 2 of the algorithm. A n u m k of equations were readily obtained by several
techniques whicb make w of the fact that quaring is a linear operator in the field. Our primiple technique
here is refencd to as the generation of systematic equations.
We briefly describe this ttrhnipuc with regard to GF(2=’) generated by j(x)=xm+x+1. Since f ( x )

divides xm+x2+x, it is m y shown that 2’.OSiSl26. can be written as c = 7 , ~ “where y,C{O.l) and
1’0
so the log of any element of the form c cun be r d y found. Similarly the log of any dement of the form
2
J’O
y,x’ where y,€{O,l}, - 1 S J s 6 am be found. This giva 31 equations where the maximum d e

gee is 16. Related to this idea b the observation that if u(x) b any irredudble polynomial of degree d thcn
the degrees of all irreducible polynomiah of w ( u ( x ) ) are divisible by d . Using thir method we obtained 142
linearly independent equations involving the 226 logarithmr of irredudble palynomialr of degree S 10.
 77

prob.bility md ap#tsd numks of rum for t

k new m d Adlanm algorithm. s=127.

New algorithm Adleman algorithm

Total no. of Expected no. Expected no.
Degree imed. polys Probability of mns Probabiliry of runs

1 1 1.27141469E- 32 7.8652544E+31 0.47772090E- 34 0.20932720E+35

2 2 1.61 023467E- 30 1.24205499E+ 30 0.10391370E- 32 0.19246730E+34
3 4 1.42OO3032E- 27 2.81684126E+27 0.10686600E- 30 0.37430020E+32
4 7 1.15313844E- 24 6.07038995E+24 0.16022050E-28 0.43689770E+ 30
5 13 3.4632 1 796E- 21 3.75373429E+21 0.128061OOE-25 0.10151400E+28
6 22 2.43083741~-18 9.05037906~+18 o.m489980~-23 0.36369650~+2~
7 40 1.75009226E- 15 2.28559379E+ 16 0.58661830E-20 0.68187380E+22
8 70 2.99279106E- 13 2.33895379E+ 14 0.20402690E- 17 0.34309190E+20
9 126 2.39477444E- 11 S.26145586E+ 12 0.40463370E- 15 0.31139250E+ 18
10 225 7.73424039E 10- 2.909141 54E+ 11 0.31 781350E - 13 0.70796220E+ 16
11 41 1 1.42517804E-08 2.88385022E+ 10 0.13612270E- 11 0.30193290E+15
12 746 1.48157461E-07 5.03518348E+09 0.29555 160E- 10 0.2S240930E+ 14
13 1376 1.0660927E-06 1.29069451E + 09 0.41 129290E -09 0.33455440E+ 13
14 2537 5.46899677E-06 463887639 0.3746155OE-08 0.67722710E+ 12
15 4719 2.I9028276E-05 215451634 0.24991280E-07 0.18882570E+ 12
16 8799 7.12191038E-05 123548311 0.1272363OE-06 0.69154690E+ 11
17 16509 1.96662481E-04 83945854.4 0.5242853OE-06 0.31488570E+ 11
18 31041 4.7 101 5 4 8 8-~04 65902291.s 0.17992970E-05 0.17251720E+ I1
19 58635 l.OO764675E- 03 58190035.4 0.53284450E-05 0.11OO4140E+I I
20 111012 1.96260912E-03 56563479.1 0.13895770E-04 0.79888990E+ 10
21 210870 3.541 77251E-03 59537985.4 0.32587350E-04 0.64709140E+ 10
22 401427 5.96621694E-03 67283339.5 0.69740460E-04 0.57560100E+ 10
23 766149 9.45338803E-03 81044911.9 0.13806940E-03 0.55490060E+ 10
24 1465019 .0142 135998 103071637 2.25535770E-03 0.57373450E+ 10
25 2807195 .0204564492 137227872 0.44523690E-03 0.63048900E+ I 0
26 5 387990 ,0283794933 189855046 0.73751900E-03 0.73054240Et 10
27 10358998 .038 1757153 271350462 0.1 16804~ O-E02 + 10
0.813t%36300~
28 19945393 .0~0024a252 398709899 0.17773340E-02 0.11222780E+ 11
29 38458183 .0640949758 60001 8684 0.26095230E-02 0.14737250E+ 11
30 74248450 .0805164802 922152208 0.33185230E-01 -

Another example of making ILK of thc linearity of quaring is Imethod referred to m weight manipula-
tion [4] (for more details ste [S]). Define p(x)=x'"+g(x) where g(r) ha, degree k<<m. Define d to bc
the IaTgat integer 8uch that 2 d m 1s n . Let I = n -Zdm md consider

4 (I)=+.J(.IP(.I.df ( r ) ) .

It follows that
&g C(x)=mCur {k2d,dcg V(x)+f)l.

If p ( x ) and C ( X ) are 8mootb with respect to & then we obtain an equation. For c~ample,in GF(Zu7) gtn-
crated b y f ( x ) = x u 7 + x + 1 takcp(1)=l+x~andd=7thens=15. Thisgives

=xu(1+~7)16=1 +=+xu.

Clearly, both t ( x ) and p(x) are smooth with respect to 6=17. A similar result can be dtveloped for
 Coppersmith [6] has ertendtd the idea behind these techniques md har obtained striking bnprovrmtntr
in the index calculus methods. We l o u l d mention that asymptotically the Waterloo algorithm is of the L B ~ C
order (q(ct(n log n)?) es the Ameman algorithm but for fields GF(2") of practical interest it gives mucb
better rumling times. 'Ibe GJppcrddl algorithm ir describedinthenaleetion.

The database for GF(2U7) was amstnutuI at Dcnclmr using the& HEP computer [12]. A HEP con-
sists of from one to sixteen procrss ascution modules and each is a pipelined p~xeuor
with a depth of 8.
Sine the HEP can w a given program in pardel with iculf. fhc inda-calculw algorithm art ideally auited
to this arrbitccture. sevcral copies of the algorithm were run in parallel to jKuducc linear tquatiDns whi&
when added to those found systematically and by weight manipulation would yield 16.510 linearly indepcn-
dent equations in the 16,510 unknown logs. Siaetn copies of the algorithm in parallel appeared to be ap
timal. The database toak about 7 houn to build and computing individual logs using Part 2 takes under 1
mxmd on the HEP. Having the database OUT implcmcntation on a VAXllnsO taka about five minutes per
logarithm.
kc mentioned in the previous paragraph. the inda dculw algorithms are ideally suited to parallel pre
assing. If we run n oopies of the program in parallel then the l o g a r i h is obtained from the which
finishes fmt. We compute the expected number of iterations to frnd the logarithm of an element given that
n copies of the algorithm are running mimultanecusly. Let p be the probability that an iteration will s d
in computing the logarithm and let q= 1-p. Suppoac i of the proccsser complete on the kh iteration and the
-
remaining n i do not. The probability of tbb event is

and the probability that at least one of the proassts finishes on the iteration is
 79

4. TheCopparmlthAltorttbm
ThC algorithm descn'bad in thir &on maka crtmak use of the linearity of quaring in GF(2"). The
method appliw ~LUI t o p p kp e n in C F ( ~ *for
) n>1.
Coppcnmith's modification [6] of this basic indcx-calculus algaithm of d o n 2 improves substantially
the perfomma of both par0 1 and 2. Let'a first d d e r part 1.
The algorithms of the prcvi~wrections and the algarithm given here rely cn the fact that polynomials
of degree k tend to factor into polynomials whose degrees arc "mnll". In order to generate enough qua-
tionr to construct the database for GF(2") ~elcctpeirS of poIynomialr (a(r),b(x))auch that &ga(x)sd and
& g b ( x ) sd where d<b and the gcd of a(x) and b(r) is 1. It ir easily aecn that there arc precisely ZUc1 rueh

pain. Let t be a powa of 2 near andrboase L to b e t h e l w t integer greater than t. Suppose also

that the generating polynomial for the field ha8 the form f ( x ) = x " + g ( x ) where g(r) has low degree. Let
h(x)=fi=g(x)E&--. and dcfic

C(J) = 2(I)~+ E (I)

and

d(.)+(=)I'.
If both c ( x ) and d ( x ) then we obtain m equation for the database. In the case
are sxnooth with respect to b.
n=127 we take b=17, t = 4 . h=32 and d=10. T~ICpolynomialr c(x) .nd d(x) have degrees ~ 4 2 .Cop-
p&th [a] shows that the 2 million possible paira (u(x),b(x)) yield h u t 47,000 equations in 16,510
unknowns. The above procedure is a variant on the waght manipulation method of the previous d o n . A
more direct application of waght manipulation am be daaibcd. We iuustrate the technique in the case
GF(Zu') generated by f ( ~ ) = x ~ ' + x + l . Select pain of p o l y n d a l r (a(x),b(x))which are relatively p r h c
and such that deg u(x)s7 and deg b ( x ) s 8 . Form the polyndala c ( x ) = a ( x ) ~ ~ ~ + bmd (x)d ( ~ ) = x ~ [ c ( x ) ] ~
whne deg c(x)s38 and dtg d ( x ) s 3 5 . If c ( x ) md d ( x ) are smooth with rtspsa to b=17 we get M qua-
tion.

We now describe part 2 of the algorithm. Let g(x) be a field elanent whose log is to be found. Sug
r-deg g(x). Let t bc B power of 2 d~ to and h be the lwt iatcga pcatcr then dk. For a-
ample, if ~ ~ 1 2 7b=17
, md r=33 tben chanc k = 2 m that h=&. F d y =lea d d- to
( r + G ) l o g n w . ~n our u a m p ~ ewe takt d = ~ . a relatively prime pair of po~ynomialsa(x) and
b(x) Cam of degrw S d r d that g ( x ) divides c(x)=2a(x)+b(x). 'Ibc dmicts for o(x) and b(x) c ~ l ld y
bc &terminad by W h k g a linear SyS- Of CqwtiOnr Over GF(2). Let ~ ( x ) s [ c ( J ) ] ~If. both C ( X ) E d d(x)
arc smooth with resped to tbe bound b(')= h m then we have at mmt 2 irrGduciblc factors of degree at
most bfl). For each factor with degree > b we iterate thic pmcuhrc and redua the bowd b(') with cad^
iteration. That ia. at iteration i , b ( i ) = h ( b / n ) - i . If not both of c(x), d ( x ) are unmth then doox a new
pair ~(1).b(x) and s ~ a r again.
t
-1 -2
The asymptotic rurming time of thic algorithm h comput#1 by coppenmith [6] to be ccp ( c n 3 ( l o g n I 3 )
which improves the results of the prcvioua two sections.
 80

We have implemented pat 2 of coppersmith’s algorithm. The following table &playa tat nrulta of 8
s a q l w each &ring of 100 randomly generated polynomials of degree at most 126. ’Ibe degree bound b
h always 17 but for ceeh q 1 e we varied the W t h degree bound b‘ and the value of d. We have a
column labelled “Total Number of Basic Iterations”. Thir r c f m to the number of iterations required to o b
tain smoothness with respect to b‘. The coIumn lnbcllcd “Total Numbcr of Coppenmith Iteration” is the to-
tal number of iterations to obtain smoothness with respect m degrtt bound 17 far thore polynomials with &
gree between 17 and b‘. We a h found that in thi3 case a mingle step reduction of the Coppcnmitb reduc-
tion WBS optimal.

Total
Total Average
number
number of time
I I ofbasic Icoppenmithl in= I
b’ I d’ I iteratiom 1
it&tiom pcrlog I
20 I 12 I 99.496 I 6.731 I 57

From the table it appeart that b‘=23 and d-14 ir optimal. With these values we ran a sample of 500
randomly generated polynomiah with the following result. The column headings are the aamc as in the pre-
vious table.

[ 23 I 14 I 120,661 I 101,563 I 26.6 I

For GF(Z1”) we r e f a to an equation of the form
[C(x)14 = [ A ( Z ) X ~ ~ + B ( X ~ ] ‘

IU a Coppersmith equation. As a direct generalization of the weight manipulation technique discus4 earlier
we consider quatiom of the form

X“C(X)]4 = $7-4’ [A(.t)r‘+B(r)14

and refer to t h u e as yndcljl41v equations. With the degree of A ( x ) and B(x) at m a t 9 in the C0PptrSmth
equations we generated 19461 equations for the database in 8.1 houn on the VAX. With thc degrua of
A(x) and B ( x ) at most 8 we obtained 7777 quatiom in 2.23 horn. Ihe follawing table lista rralta when
underflow quatiom were used. Thc columnr labelled drg A and drg B refer to the bighest degree used for
A and B rcspcdvely. For polynomial A we require that it hss a amstant tcrm BO that no coppCrrrnim equa-
tions are generated this way m d the cquationr obtained from distinct rows are all different.
 Valucof Numberof

7193 2.88

Ifwe~theCoppersmith~ti~withthe&greaofA(x)andB(~)atmort8.ndweusetheunderflow
cquatiom given in the frnt two m a of the table we get 22,861 equations in 8 hours or one equation every
.3499x houii. Thir is approximately a 16% improvement ova collatinp the 19461 cquatim using the
CoPpmmhh equations with and &g E(x)S9. Thir data WYIUobtained by running our program on
I g A(x).
a VAXllnsO at the University of Waterloo. The program b written ia Fortran 77 with the gcd routina in
assembler.

5. Coadarlon

We have described tbe basic hdex-caladus algorithm and two variants of it. 'Tbe basic algorithm and
the Waterloo dgOrithm both carry over to GF(p), p a prime. Using &t Eudidcan algorithm for integers it
is easy to show that given an h t ~ g a,
n I s a s p - 1 , that there exist integaa r md t w d that
~ ~ t - t ( d p )
and l s l s l , rsp-1.
As for GF(2") it h dear that for n=127 thh field is insa*m and &odd be avoided in cryptographic
demes. In [13] Odlyzko analyses the performance of the copperrmith algorithm for various v d u a of n
running on various ~ ~ I X Sof equipment. me mmlusion scans to bc that i
m ambitious effort might k able
to produx the ncccsary database for ns1280.

L.M. Ademan. A rubaponcntial a l g O r i h for the dircrete logarithm problem with applications to
cryptography, Proc. 20rh IEEE Found. C o y . Sci. Symp. (1979), 55-60.
B. Arazi, Sequences ~mstNcttdby operations modulo 2"-1 or mod2" md their application in
evaluating the mmplcxity of a log operation WCTGF(2"), prCprint.
I.F. Blake, R. Fuji-Hara, R. C. Mullin arrd S.A. Vanstone, Computing logarithan in finite fields of
characteristic two. S U M 1. A l g . Disc. M c r M . Vol. 5 4 2 (1984). 276.285.
I.F. Blake, R. Fuji-Hara, R.C. Mullin and S.A. Vanstone, Frnite field-techniques for Wt registera
with applications to ranging problems and cryptography, F d Repart Project +10616-02. Department
of Communeatim (1983).
I.F. Bake, R. Fuji-%a, R.C. Mullin and S.A. Vanstone, An attack 011 the discrete logarithm prob
]em in ~ ~ ( 2 R O~ ~ ~W 1~ e,p o r t ROW
. +iwim,Dtpsrtmmt of communiesti~nr(1982).
D. Coppenrnittr. Fast evaiustion of logarithms in fieldr of Charlrcterirtic two. IEEE Trznr. Iqfonn.
Thcav, (July 1984). 587-594.
W. Diffie and M E . Hellman, New directions in cryptography, IEEE Trans. Idom. Theory. lT-22
(1976), 644.65'4.
 82

[8] T. ElGamel. A public key ayptosystan aad a signature scheme based on discrete logarithms. 1EE.E
T r w . Znfonn. Theory. to ~tppear.
[9] T. Hcrlutam and R. Johormeson, On mmpuh logaritbmr o v a GF(2p). BIT 21 (1981), 326-334.
[lo] D.E. Knuth The A n of Computer Programming: Vol. 2. S c m h w n d d Algorirhw. 2nd ed. Mdison-
Wesley 1981.
[ll]D.L. Long and k Wigdtnon. Hoar discreet is the discrete log? P m . 15th ACM Xymp. Theory 01
Computing (1983). 413420.
[12] R.C. Mullin, E. Naneth and N. Weidcnhofer, Will public key crypt0 systems live up to thcir erpeaS-
of the discrete log atwrtaker. preprint.
tions7 HEP imp~anmtation
[13] A. Odlyzko, Dirattc logarithms in finite fie16 and thdr ayptopphic sienificawc, Ewtxrypr-84 (to
a m ) .
[14]S.C. Pohlig and M. Htllman. An improved algorithm for complting logariithms ova GF(p) and its
cryptographic sieaificaoa. IEEE T n w . ldorm. Theory IT-24(1978). 1W110.
1151 B.P. Sdmnnhg, Data mpyption witb public key dirt~C~tion.
W C O N Cod. R a . . W&ington D.C.,
October 1979,653-660.
[la] A.E. Western and J.C.P.Miller. Tabla of indices and primitive roots. Royul Socicry Afurhumxficul
Tublcs, Cambridge University 9 (1968).
[lq K. Yiu and K. Peterson. A singlbebip VLSX implanmtatim of thc dircrcte exponentid public key di8-
tribution system, Proc. GWBECOhf-82, IEEE (1982). 173-179.