diff options
Diffstat (limited to 'lib/ssh/src/ssh_math.erl')
| -rw-r--r-- | lib/ssh/src/ssh_math.erl | 74 |
1 files changed, 9 insertions, 65 deletions
diff --git a/lib/ssh/src/ssh_math.erl b/lib/ssh/src/ssh_math.erl index 4aa385b18d..e4610377f8 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,8 +23,8 @@ -module(ssh_math). --export([ilog2/1, ipow/3, invert/2, ipow2/3]). - +-export([ipow/3]). +-export([ilog2/1, invert/2, ipow2/3]). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% @@ -32,20 +32,17 @@ %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%% 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). +ilog2(N) -> + ssh_bits:isize(N) - 1. ipow2(A, B, M) when M > 0, B >= 0 -> if A == 1 -> - 1; + 1; true -> - ipow2(A, B, M, 1) + ipow2(A, B, M, 1) end. ipow2(A, 1, M, Prod) -> @@ -56,50 +53,11 @@ ipow2(A, B, M, Prod) -> B1 = B bsr 1, A1 = (A*A) rem M, if B - B1 == B1 -> - ipow2(A1, B1, M, Prod); + ipow2(A1, B1, M, Prod); true -> - ipow2(A1, B1, M, (A*Prod) rem M) + 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 @@ -113,19 +71,5 @@ inv(X,P,R1,Q1) -> 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. |