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

…… 此处隐藏0字 ……

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.

1