From: bobs@mathworks.com (Bob Silverman) Newsgroups: sci.math,sci.crypt Subject: Re: Factorization Algorithms Wanted Date: 4 Sep 1995 19:43:46 -0400 In article <42egrm$hrt@goanna.cs.rmit.edu.au>, Adam Frey wrote: >Hi. > >I am involved in a small project which aims to compare the performance of ^^^^^ I estimate that it would be a minimum of 8 months of full time work to implement all of the algorithms you have outlined below. That is the time it would take ME to recode all my stuff from scratch. It would take a novice much longer; this is not a "small" project. Further, in order to get effective performance measurements from the Number Field Sieve, you need to do benchmarks on (at a minimum) 90-100 digit numbers. This requires large amounts of computer time. For the other algorithms you can get effective measurements in a few 10's of hours on a fast workstation. >I intend to measure the performance of some or all of: > Naive Algorithm I assume you mean trial division? > Number Field Sieve > Multiple Polynomial Method Multiple Polynomials for what? There is no such thing as the "multiple polynomial method" by itself. You can use multiple polynomials for either QS or NFS, but since you list those separately, I assume you mean something else here. Perhaps I can help clear up any confusion. > Quadratic Sieve > Eliptic Curve > A hueristic method I would be interested in hearing about this. What do you have in mind? > >Before I go ahead and research and implement the above, I thought I would >ask if anyone has code or algorithm outlines for them. The best papers (In my obviously biased opinion) on QS and ECM can be found in the Jan. 1987 issue of Mathematics of Computation. The issue dedicated to Dan Shanks. One is by Peter Montgomery (a superb paper) the other is by me. Implementation of other methods is described in: D. Bressoud, Factorization & Primality Testing, Springer-Verlag, Undergrad Texts in Math. Implementation of the Number Field Sieve is discussed across many scattered papers; many of the nitty gritty implementation details are not in print. I suggest you forget about the number field sieve. There is too much code involved. You need code for: (1) Roots of polynomials over finite fields (to compute the factor base and sieve starting points) (2) Sieving code which has multiple pieces; besides the sieve you need code to evaluate the polynomials , factor their values (perhaps with multiple large primes) etc. (3) Code to find cycles in a graph (to combine the large primes) as well as code to distinguish large primes of the same norm but with different ideal generators (4) Code to find quadratic signatures (5) Code to build and solve a very large (100K x 100K and up) bit matrix over GF(2) (6) Code to compute square roots of an algebraic number which is represented as product of a large number of prime ideals (7) Code to multiply out the congruences at the end and produce the factorization It is a LOT of code, and requires quite a bit of knowledge about algebraic number theory. Even the special number field sieve requires a lot of code. Much of what you need is presented in scattered papers. Indeed, I'm not even sure whether Peter Montgomery's fast method for finding the algebraic square root has appeared in print yet. -- Bob Silverman The MathWorks Inc. 24 Prime Park Way Natick, MA ============================================================================== From: pcl@sable.ox.ac.uk (Paul Leyland) Newsgroups: sci.math,sci.crypt Subject: Re: Factorization Algorithms Wanted Date: 10 Sep 1995 16:28:04 GMT Let's get this out of the way first. DISCLAIMER --- apart from a few of bug fixes and some contributed efficiency hacks, I didn't write much this software, so give credit where it's due (primarily to Arjen Lenstra). In article <42ppd2$aqm@puff.mathworks.com> bobs@mathworks.com (Bob Silverman) writes: > In article , Adam Back wrote: > >Don't suppose anyone has any code available to kick start some of > >these things? I thought it would be fun to have a look at a few of > >these algorithms to get an understanding of how they work, but the > > I think that you can get a better understanding of how the > algorithms work and how they are implemented from reading the papers > about them, rather than the code. The code would just be a "black box". Personally, I find studying code and tutorial material (Riesel, Knuth, etc) helpful, as well as reading the papers. I'm probably dimmer than many people in this field and I find multiple restatements of the ideas make it easier for me to comprehend what's going on. > If I may suggest: If you already have a multi-precision library, why > don't you implement Pollard P-1, P+1, Pollard Rho, and SQUFOF? You > might also try implementing step 1 of ECM. These would be reasonable > to do in a small project. > > >Would help reduce duplicated effort if the various people into > >factoring donated their code to the public domain. Deletia > Also, researchers in the field do borrow code from one another; I have > given my QS code to others in exchange for some of their code, etc. > But it *usually* is an exchange. While we are all colleagues working > on a common problem, we are still in some sense "competitors". More deletia. > >Fair enough. Nice to see the code, and learn how NFS works anyway > >tho. The problem with some of these is that you need a large matrix > > But you won't learn how NFS works from reading the code. > Of all the modern factoring algorithms, NFS would be the most difficult > to figure out from the code; you have to learn the math behind it. I can confirm this. I've seen both Silverman's and Lenstra's code and, frankly, I found it almost incomprehensible. I'm busy ploughing through the literature to see how it is supposed to work. That is beginning to make sense, so I'll take a look at the code in detail in a while. For the moment, it's a black box. Yet more deletia. > >Any one interested in collecting all of the code which must surely be > >out there together somewhere? There's no end of multi-precision maths > >libraries around, gmp, lip, pari, etc. but little code using them. > > There is lots of code using them. But most of it is "research code". > And there is little payoff to making it available to the general public. There is even some public code. See below. > Just to cite some examples: On several occasions I have given out code > which checks for Mersenne primes. I did so with assurances from the > other party(s) involved that they were going to run the code to fill > in some gaps in the search. There are exponents less than the current > record that have not been checked. Once I gave out the code, I did > not hear from those people again. On another occasion I gave out my > QS program with the understanding that the person was going to factor > some numbers with it that I wanted factored and which were within the > CPU resources claimed by the other party. I was busy working on > "more wanted" factorizations. These were what are now called "smaller > but needed" numbers. I never heard from that person again either. > > So I now only give out code to: > > (1) Fellow researchers > (2) Mathematicians/Computer Scientists whom I know about by reputation > but not necessarily personally. > (3) People who are vouched for by someone I know personally or whom I > respect because of reputation. > (4) People whom I believe know enough math to be able to implement the > algorithms on their own, but just don't have the time. > > There is an old addage about "Once bitten, twice shy". Here's my offer. It doesn't cost me much, because the code has been given to me to redistribute anyway. I'll offer you full implementations of ECM, SQUFOF and Pollard Rho. I'll throw in Miller-Rabin pseudoprimality testing. I'll chuck in the sieving half of ppmpqs as well. In return, you have to write the relation-processing and matrix solver code for ppmpqs and make that available under a license no more restrictive than the GPL. I am, of course, cheating, as it costs me very little. Lenstra's freeLIP package gives you the multiprecision package and the algorithms mentioned other than the ppmpqs siever. The latter is given away free with the RSA-129 project software. Both are available by anon-ftp from ftp.ox.ac.uk and you should take a rummage around in the /pub/math sub-directories. You will also find a vast amount of test data and research problesm there -- the Cunningham project files for instance. That sounds like a bargain to me! Another source of free software: get UBASIC and its libraries. If you don't like having run it under MSDOS, contribute to the community by translating the code into high quality C and make that available (but check with the author first!) Paul -- Paul Leyland | Hanging on in quiet desperation is Oxford University Computing Services | the English way. 13 Banbury Road, Oxford, OX2 6NN, UK | The time is gone, the song is over. Tel: +44-1865-273200 Fax: 273275 | Thought I'd something more to say. Finger pcl@sable.ox.ac.uk for PGP key |