home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / programm / 3619 < prev    next >
Encoding:
Internet Message Format  |  1993-01-28  |  1.5 KB
  1. Path: sparky!uunet!europa.eng.gtefsd.com!paladin.american.edu!news.univie.ac.at!hp4at!mcsun!sun4nl!cwi.nl!dik
  2. From: dik@cwi.nl (Dik T. Winter)
  3. Newsgroups: comp.programming
  4. Subject: Re: how about PRIME numbers ?
  5. Message-ID: <8752@charon.cwi.nl>
  6. Date: 28 Jan 93 02:21:48 GMT
  7. References: <peterd.727578786@tscc2> <1jvfnq$rvn@agate.berkeley.edu> <4671@sicsun.epfl.ch>
  8. Sender: news@cwi.nl
  9. Organization: CWI, Amsterdam
  10. Lines: 21
  11.  
  12. In article <4671@sicsun.epfl.ch> guglielmetti@elia.epfl.ch (Philippe Guglielmetti) writes:
  13.  > about primes, I've read somewhere that it is possible to check if a
  14.  > really large "candidate" number like 2^245-1 is prime or not in a
  15.  > reasonable time
  16. Yup.  A few minutes for a number in that range.  The actual technique takes
  17. a bit more space to explain.
  18.  > 
  19.  > I remember that this what makes modern "revealed key encryption" feasible
  20.  > since the public key is the the product of 2 large prime numbers (which
  21.  > form the private key used in decryption).
  22. Actually it is in general not really necessary that both components are
  23. primes.  Being strong pseudo-primes will also help.  But you are less
  24. secure, and communication might fail.
  25.  
  26.  >                                            If I understood correctly, it
  27.  > was formally prooved that no polynomial time algorithm exists to
  28.  > decompose a number in its prim e factor...
  29. There is no formal proof.  But it is widely believed.
  30. -- 
  31. dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland
  32. home: bovenover 215, 1025 jn  amsterdam, nederland; e-mail: dik@cwi.nl
  33.