🚀 go-pugleaf

Pat_Barron@transarc.com writes:

>I was tinkering around with the RSA algorithm last night, using really
>small primes (e.g., 13 and 17) to generate keys.  The idea was that I
>only wanted to use a 16-bit modulus, so I could avoid doing any
>extended precision arithmetic, and so I could do the exponentation via
>a naive "compute x^y by looping and multiplying by x, y times
>(remember, this is just a toy implementation, and it's not intended
>to do any "real" work).  But I ran into a few snags:

>1)  During the exponentiation, the numbers get *really* big.  Like, I
>was shocked at how quickly they got big.  Is there any shortcut for
>computing m^e mod n, without actually computing m^e first?  Like, can
>I loop somehow, accumulating partial results, until at the end I have
>the value m^e mod n, without having actually computed m^e first?  Even
>if I choose, say, 3 or 5 as the private key, the public exponent tends
>to be big enough that m^e is way beyond the capacity of a 32-bit
>unsigned integer.

> [another RSA question ommitted]

There are already a few replies to your message giving better
ways to calculate z=x^y mod n.  But if all you want to do is simply
modify your original program, keeping your brute force expotentiation
method, then just do a modulus after each multiply.

I.E change your code that looks like

      Z:=1;
      FOR I:= 1 TO Y DO Z:= Z*X;

into
      Z:=1;
      FOR I:= 1 TO Y DO Z:= (Z*X) MOD N;

which will keep you from running into interactions with the implict
modulo that computer interger arithmatic involves.

you might even be able to stay within 16 bit integers and not have to
worry about 32 bits at all.