home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / programm / 3606 < prev    next >
Encoding:
Internet Message Format  |  1993-01-27  |  1.2 KB
  1. Path: sparky!uunet!math.fu-berlin.de!ira.uka.de!scsing.switch.ch!sicsun!iamace9.epfl.ch!guglielmetti
  2. From: guglielmetti@elia.epfl.ch (Philippe Guglielmetti)
  3. Newsgroups: comp.programming
  4. Subject: Re: how about PRIME numbers ?
  5. Message-ID: <4671@sicsun.epfl.ch>
  6. Date: 26 Jan 93 17:09:18 GMT
  7. References: <peterd.727578786@tscc2> <1jvfnq$rvn@agate.berkeley.edu>
  8. Sender: news@sicsun.epfl.ch
  9. Organization: IA-DME-EPFL
  10. Lines: 16
  11. X-UserAgent: Nuntius v1.1.1d11
  12. X-XXMessage-ID: <A78B307C03017B20@iamace9.epfl.ch>
  13. X-XXDate: Tue, 26 Jan 93 18:16:28 GMT
  14.  
  15. Hi!
  16. about primes, I've read somewhere that it is possible to check if a
  17. really large "candidate" number like 2^245-1 is prime or not in a
  18. reasonable time using "congruence", without generating all the primes and
  19. without looking for divisors (which is roughly equivalent) but I didn't
  20. really understood how it worked in practice. Does anyone have code for
  21. this ?
  22.  
  23. I remember that this what makes modern "revealed key encryption" feasible
  24. since the public key is the the product of 2 large prime numbers (which
  25. form the private key used in decryption).  If I understood correctly, it
  26. was formally prooved that no polynomial time algorithm exists to
  27. decompose a number in its prim e factor...
  28.  
  29.  
  30. Ph. Guglielmetti
  31.