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.             `-'