Bignum arithmetic

[Sean Hinde]

On Monday, May 19, 2003, at 04:23 PM, Vladimir Sekissov wrote:

> Good day,
>
> sean.hinde> > 2^BigNumber mod ReasonableNumber, then there's no need to
> sean.hinde> > calculate 2^BigNumber.
> sean.hinde>
> sean.hinde> Aha! Any pointers on how to do this?
>
> Volume 2 of Donald Knuth's "The Art of Computer Programming" is now
> your best friend.
>
> Or search google with "arbitrary precision arithmetic".
>

Thanks. Here's what turned up. Translated from C:

% Calculate  M ^ P mod Q
modexp(M, P, Q) ->
     modexp(M, P, Q, 1).

modexp(M, 0, Q, Z) ->
     Z;
modexp(M, P, Q, Z) ->
     Z1 = if ((P band 1) == 1) ->
		 Z * M rem Q;
	    true ->
		 Z
	 end,
     M1 = M * M rem Q,
     P1 = P bsr 1,
     modexp(M1, P1, Q, Z1).

Cheers,
Sean