home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / programm / 3621 < prev    next >
Encoding:
Internet Message Format  |  1993-01-28  |  2.4 KB
  1. Path: sparky!uunet!math.fu-berlin.de!uni-paderborn.de!urmel.informatik.rwth-aachen.de!gmd.de!newsserver.jvnc.net!netnews.upenn.edu!netnews.cc.lehigh.edu!ns1.cc.lehigh.edu!mal4
  2. From: mal4@ns1.cc.lehigh.edu (Marty Lamb)
  3. Newsgroups: comp.programming
  4. Subject: Re: how about PRIME numbers ?
  5. Message-ID: <1993Jan27.175613.62630@ns1.cc.lehigh.edu>
  6. Date: 27 Jan 93 17:56:13 GMT
  7. Organization: Lehigh University
  8. Lines: 52
  9.  
  10. In article <4671@sicsun.epfl.ch>, guglielmetti@elia.epfl.ch (Philippe Guglielmet
  11. ti) writes:
  12. >Hi!
  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 using "congruence", without generating all the primes and
  16. >without looking for divisors (which is roughly equivalent) but I didn't
  17. >really understood how it worked in practice. Does anyone have code for
  18. >this ?
  19. >
  20.  
  21. I haven't got code, but it's a simple (or at least simply implemented)
  22. algorithm.  I have ABSOLUTELY NO IDEA why it works, so if anyone does I'm sure
  23. it's interesting enough to post.
  24.  
  25. A number of the form 2^p - 1 (p is an integer) is called a Mersenne Number,
  26. after the mathematician whose first name currently escapes me.  The algorith
  27. goes like this:
  28.  
  29.      p = exponent to test
  30.      MersenneNumber = 2^p - 1
  31.  
  32.      Start with L = 4
  33. |--> set L = L^2 - 2 MOD MersenneNumber  -----|
  34. |<----- do this p - 2 times <-----------------|
  35.      If L = 0 then the Mersenne Number is prime.
  36.  
  37. It's amazingly quick, with the HUGE disadvantage that you have to calculate
  38. the Mersenne Number, although I suppose a clever MOD subroutine might be able
  39. to bypass that.
  40.  
  41.  
  42. >I remember that this what makes modern "revealed key encryption" feasible
  43. >since the public key is the the product of 2 large prime numbers (which
  44. >form the private key used in decryption).  If I understood correctly, it
  45. >was formally prooved that no polynomial time algorithm exists to
  46. >decompose a number in its prim e factor...
  47. >
  48. >
  49. >Ph. Guglielmetti
  50. >
  51.  
  52.  
  53. Marty Lamb
  54. -- 
  55.  
  56.  ___________________________________________________________________________
  57. /-------------------------------------------------------------------------/|
  58. |  Be like the 22nd elephant with     |     Marty Lamb   (215)758-1921    ||
  59. |  heated value in space.   Bark!     |     Box 0151                      ||
  60. |--------------------------------------     Lehigh University             ||
  61. |  mal4@lehigh.edu                    |     29 Trembley Dr.               ||
  62.