%%
%% %CopyrightBegin%
%%
%% Copyright Ericsson AB 2005-2009. All Rights Reserved.
%%
%% The contents of this file are subject to the Erlang Public License,
%% Version 1.1, (the "License"); you may not use this file except in
%% compliance with the License. You should have received a copy of the
%% Erlang Public License along with this software. If not, it can be
%% retrieved online at http://www.erlang.org/.
%%
%% Software distributed under the License is distributed on an "AS IS"
%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
%% the License for the specific language governing rights and limitations
%% under the License.
%%
%% %CopyrightEnd%
%%
%%
%%% Description: SSH math utilities
-module(ssh_math).
-export([ilog2/1, ipow/3, invert/2, ipow2/3]).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% INTEGER utils
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% number of bits (used) in a integer = isize(N) = |log2(N)|+1
ilog2(N) ->
ssh_bits:isize(N) - 1.
%% calculate A^B mod M
ipow(A, B, M) when M > 0, B >= 0 ->
crypto:mod_exp(A, B, M).
ipow2(A, B, M) when M > 0, B >= 0 ->
if A == 1 ->
1;
true ->
ipow2(A, B, M, 1)
end.
ipow2(A, 1, M, Prod) ->
(A*Prod) rem M;
ipow2(_A, 0, _M, Prod) ->
Prod;
ipow2(A, B, M, Prod) ->
B1 = B bsr 1,
A1 = (A*A) rem M,
if B - B1 == B1 ->
ipow2(A1, B1, M, Prod);
true ->
ipow2(A1, B1, M, (A*Prod) rem M)
end.
%% %%
%% %% Normal gcd
%% %%
%% gcd(R, Q) when abs(Q) < abs(R) -> gcd1(Q,R);
%% gcd(R, Q) -> gcd1(R,Q).
%% gcd1(0, Q) -> Q;
%% gcd1(R, Q) ->
%% gcd1(Q rem R, R).
%% %%
%% %% Least common multiple of (R,Q)
%% %%
%% lcm(0, _Q) -> 0;
%% lcm(_R, 0) -> 0;
%% lcm(R, Q) ->
%% (Q div gcd(R, Q)) * R.
%% %%
%% %% Extended gcd gcd(R,Q) -> {G, {A,B}} such that G == R*A + Q*B
%% %%
%% %% Here we could have use for a bif divrem(Q, R) -> {Quote, Remainder}
%% %%
%% egcd(R,Q) when abs(Q) < abs(R) -> egcd1(Q,R,1,0,0,1);
%% egcd(R,Q) -> egcd1(R,Q,0,1,1,0).
%% egcd1(0,Q,_,_,Q1,Q2) -> {Q, {Q2,Q1}};
%% egcd1(R,Q,R1,R2,Q1,Q2) ->
%% D = Q div R,
%% egcd1(Q rem R, R, Q1-D*R1, Q2-D*R2, R1, R2).
%%
%% Invert an element X mod P
%% Calculated as {1, {A,B}} = egcd(X,P),
%% 1 == P*A + X*B == X*B (mod P) i.e B is the inverse element
%%
%% X > 0, P > 0, X < P (P should be prime)
%%
invert(X,P) when X > 0, P > 0, X < P ->
I = inv(X,P,1,0),
if
I < 0 -> P + I;
true -> I
end.
inv(0,_,_,Q) -> Q;
inv(X,P,R1,Q1) ->
D = P div X,
inv(P rem X, X, Q1 - D*R1, R1).
%% %%
%% %% Integer square root
%% %%
%% isqrt(0) -> 0;
%% isqrt(1) -> 1;
%% isqrt(X) when X >= 0 ->
%% R = X div 2,
%% isqrt(X div R, R, X).
%% isqrt(Q,R,X) when Q < R ->
%% R1 = (R+Q) div 2,
%% isqrt(X div R1, R1, X);
%% isqrt(_, R, _) -> R.
