This runs in time O(Y) a better algorthim runs in time O(log(Y))
pow(A, B, M) computes A^B mod M. To compute this we proceed as follows: if B is even we compute pow(A, B div 2, M) and square the result (modulo M). If B is odd and greater than one we compute P = pow(A, (B-1)div 2, M) and then P*P*A mod M:
pow(A, 1, M) ->
A rem M;
pow(A, 2, M) ->
A*A rem M;
pow(A, B, M) ->
B1 = B div 2,
B2 = B – B1,
%% B2 = B1 or B1+1
P = pow(A, B1, M),
case B2 of
B1 -> (P*P) rem M;
_ -> (P*P*A) rem M
end.
joe armstrong - 2006-08-23 08:24:28
This runs in time O(Y) a better algorthim runs in time O(log(Y))
pow(A, B, M) computes A^B mod M. To compute this we proceed as follows: if B is even we compute pow(A, B div 2, M) and square the result (modulo M). If B is odd and greater than one we compute P = pow(A, (B-1)div 2, M) and then P*P*A mod M:
pow(A, 1, M) ->
A rem M;
pow(A, 2, M) ->
A*A rem M;
pow(A, B, M) ->
B1 = B div 2,
B2 = B – B1,
%% B2 = B1 or B1+1
P = pow(A, B1, M),
case B2 of
B1 -> (P*P) rem M;
_ -> (P*P*A) rem M
end.
Taken from http://www.erlang.org/examples/examples-2.0.html
Where you can also find functions for crypto arithmetic, testing primes, RSA etc.