# MODPOWER --- computes powers mod n
 #
 # modpower( a, k, N) computes  a^k mod N
 # by the method of successive squaring.

 
 modpower := proc(a,k,N)
    local q, r, mp;
    r := k mod 2;
    q := (k-r)/2;
    if q = 0 
       then RETURN( a^r mod N );
    else
       mp := modpower(a,q,N);
       RETURN( mp^2*a^r mod N );
    fi;
 end:


 # jac, 6/11/2001