diff options
Diffstat (limited to 'lib/ssh/src/ssh_math.erl')
-rwxr-xr-x | lib/ssh/src/ssh_math.erl | 131 |
1 files changed, 131 insertions, 0 deletions
diff --git a/lib/ssh/src/ssh_math.erl b/lib/ssh/src/ssh_math.erl new file mode 100755 index 0000000000..efe7f56979 --- /dev/null +++ b/lib/ssh/src/ssh_math.erl @@ -0,0 +1,131 @@ +%% +%% %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. + + |