From: hb3@aixterm5.urz.uni-heidelberg.de (Franz Lemmermeyer) Newsgroups: sci.math Subject: Re: Factorising numbers Date: 24 Feb 1995 10:33:59 GMT In article <793557609snz@wincoll.demon.co.uk>, twomack@wincoll.demon.co.uk ("Thomas O. Womack") writes: |> OK : this is possibly one for sci.crypt. On reading through their articles |> about the security of RSA codes (based on the difficulty of factorisation), |> I found references to the 'number field sieve', the 'multiple polynomial |> quadratic sieve', and the 'elliptic curve' method of factorisation. I'd |> quite like to implement these, just to see what happens; however, I couldn't |> find any references to the number field sieve even in the neighbourhood |> university library, and the references I found for the other two were |> utterly incomprehensible. |> Has anyone got the algorithms for these? More difficult, does anyone |> know why they work? I am an A-level student with Maths and Further Maths, |> have read Davenport on number theory and the like; are these algorithms |> likely to be far above my head? If so, post them anyway - someone must |> understand them!? It's probably best to start with the theory of Pollard's p-1-method and Brillhart's continued-fraction method: they are the father's of the elliptic curve and the number field sieve method, respectively. The latter is described in a recent article in Math. Comp. on the factorization of F_9. Davenport's book is sufficient for an understanding of p-1 and CF; for elliptic curves, take a look at the book of Koblitz on these matters. franz `&' ******************************************************** # Franz Lemmermeyer ** Die endgueltige * # Erwin-Rohde-Str. 19 ** Teilung * _#_ 69120 Heidelberg ** Deutschlands, * ( # ) ** das ist unser * / O \ hb3@ix.urz.uni-heidelberg.de ** Auftrag! * ( === ) ***** Chlodwig Poth **** `---' ******************************************************** ============================================================================== From: strauch@emmy.mathematik.uni-dortmund.de (Michael Strauch) Newsgroups: sci.math Subject: Re: Factorising numbers Date: 24 Feb 1995 12:36:56 GMT Thomas O. Womack (twomack@wincoll.demon.co.uk) wrote: > OK : this is possibly one for sci.crypt. On reading through their articles > about the security of RSA codes (based on the difficulty of factorisation), > I found references to the 'number field sieve', the 'multiple polynomial > quadratic sieve', and the 'elliptic curve' method of factorisation. I'd > quite like to implement these, just to see what happens; however, I couldn't > find any references to the number field sieve even in the neighbourhood > university library, and the references I found for the other two were > utterly incomprehensible. > Has anyone got the algorithms for these? More difficult, does anyone > know why they work? I am an A-level student with Maths and Further Maths, > have read Davenport on number theory and the like; are these algorithms > likely to be far above my head? If so, post them anyway - someone must > understand them!? A few months ago the second edition of Hans Riesel's book "Prime Numbers and Computer Methods for Factorization" has been published. If I remember correctly, this new edition contains a description of NFS, MPQS, and ECM. ECM and MPQS can be understood with basic knowledge of algebra and elmentary number theory. NFS is much harder to understand, you will need some experience in algebraic number theory. - Michael - -- *************************************************************************** * Michael Strauch * email: * * University of Dortmund * strauch@emmy.mathematik.uni-dortmund.de * * Department of mathematics * * *************************************************************************** ============================================================================== From: robert@cs.caltech.edu (Robert J. Harley) Newsgroups: sci.math Subject: Re: Factorising numbers Date: 25 Feb 1995 18:56:21 GMT twomack@wincoll.demon.co.uk writes: >[...] >I found references to the 'number field sieve', the 'multiple polynomial >quadratic sieve', and the 'elliptic curve' method of factorisation. I'd >quite like to implement these, just to see what happens; [...] For ECM and QS, there are very clear explanations (with code) in : "Factorization and primality testing" by David M. Bressoud, New York : Springer-Verlag, c1989, UTM series. Another good source is: "Prime numbers and computer methods for factorization" by Hans Riesel, Boston : Birkhauser, c1994, Progress in mathematics #126. The NFS is rather harder to understand but there is an easy explanation of a special case by J.M. Pollard at the beginning of: "The development of the number field sieve" by A.K. & H.W. Lenstra (eds.), Berlin ; New York : Springer-Verlag, c1993, LNM #1554. Bye, Rob. .-. robert@vlsi.cs.caltech.edu .-. / \ .-. .-. / \ / \ / \ .-. _ .-. / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / `-' `-' \ / \ / \ \ / `-' `-' \ / `-' Question all you are. `-'