Integer Factorization and Computing Discrete Logarithms in Maple

更新时间：2023-05-21 13:36:01 阅读量：实用文档文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

integer推荐度：
相关推荐

have investigated algorithms for integer factorization and computing discrete logarithms. We have implemented a quadratic sieve algorithm for integer factorization in Maple to replace Maple’s implementation of the Morrison-

Integer Factorization and Computing Discrete

Logarithms in Maple

Aaron Bradford?,Michael Monagan?,Colin Percival?anbradfo@sfu.ca,mmonagan@cecm.sfu.ca,cperciva@irmacs.sfu.ca

Department of Mathematics,Simon Fraser University,

Burnaby,B.C.,V5A1S6,Canada.

1Introduction

As part of our MITACS research project at Simon Fraser University,we have investigated algorithms for integer factorization and computing discrete logarithms.We have implemented a quadratic sieve algorithm for integer factorization in Maple to replace Maple’s implementation of the Morrison-Brillhart continued fraction algorithm which was done by Gaston Gonnet in the early1980’s.We have also implemented an indexed calculus algorithm for discrete logarithms in GF(q)to replace Maple’s implementation of Shanks’baby-step giant-step algorithm,also done by Gaston Gonnet in the early 1980’s.

In this paper we describe the algorithms and our optimizations made to them.We give some details of our Maple implementations and present some initial timings.Since Maple is an interpreted language,see[7],there is room for improvement of both implementations by coding critical parts of the algorithms in C.For example,one of the bottle-necks of the indexed calculus algorithm is?nding and integers which are B-smooth.Let B be a set of primes.A positive integer y is said to be B-smooth if its prime divisors are all in B.Typically B might be the?rst200primes and y might be a50 bit integer.

?This work was supported by the MITACS NCE of Canada.

2Integer Factorization

Starting from some very simple instructions—“make integer factorization faster in Maple”—we have implemented the Quadratic Sieve factoring al-gorithm in a combination of Maple and C(which is accessed via Maple’s capabilities for external linking).In this section,we shall describe some the design decisions we made,the reasoning behind them,and some of the opti-mizations we were able to make which allowed us to improve performance.

2.1Maple

The?rst design decisions we made resulted from the target of speeding up integer factorization in Maple.While most work in the?eld of integer fac-torization has historically been centered around factoring integers which are as large as possible—usually involving hundreds of processors and several months—Maple is typically used interactively and on a single processor, so we concluded that obtaining good performance for inputs ranging from 50to100digits(which,on modern systems take time ranging from a few CPU-seconds to a couple of CPU-days)was of far greater importance than reducing the time needed to factor a150-digit input.In light of this,we decided to ignore the General Number Field Sieve in favour of the Quadratic Sieve.While the Quadratic Sieve is asymptotically slower than the Number Field Sieve,the constants involved make the Quadratic Sieve faster up to a break-even point of around90–135digits depending upon the implementa-tions used,and even beyond this point the Quadratic Sieve falls behind quite slowly.

Our second major design decision was inspired by the use of Maple as a pedagogical and research tool.The Quadratic Sieve factoring algorithm consists of three major steps—sieving to?nd“relations”;?ltering the list of relations found to make it more manageable;and solving a large sparse linear system modulo2—and all three of these steps are targets of active research.Consequently,we decided to perform as much work as possible in Maple,and to return the results of each step into Maple before passing it into the next step.In this manner,we make it easier for students to examine the code in order to learn how the Quadratic Sieve operates,and even more importantly make it easier for researchers to“drop in”a replacement for one of the parts if they are investigating potential improvements.Although Maple is generally signi?cantly slower than code written directly in C,we

shall see later that since most time is spent executing a relatively small

amount of code,it is possible to obtain good performance while only writing

a small portion of the code in C.

2.2The Sieve

While it is traditional to speak of the Quadratic Sieve,it is grammatically

more accurate to speak of a Quadratic Sieve,since there have been a series

of improvements made to the original concept.The original Quadratic Sieve

developed by Pomerance[10]in1981,which factored an input N by searching for values of x such that f(x)=(x+ √N )2?N is smooth,was quickly replaced by the Multiple Polynomial Quadratic Sieve[11](hereafter MPQS),

which takes a series of values a=q2for primes q,solves b2≡N(mod a), and then searches for smooth values of f(x)=(ax+b)2?N.This was revised further by Alford and Pomerance[1]in the Self-Initializing Quadratic Sieve1(hereafter SIQS)which takes values a of the form a=q0q1...q r for appropriate q i and then searches for smooth values of f(x)=(ax+b i)2?N for b i equal to the2r non-trivially di?erent2square roots of N modulo a.

Whichever Quadratic Sieve is being used,the sieving takes a similar form.

An array of M bytes is?rst initialized to zero,then for each prime p less than

a bound B1(known as the“prime bound”)modulo which N is a quadratic

residue,each position x in the array satisfying f(x)≡0(mod p)is increased

by log p.These locations are computed from the roots of f(x)modulo p—

for each rootα,the values in positionsα,α+p,α+2p,...are adjusted.In

SIQS,this initialization cost—computing the roots of f(x)modulo each of

the sieving primes—is amortized over2r sieving intervals(thus the“Self-

Initializing”sieve would more appropriately be called an“Amortized Initial-

ization Costs”sieve).

In light of our design decision to perform as much computation as possible

within Maple,and also in keeping with the general principle of using the best

available algorithms,we decided to use SIQS,performing the initialization

computations in Maple but sieving each“hypercube”in C.

We also apply the ubiquitous“large prime variation”,with either one or 1The Self-Initializing Quadratic Sieve was also independently discovered by Peralta, who called it the Hypercube Multiple Polynomial Quadratic Sieve.

2Since(?ax?b)2=(ax+b)2,we can ignore half of the2r+1square roots of N modulo a;this is usually performed by requiring that all the b i are congruent modulo q0.

two large primes,depending upon the size of integer to be factored:Rather than requiring that f(x)factor completely over the primes less than B1,we permit it to have one or two prime factors between B1and a“large prime bound”B2.

2.3Choosing hypercubes

The choice of the primes q i(and thus the values a)is subject to a number of considerations:

1.In SIQS,as in MPQS,the value a should be approximately equal to

√8N/M,where M is the length of the sieving interval3.The further

a varies from this value,the larger the average value of f(x)will be

at points within the sieve,with the inevitable result that fewer of the points within the sieve will be smooth.

2.Since SIQS amortizes the cost of sieve initialization over2r sieving

intervals,larger values of r will reduce the time spent on initialization.

3.On the other hand,each prime q has the e?ect of reducing the frequency

of smooth values in the sieve.Since N is required to be a quadratic residue modulo each q,there would normally be two values x mod q for which x2?N≡0(mod q);however,for b2≡N(mod q)there will only be one value of x mod q for which f(x)q?1≡0(mod q).

4.Finally,SIQS can often?nd the same relation multiple times,which

both decreases the number of useful relations found and adds the addi-

√2N tional complexity of removing such duplicates.If a value0≤x<

satis?es x2?N≡0modulo both a=q0...q r and a =q 0...q r,then the relation will be found twice(assuming that both values are taken for a during the sieving).Naturally,this is almost impossible unless the sets{q0...q r}and{q 0...q r}intersect.

While Contini[5]recommends minimizing the number of duplicate rela-tions found by requiring that the sets{q i}di?er by at least two primes,we adopt a sharply di?erent approach.Fixing q1...q r,we allow q0to take on,in increasing order,the primes immediately following the sieving prime bound B1.Since the number of hypercubes which need to be sieved in order to?nd 3Note that some authors use a sieving interval of length2M,i.e.,from?M to M.

enough relations is typically far less than B 1,the values a will remain rea-sonably close to their ideal value and the number of duplicate relations will be small.In addition,since all of the values q 0are above the prime bound

B 1,any duplicate relation will contain the relevant q 0as a “large prime”,making the task of removing duplicates trivial.

Choosing the primes q i in this manner has a further bene?t in reducing the initialization costs.After ?xing q 1...q r ,we can precompute

α0=r i =1q i

βi =α0q ?1i ?1≤i ≤r γi =√Nβ?1i mod q i

?1≤i ≤r θi,p =q ?1i mod p ?1≤i ≤r,?p ∈P ψp =√Nα?10mod p ?p ∈P

where P is the set of primes less than B 1modulo which N

is a quadratic residue,and the notation √N mod p means either root of x 2?N mod p .For each cube,after selecting q 0,we then compute

αi =q 0βi

?1≤i ≤r φi =γi q ?10mod q i ?1≤i ≤r φ0=√Nα?10

mod q 0θ0,p =q ?10mod p

?p ∈P and note that a =q 0β0,the 2r values of b are

?α0θ0?r i =1d i αi φi

where the d i each take the values ?1and 1,and the sieving o?sets at which log p must be added are

(φ0±ψ0)θ0,p +r i =1d i θi,p φi .

In this manner,the initialization costs are reduced r -fold beyond those in most implementations of SIQS.

2.4Sieving optimizations

The?rst optimization we made to the sieving process itself was to apply the widely used“small prime variation”.Here we?x a value B0,known as the “small prime bound”,and instead of sieving using primes less than B0,we compute the average contribution which will result from such primes.Since small primes require the most work to be done during sieving,this provides a signi?cant speedup.In our implementation,however,we di?er somewhat from the usual small prime variation:Instead of merely computing the mean contribution from small primes,we compute both the mean and standard deviation,and then attribute to each point in the sieve an estimated small prime contribution equal to the mean plus2.5standard deviations4.In this manner,we reduce the number of smooth values which are missed due to having above-average numbers of small divisors.

After the sieving process produces a list of“hits”,we add an optimization which we believe to be new.Realizing that most points will have fewer small prime divisors than the above-average value which we earlier attributed to them,we compute for each point the actual contribution from small primes. Taking this in combination with the“over-sieve”(the amount by which the sieve threshold was exceeded),we?lter the list of hits returned by the sieving and reduce the number of insu?ciently smooth points being considered;this provides a signi?cant speedup in later steps.

Given this(now much reduced)list of sieve hits,we proceed to trial division:We divide the values f(x)by each of the sieving primes p in turn, constructing the factorization of each f(x)into a product of primes less than B1and possibly a remaining term which is either a single large prime or the product of two large primes.In this trial division process,we make another new optimization:Since we know from the sieving process the sum of the(rounded)logarithms of the primes dividing f(x),we subtract away the logarithm of each prime as we?nd it,and exit the trial division loop once we know that we have found all the sieving prime divisors.Since the largest

prime divisor of f(x)below B1is on average about2

3B1,this“early exit”

optimization provides a signi?cant speedup to the trial factorization step.

Once the trial factoring is complete,we consider the remaining part(if any)of f(x).If the remaining value is between B1and q0,we discard the value—we have a duplicate of a relation which was found in an earlier hypercube.For values between q0and B2,we have a relation containing 4The value2.5was chosen based on performance testing.

a single large prime.Values between B2and B21we discard,since they must re?ect a single prime greater than the large prime bound;and?nally values greater than B21are subjected to a single pseudoprime test,probable primes are discarded,and then Brent’s variation of the Pollard Rho factoring algorithm[3]is used to split the value and a relation is constructed containing the two large primes.

2.5Cycle counting and relation?ltering

In keeping with standard practice,we use the Union-Find algorithm to?nd cycles within the large primes.Unlike most implementors,however,we have two major advantages:First,since all the sieving is performed on the same system,we can run the Union-Find algorithm while the sieving is ongoing, adding new relations as they are found;this allows us to stop sieving as soon as we have enough relations rather than needing to guess when we should stop.Second,Maple provides very easy to use hash tables,making the implementation far simpler than it would be in a less powerful language.

Once we have enough relations,we take further advantage of the Union-Find algorithm to?lter the relations.By e?ectively running the algorithm backwards,we eliminate all of the relations which contain a large prime but are not a member of a cycle;this is considerably faster than the more common approach of repeatedly?ltering the list of relations by removing “singletons”(relations containing a large prime which does not occur in any other relations).

Finally,we make a pass through the relations eliminating any prime which occurs in only two relations by multiplying those relations together.

2.6Linear algebra

Once we have a?ltered list of relations with more relations than primes involved,we return to C and apply the block Lanczos algorithm for solving sparse systems of linear equations modulo2.Here we do not diverge from the usual approach at all:For performance reasons,the entire block Lanczos algorithm must be performed in C5,and we use a block size equal to the machine word-length,taking advantage of the internal parallelism of bitwise operators.

5We found at one point that our C code could solve an entire system of order2000in less time than it took for Maple to compute a single matrix-vector product!

Once the block Lanczos algorithm completes,we take the solutions re-turned in order,multiply together the indicated relations to produce an equa-tion of the form X2≡Y2(mod N),and compute igcd(X?Y,N);when we?nd a non-trivial factor,we stop and return it to the user.

2.7Performance

In order to demonstrated the performance of our code,we consider the values

N=p>(10n/2e)·p>(10n/2?1π)

where p>(x)denotes the smallest prime greater than x;these are n-digit integers.In Table1we show the time taken on a2.5GHz Apple G5sys-tem by Maple’s current default integer factoring algorithm,the Morrison-Brillhart algorithm(“maple”),Magma’s integer factorization routine,which spends a short time searching for small factors using special-purpose fac-toring algorithms prior to using the Multiple Polynomial Quadratic Sieve (“magma”),our own implementation(“SIQS”),and Jason Papadopoulos’“msieve”command-line application,which is generally regarded as being the fastest implementation available of any form of the Quadratic Sieve[9].

n maple magma SIQS msieve n magma SIQS msieve 280.720.260.190.156087.7321.6614.59 32 2.410.380.320.1964204.4949.9042.14 36 5.890.490.470.2668449.8592.2781.39 4019.60 1.150.810.51721189.31226.69201.47 4484.83 2.04 1.910.63762731.23425.95396.17 48281.29 4.87 2.93 1.33807177.241329.671329.88 521472.3311.89 5.73 3.1884>1043339.392821.30 565136.7532.3410.58 6.2188>1047027.395042.18 Table1:Integer factorization timings(in CPU seconds)

While it is immediately clear that the Morrison-Brillhart algorithm is inferior to the various Quadratic Sieve implementations,we note also that the gap between Magma’s MPQS implementation and our SIQS reaches a factor of5,while our code comes very close to msieve’s performance,con?rming that —at least for large inputs—the cost of performing hypercube initialization in Maple is ultimately insigni?cant.

3Discrete Logarithms

We begin by de?ning the discrete logarithm problem.Suppose we have a ?nite group G and an elementα∈G of order n and an elementβ∈ α .The Discrete Logarithm Problem(DLP)is,givenαandβ,solveαc=βfor the unique integer c satisfying0≤c<n.We denote this value,c,as logα(β). Example1.Let G be the subgroup of Z101,the integers modulo101,gener-ated byα=2and supposeβ=14.Here G= α ={1,4,16,64,54,14,56,...} and the order ofαis50.In this simple example,the order ofαis small,so we may simply test ifαc=βfor c from0to50until we?nd one that works, in this case,c=5.

In a larger group,for example,a group with2100elements,this brute force method,which requires n/2multiplications in G on average,becomes infeasi-ble.Although we can do better than O(n)multiplications in general,it turns out that there are no known algorithms for large subgroups of Z q generated byαwhich are polynomial time in log q.It is this di?culty of computing discrete logarithms in this group,and also the group of points on an elliptic curve,that is the basis for various modern cryptographic systems,such as the the ElGamal public key cryptosystem.See[12].

3.1Maple’s mlog command.

Maple’s current method,the numtheory[mlog]command,for solving the DLP on the multiplicative structure of Z m where m is an integer,employs the following strategy.The method factors m and solves a number of DLPs in Z p for each prime p dividing m.To solve these smaller problems,Maple implements the Pohlig-Hellman algorithm,which in turn calls Shanks’baby-step,giant-step algorithm as a subroutine.The Pohlig-Hellman algorithm takes advantage of the factorization of

(p?1)=Πk i=1q e i i

by solving e i instances of the DLP modulo q i to obtain c i satisfying

β=αc i mod q e i i,

and then applies Chinese remainder theorem to?nd the value c modulo (p?1).For a full description of this algorithm,we refer the reader to the Handbook of Applied Cryptography[6]or Stinson’s text[12].

To solve the DLPs modulo each prime factor q of(p?1),Maple currently implements Shanks’Baby-Step,Giant-Step method.This method is is an O(√q)method.It is illustrated with the following example in Z101. Example2.Suppose q=101,α=7andβ=57.Hereαis a primitive element of Z101so n=100.In the?rst step we build a table of pairs of values. Let k= √q =11and for i from1to k?1compute values(i,αmi mod q) and sort them by the second entry.In our example,this table is

i074963185102

αki115192930385158696576

In the second step we compute the discrete logarithm ofβas follows.For j from0to k?1we test,using binary search,ifβ×α?j is among the second entries in the table.For j=0we haveβα?j=57,which is not in the table. Eventually we?nd for j=8we haveβα?j=15,and we see that(7,15) is one of the entries in the table.We haveα11×7≡βα?8(mod q)and so β≡α11×7+8(mod q)and we have found that logαβ=11×7+8=85. Now let us look a the complexity of the algorithm.Notice that we can compute the k entriesαmi in the table in O(k)=O(√q)multiplications in G.The cost of sorting the table on the second entry using an O(n log n) sorting algorithm requires O(k log k)=O(√q log q)comparisons.In the second step,computing theβα?j costs one inverse and at most another k=O(√q)multiplications and at most another O(k log k)=O(√q log q) comparisons to search the table using binary search.Thus this algorithm does O(k)=O(√q)multiplications in G and makes O(k log k)=O(√q log q) comparisons of elements of G.It also needs to store O(√q)elements of G in the table.

This is not a problem for Maple’s current implementation when the prime factors of(p?1)are all small,however,when this is not the case,Maple will take an inordinate amount of resources to compute the desired logarithm.In the worst case,p is prime and p=2q+1with q also prime.This will force Maple to construct a table with O(√p)entries.Primes p of this form are called‘safe primes’because they make integer factorization algorithms and discrete logarithm algorithms harder and hence,cryptosystems like RSA and ElGamal‘safer’.

3.2The Index Calculus Method

As we will see,a better approach would be to use an index calculus method instead of Shanks’method when the prime q is‘large’.The index calculus method is a randomized algorithm that constructs a database of the loga-rithms of‘small’primes(say the smallest50,100or500primes)and uses this database to reconstruct the logarithm desired.Returning to our previous example,we illustrate how the index calculus method works.

Example3.Recall that we had q=101,α=7andβ=57whereαis of order n=100.Let B={2,3,5}be the set of‘small’primes(called the factor base).We calculate logα2,logα3,and logα5and use these to reconstruct logαβ.The key is to?nd values of c such thatαc mod q is B-smooth(that is,is only divisible by the primes in B,or,in an abuse of notation,is divisible only by primes less than or equal to B;in this way,B is an upper bound but can also be thought of as a set of primes).We choose these values of c at random from[2,q?2].Many values of c will work,three of which are c=25,30,61.For these values we have

α25=2×5mod q,α30=2×3mod q,α61=2×52mod q. Taking logarithms this yields the system of linear congruences

25=logα2+logα5(mod q?1),

30=logα2+logα3(mod q?1),

61=logα2+2logα5(mod q?1).

One now solves this linear system modulo q?1=100to obtain the unique solution which is

{logα2=89,logα3=41,logα5=36}.

Now,by?nding one value d for whichβαd is B-smooth,we can solve for logαβ.One value that works is d=81.We obtain

βα81=2×3×5(mod q).

Again,taking logarithms we have

logαβ+81=logα2+logα3+logα5(mod q?1). Substituting for logα2,logα3and logα5,and solving for logαβwe obtain logαβ=89+41+36?81=85(mod q?1).

3.3Optimizing the index calculus algorithm.

The limiting factor for this procedure is how quickly we can?nd a set of congruences that determines a unique solution for the logarithms of the factor base B.For large q,few choices of c work,so we generally end up spending most of the time searching for appropriate candidates c.In order to make this task faster,we might simply increase the size of the factor base B.While this would certainly guarantee an increase in the probability that a number αc mod q is B-smooth,we also must keep in mind that in order to uniquely determine a system of linear congruences,logαp must be involved in at least one congruence for each p in B.But the larger that we make B,the less likely it is that the larger primes of B will be divisors ofαc mod q.At one extreme B={2}and we expect to search O(log2q)values of c to?ndαc mod q which is an exact power of2.This is no better than Shanks’method.And at the other extreme,B contains all primes less than q and we expect to search O(q)values of c to?nd the only such value to yield a congruence involving the?rst prime less than q.A compromise can be found between these two extremes(a lot closer to the?rst one)that will allow us to make signi?cant gains on Shanks’method for large q.

In a result from[4],Can?eld et al.show that the probability that a number less than q is B-smooth is asymptotically u?u(1+o(1))where u= log q B.As well,the prime number theorem tells us that the number of primes less than B is asymptotically B/ln B.Although our choice for B will usually be rather small,these two equations will at least give us a starting point for choosing what value we ought to set B for a given q.We must?nd at least one congruence for each p in B,and it will take u u(1+o(1))tries to?nd c for whichαc mod q is B-smooth.Therefore,we expect to search u u(1+o(1))B/ln B choices of c before we have determined our system of congruences.We should, then,seek to minimise this function over all possible choices of B.The above discussion applies in the limit that q and B tend to in?nity,however,we will be concerned with‘medium’sized values for q and B such as log q<100and |B|<5000.In practice,we compiled many experiments for di?erent choices of q and B and sought a polynomial approximation relating log2q and B.

Once we have chosen our smoothness bound,B,the greatest speed up that we can get is in formulating a strategy that will allow us to quickly decide whether a value c will lead us to a value for whichαc mod q is B-smooth. The greatest boon in this was a result presented in[2]for computing discrete logarithms over GF(2k),though it is straightforward to modify for logarithms

in GF(q)as was done in[8].We describe the idea.

Consider applying the Extended Euclidean Algorithm(EEA)to the in-tegers q and y=αc mod q.We will obtain a sequence of triples(r i,s i,t i) satisfying

r i=s i y+t i q

where the remainders r i decrease in size from q to1and the s i increase monotonically in magnitude from0to an integer of size O(q).The index,k, of i when r i is?rst less than|s i|will have r k and s k roughly the same length, namely,half the length of q.Taking the above equation modulo q we have

r i≡s iαc(mod q)

and hence

logαr i=logαs i+c(mod q?1).

Now instead of checking if y=αc mod q is B-smooth,we check if r k and s k are simultaneously B-smooth.It turns out that it is much more likely that these two smaller integers are simultaneously B-smooth than y is.Moreover, we will usually only have to check one of r k and s k,because if,say,r k is not B-smooth,then we don’t care about this(r k,s k)pair.Furthermore,the pairs

(r k?2,s k?2),(r k?1,s k?1),and(r k+1,s k+1)

obtained from the Euclidean algorithm will also have integers close to half the length of q in size.

Note also that the sequence s i alternate from positive to negative,and so one must add the integer?1to the factor base,B.As well,we don’t need to continue the EEA past i=k+1as we don’t make use of any of those stly,note that we don’t need to explicitly compute the t i values.

3.4Maple Implementation and Timings

The e?ciency of the algorithm now depends on how fast we can test if an integer y is B-smooth.The basic test to see if r i(or s i)is B-smooth is to trial-divide by the primes in B in a loop.However,since large primes are far less likely to divide the values r i than small primes,we handle these di?erently.For small primes in B we use a traditional trial division loop. For the larger primes in B we perform a gcd calculation with a product of a certain number of them with whatever is left of r i.If this gcd is1then we

can skip a bunch of trial divisions.Through experimentation,we found that taking products of twenty large primes at a time and computing the gcd with r i produced the best gains.

Lastly,a word on the storage of the system of linear congruences.The congruences will be sparse,having typically O(log r i)non-zero terms,thus we store the congruences as polynomials rather than in matrix form.Taking advantage of the sparsity of the system will also allow us to make gains in calculating its solution.

With all of these tricks to speed up our Maple implementation of the index calculus algorithm,we?nd that two thirds of the time is spent on the Euclidean algorithm step for calculating the(r i,s i)pairs.This suggests that there is not much else we can do to speed up our Maple implementation unless we adopt another algorithm or code parts of it in C.Below we show timings (in seconds on a2.0GHz AMD64bit Opteron)which pit Maple’s current mlog command against our implementation of the index calculus algorithm for increasing choices of a prime q having a large prime dividing q?1(in fact all choices were with q=2p+1with p also prime).

log2q Maple’s mlog Index Calculus

200.0090.17

250.0380.314

300.3240.587

35 2.744 1.632

4021.539 2.97

45164.565 4.572

501815.2728.603

5527978.41118.345

6045.756

65114.607

70303.185

75606.303

801875.977

855278.757

909690.946

9522124.051

Table2:Discrete logarithm timings(in CPU seconds)

References

[1]W.Alford and C.Pomerance,Implementing the Self-Initializing

Quadratic Sieve on a distributed network,in A.J.van der Poorten,I.Sh-parlinski,and H.G.Zimmer(eds),“Number theoretic and algebraic meth-ods in computer science”(1995),163–174.

[2]I.F.Blake,R.Fuji-Hara,R.C.Mullin,and put-

ing logarithms in?nite?elds of characteristic two,SIAM J.Alg.Disc.

Methods,5(1984),276–285.

[3]R.P.Brent,An improved Monte Carlo factorization algorithm,BIT20

(1980),176–184.

[4]E.R.Can?eld,P.Erdos,and C.Pomerance.On a problem of Oppenheim

concerning‘factorisatio numerorum’,J.Number Theory,17(1983),1–28.

[5]S.P.Contini,Factoring integers with the Self-Initializing Quadratic Sieve,

MA thesis,University of Georgia(1997).

[6]A.J.Menezes,P.C.van Oorschot,and S.A.Vanstone.Handbook of

Applied Cryptography,CRC Press,(1996).ISBN0-8493-8523-7

[7]M.B.Monagan,K.O.Geddes,K.M.Heal,bahn,S.M.Vorkoetter,