home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / crypt / 2733 < prev    next >
Encoding:
Internet Message Format  |  1992-07-24  |  1.7 KB
  1. Path: sparky!uunet!cs.utexas.edu!sun-barr!ames!elroy.jpl.nasa.gov!swrinde!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!ucbvax!virtualnews.nyu.edu!brnstnd
  2. From: brnstnd@nyu.edu (Dan Bernstein)
  3. Newsgroups: sci.crypt
  4. Subject: New record non-networked factorization of difficult number
  5. Message-ID: <9117.Jul2414.50.2192@virtualnews.nyu.edu>
  6. Date: 24 Jul 92 14:50:21 GMT
  7. Organization: IR
  8. Lines: 29
  9. X-Reposting-Note: article munged in first distribution; trying again
  10.  
  11. Arjen Lenstra and I are pleased to announce the record non-networked
  12. factorization of a difficult number (no prime factors under 40 digits).
  13. The number is (2^488 + 1)/257. Its prime factors are p_49 and p_97,
  14. where
  15.   
  16.   p_49 = 1035817877926014488587133818491976759389034764353
  17.  
  18. and
  19.  
  20.   p_97 = 3002073757428777382273857922385512797763792723266417656025\
  21.      021527116989779952950182556537541850817.
  22.  
  23. We carried out the bulk of the computation in under ten days on a MasPar
  24. SIMD computer with 16384 processors at Bellcore. We also used under a
  25. day of CPU time on a DEC workstation. The entire factorization took
  26. approximately a month and a half real time.
  27.  
  28. This should be compared with the overall record factorization of a
  29. difficult number, namely 2^512 + 1, which took four months real time on
  30. approximately 700 workstations around the world, together with a
  31. 65536-processor Connection Machine in one stage.
  32.  
  33. This computation can be seen as a substantial step towards a practical
  34. implementation of the general number field sieve (GNFS): it depended on
  35. character columns and a square root inside the algebraic number field
  36. rather than explicit generators of the unit group and of prime ideals of
  37. the field. We are investigating the practical effectiveness of GNFS.
  38.  
  39. ---Dan
  40.