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