Modular exponentiation: Difference between revisions

Content added Content deleted

Inline

@@ Line 466: / Line 466: @@
       Mod > 0 ->
     binary_exp_mod(Base,Exp,Mod).
-binary_exp(Base,Exponent) ->
-    binary_exp(Base,Exponent,1).
-binary_exp(_,0,Result) ->
-    Result;
-binary_exp(Base,Exponent,Acc) ->
-    binary_exp(Base,Exponent,Acc,Exponent band 1).
-binary_exp(Base,Exponent,Acc,0) ->
-    binary_exp(Base*Base,Exponent bsr 1,Acc);
-binary_exp(Base,Exponent,Acc,1) ->
-    binary_exp(Base*Base,Exponent bsr 1,Base*Acc).
 binary_exp_mod(Base,Exponent,Mod) ->
-    binary_exp_mod(Base,Exponent,Mod,1).
+    binary_exp_mod(Base rem Mod,Exponent,Mod,1).
 binary_exp_mod(_,0,_,Result) ->
    Result;
 binary_exp_mod(Base,Exponent,Mod,Acc) ->
-    binary_exp_mod(Base,Exponent,Mod,Acc,Exponent band 1).
+    binary_exp_mod((Base*Base) rem Mod,
+		   Exponent bsr 1,Mod,(Acc * exp_factor(Base,Exponent))rem Mod).
+exp_factor(_,0) ->
-binary_exp_mod(Base,Exponent,Mod,Acc,0) ->
+;
-    binary_exp_mod((Base*Base) rem Mod,Exponent bsr 1,Mod,Acc);
-binary_exp_mod(Base,Exponent,Mod,Acc,1) ->
+exp_factor(Base,1) ->
+    Base;
-    binary_exp_mod((Base*Base) rem Mod,Exponent bsr 1,Mod,(Acc*Base) rem Mod).
+exp_factor(Base,Exponent) ->
+    exp_factor(Base,Exponent band 1).
 test() ->