home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / crypt / 7103 < prev    next >
Encoding:
Internet Message Format  |  1993-01-23  |  1.9 KB
  1. Path: sparky!uunet!olivea!pagesat!netsys!agate!linus!linus.mitre.org!gauss!bs
  2. From: bs@gauss.mitre.org (Robert D. Silverman)
  3. Newsgroups: sci.crypt
  4. Subject: Re: References for number field sieve (was Re: Oh yeah?  Factor this...)
  5. Message-ID: <1993Jan22.211630.14433@linus.mitre.org>
  6. Date: 22 Jan 93 21:16:30 GMT
  7. References: <1993Jan22.004018.2036@csi.uottawa.ca> <1993Jan22.013643.10520@linus.mitre.org> <PC123.93Jan22192804@bootes.cus.cam.ac.uk>
  8. Sender: news@linus.mitre.org (News Service)
  9. Distribution: na
  10. Organization: Research Computer Facility, MITRE Corporation, Bedford, MA
  11. Lines: 27
  12. Nntp-Posting-Host: gauss.mitre.org
  13.  
  14. In article <PC123.93Jan22192804@bootes.cus.cam.ac.uk> pc123@cus.cam.ac.uk (Pete Chown) writes:
  15. :In article <1993Jan22.013643.10520@linus.mitre.org> bs@gauss.mitre.org (Robert D. Silverman) writes:
  16. :
  17. :   The Number Field Sieve [on some reasonable unproved assumptions] takes
  18. :   exp( (c + o(1))  (log N)^1/3  (log log N)^2/3)
  19. :   with c ~ 1.91
  20. :
  21. :Does anyone have a reference for any articles or books on the number
  22. :field sieve?  I would quite like to see how they have done it.
  23.                          ^^^^           ^^
  24.  
  25. The antecedent of the pronoun "they" is unclear to me. To whom do
  26. you refer? And what is "it"? Derived the asymptotic run time? Or
  27. are you asking how the algorithm works?
  28.  
  29. I gave a reference in the bibliography I just posted. The paper 
  30. assumes quite a lot of background in algebraic number theory and
  31. knowledge of the quadratic sieve [they do not explain sieving
  32. procedures]. It also assumes you know a lot of general techniques
  33. in computational number theory, e.g. the Cantor-Zassenhaus method
  34. for factoring polynomials modulo primes, etc. etc. It is a really
  35. excellent paper, but novices will have a rough time with it.
  36. --
  37. Bob Silverman
  38. These are my opinions and not MITRE's.
  39. Mitre Corporation, Bedford, MA 01730
  40. "You can lead a horse's ass to knowledge, but you can't make him think"
  41.