Rosetta Code

Modular exponentiation: Difference between revisions

Page Discussion

Modular exponentiation (view source)

Revision as of 20:02, 21 July 2021

402 bytes removed ,  2 years ago
factorised out function exp_factor to improve structure
m (added whitespace.)
(factorised out function exp_factor to improve structure)
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 rem Mod,Exponent,Mod,1).
 
binary_exp_mod(_,0,_,Result) ->
Result;
binary_exp_mod(Base,Exponent,Mod,Acc) ->
binary_exp_mod((Base,Exponent,*Base) rem Mod,Acc,Exponent band 1).
Exponent bsr 1,Mod,(Acc * exp_factor(Base,Exponent))rem Mod).
 
exp_factor(_,0) ->
binary_exp_mod(Base,Exponent,Mod,Acc,0) ->
▲ Result1;
binary_exp_mod((Base*Base) rem Mod,Exponent bsr 1,Mod,Acc);
binary_exp_modexp_factor(Base,Exponent,Mod,Acc,1) ->
Base;
binary_exp_mod((Base*Base) rem Mod,Exponent bsr 1,Mod,(Acc*Base) rem Mod).
▲binary_expexp_factor(Base,Exponent) ->
▲ binary_expexp_factor(Base,Exponent, band 1).
 
test() ->
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/210374"