home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / crypt / 3018 < prev    next >
Encoding:
Internet Message Format  |  1992-08-26  |  1.9 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!ucbvax!virtualnews.nyu.edu!brnstnd
  2. From: brnstnd@nyu.edu (D. J. Bernstein)
  3. Newsgroups: sci.crypt
  4. Subject: Re: RSA-129 contest
  5. Message-ID: <18885.Aug2623.38.5292@virtualnews.nyu.edu>
  6. Date: 26 Aug 92 23:38:52 GMT
  7. References: <9208260234.AA05450@ucbvax.Berkeley.EDU>
  8. Organization: IR
  9. Lines: 36
  10.  
  11. In article <9208260234.AA05450@ucbvax.Berkeley.EDU> jbs@WATSON.IBM.COM writes:
  12. >          Well if you actually had a complete GFNS implementation for
  13. > general numbers I believe you would obtain more reliable estimates by
  14. > performing a whole bunch of "wimpy" factorizations as opposed to a
  15. > single factorization of RSA-129.
  16.  
  17. Unfortunately not. Example: Arjen Lenstra and I tried our MasPar GNFS
  18. implementation on a 66-digit general number. We used the smallest
  19. sensible factor bases for that architecture---namely 16384 primes on
  20. each side of the sieve---and without any tuning found that we had more
  21. than enough relations *from ff's alone*. No partials were necessary.
  22.  
  23. When you want to make predictions, the statistics from such a tiny
  24. factorization are worse than useless. One can safely predict how long
  25. GNFS will need to factor a 130-digit number---within an order of
  26. magnitude.
  27.  
  28. >          You might also have a reliable figure of merit for what con-
  29. > stitutes a good polynomial representation.
  30.  
  31. This is, unfortunately, an open research problem. The best procedure I
  32. know is to generate many polynomials with relatively small coefficients,
  33. then look for polynomials with ``many'' small algebraic primes in a
  34. certain sense. This is exactly what the RSA-129 contest is meant to
  35. achieve.
  36.  
  37. (For those who missed the start of the discussion: If your mail address
  38. is joe@foo.bar and you want to see the contest announcement, send mail
  39. to factor@src.dec.com with the two lines
  40.  
  41. path#joe@foo.bar
  42. rsastatus#
  43.  
  44. and wait a few minutes.)
  45.  
  46. ---Dan
  47.