🚀 go-pugleaf

Rudy Crespin (crespin@nadir.uucp) wrote:
: Yes! I still don't get how you figure out 133^235 without blowing up your PC.

You needn't calculate 133^235, only 133^235 mod 391.
First you can use square-and-multiply (see Knuth, Vol 2):
133^235 = 133^234*133 = (133^117)^2*133=(133^176*133)^2*133 = ...
 Then there is (a*b) mod m = (a mod m)*(b mod m), so instead of using
huge numbers, you can reduce modulo 391 every time, you have done a
square- or a multiply-step.
 For discussion of fast multiply-, square- and modulo-reduction-algorithms
again read D.E.Knuth, The art of computer programming, Vol 2.  There are
even faster algorithms for exponentiation than square-and-multiply, some of
which are also discussed in Knuth, Vol 2.

Joerg

--
Joerg Czeranski
Osteroeder Strasse 55          EMail injc@sun.rz.tu-clausthal.de
W-3392 Clausthal-Zellerfeld    SMTP  injc@[139.174.1.3]
Germany

PGP Public Key will soon be available upon request.

(.sig under construction, sorry for the inconvenience)