# hipow(a,n,m) = a^n mod m computed in 2log_2(n) time using a minimal
#    number of squarings (mod m) and multiplications by a (mod m) based
#    upon the 2-adic expansion of the exponent n.
hipow := proc(a,n,m) local t,u,j,r,s,c;
t := convert(n, base, 2);
# print(`t-array`,t);
r := nops(t);
if (r < 1) then ERROR(`t-array has length 0`) fi;
if (r < 2) then print(`CAUTION: t-array has length 1, exponent 0 or 1?`) fi;
s := r-1;
u := array(0..s);
u[0] := a;
for j from 1 to s do u[j] := u[j-1]^2 mod m od;
# print(`u-array`,u);
c := 1;
for j from 1 to r do
if t[j] = 1 then c := c*u[j-1] mod m fi;
od;
RETURN(c)
end:

# w := menc(v,n,m) returns the vector  v[j]^n mod m  computed fast
#                  (in 2log_2(n) time) for each j  using  hipow(v[j],n,m)

menc := proc(v,n,m) local a,t;
t := linalg[vectdim](v);
if not t > 0 then print(`menc: First argument is not a vector`); RETURN fi;
map(hipow, v, n, m)
end:

`hipow, menc defined`;