home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / sci / crypt / 6210 < prev    next >
Encoding:
Internet Message Format  |  1992-12-22  |  1.6 KB
  1. Xref: sparky sci.crypt:6210 alt.security.pgp:435
  2. Path: sparky!uunet!olivea!spool.mu.edu!yale.edu!ira.uka.de!Sirius.dfn.de!solaris.rz.tu-clausthal.de!sun.rz.tu-clausthal.de!injc
  3. From: injc@sun.rz.tu-clausthal.de (Joerg Czeranski)
  4. Newsgroups: sci.crypt,alt.security.pgp
  5. Subject: Re: RSA Question (was Re: PKP/RSA comments on PGP legality)
  6. Message-ID: <1992Dec27.171211.19260@solaris.rz.tu-clausthal.de>
  7. Date: 27 Dec 92 17:12:11 GMT
  8. References: <CkCNrAILBh107h@nadir.uucp>
  9. Sender: root@solaris.rz.tu-clausthal.de (Operator)
  10. Organization: Techn. Univ. Clausthal
  11. Lines: 25
  12. X-Newsreader: Tin 1.1 PL5
  13.  
  14. Rudy Crespin (crespin@nadir.uucp) wrote:
  15. : Yes! I still don't get how you figure out 133^235 without blowing up your PC.
  16.  
  17. You needn't calculate 133^235, only 133^235 mod 391.
  18. First you can use square-and-multiply (see Knuth, Vol 2):
  19. 133^235 = 133^234*133 = (133^117)^2*133=(133^176*133)^2*133 = ...
  20.  Then there is (a*b) mod m = (a mod m)*(b mod m), so instead of using
  21. huge numbers, you can reduce modulo 391 every time, you have done a
  22. square- or a multiply-step.
  23.  For discussion of fast multiply-, square- and modulo-reduction-algorithms
  24. again read D.E.Knuth, The art of computer programming, Vol 2.  There are
  25. even faster algorithms for exponentiation than square-and-multiply, some of
  26. which are also discussed in Knuth, Vol 2.
  27.  
  28. Joerg
  29.  
  30. --
  31. Joerg Czeranski
  32. Osteroeder Strasse 55          EMail injc@sun.rz.tu-clausthal.de
  33. W-3392 Clausthal-Zellerfeld    SMTP  injc@[139.174.1.3]
  34. Germany
  35.  
  36. PGP Public Key will soon be available upon request.
  37.  
  38. (.sig under construction, sorry for the inconvenience)
  39.