diff options
Diffstat (limited to 'lib/ssh/src/ssh_math.erl')
-rw-r--r-- | lib/ssh/src/ssh_math.erl | 96 |
1 files changed, 3 insertions, 93 deletions
diff --git a/lib/ssh/src/ssh_math.erl b/lib/ssh/src/ssh_math.erl index 4aa385b18d..e05964daa1 100644 --- a/lib/ssh/src/ssh_math.erl +++ b/lib/ssh/src/ssh_math.erl @@ -1,7 +1,7 @@ %% %% %CopyrightBegin% %% -%% Copyright Ericsson AB 2005-2011. All Rights Reserved. +%% Copyright Ericsson AB 2005-2013. 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 @@ -23,109 +23,19 @@ -module(ssh_math). --export([ilog2/1, ipow/3, invert/2, ipow2/3]). +-export([ipow/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). - + crypto:binary_to_integer(crypto:mod_pow(A, B, M)). -%% %% -%% %% 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. |