Computes A^P (mod N) when A, P, and N are no larger than
2E13.  Uses Head's algorithm for mulitplication.



This program computes A^P (mod N) for large values of each
(A, P, and N must not exceed 2E13).

The program uses the included subroutine SuMult, which
multiplies X and Y (mod N) for numbers where X*Y is too
large for the calculator to store without losing the
less-significant digits.  SuMult uses Head's algorithm.

ModPower works by computing sucessive squares of A (mod N)
and concurrently performs a binary expansion of P.  The 
program uses these to compute A^P with only about 
2*log_2(P) multiplications.

For example, 3^21 = 3^(1+4+16) = 3*3^4*3^16, so computing
3^2, 3^4, 3^8, and 3^16 by iteratively squaring "3" does
most of the work.

Programs written by Prof. Mark Janeba, Dept. of Math,
Willamette Univ, Salem, OR 97301  
(internet: mjaneba@willamette.edu)

Reference:  Most number theory texts.