Anonymous user
Montgomery reduction: Difference between revisions
→{{header|Tcl}}: added zkl
(→{{header|Racket}}: actual implementation added) |
(→{{header|Tcl}}: added zkl) |
||
Line 308:
}</lang>
<!-- Not quite sure how to demonstrate this working; examples above aren't very clear… -->
=={{header|zkl}}==
{{Trans|Go}}
Uses GMP (GNU Multi Precision library).
<lang zkl>var [const] BN=Import("zklBigNum"); // libGMP
fcn montgomeryReduce(modulus,T){
_assert_(modulus.isOdd);
bits:=modulus.len(2);
a:=BN(T); // we'll do in place math
foreach i in (bits){
if(a.isOdd) a.add(modulus);
a.div(2); // a>>=1
}
if(a>=modulus) a.sub(modulus);
a
}</lang>
<lang zkl> // magic numbers from the Go solution
//b:= 2;
//n:= 100;
//r:= BN("1267650600228229401496703205376");
m:= BN("750791094644726559640638407699");
t1:=BN("323165824550862327179367294465482435542970161392400401329100");
t2:=BN("308607334419945011411837686695175944083084270671482464168730");
r1:=BN("440160025148131680164261562101");
r2:=BN("435362628198191204145287283255");
x1:=BN("540019781128412936473322405310");
x2:=BN("515692107665463680305819378593");
// now demonstrate that it works:
println("Original x1: ", x1);
println("Recovererd from r1:",montgomeryReduce(m,r1));
println("Original x2: ", x2);
println("Recovererd from r2:", montgomeryReduce(m,r2));
// and demonstrate a use:
print("\nMontgomery computation of x1 ^ x2 mod m: ");
// this is the modular exponentiation algorithm, except we call
// montgomeryReduce instead of using a mod function.
prod:=montgomeryReduce(m,t1/x1); // 1
base:=montgomeryReduce(m,t1); // x1^1
exp :=BN(x2); // not reduced
while(exp){
if(exp.isOdd) prod=montgomeryReduce(m,prod.mul(base));
exp.div(2); // exp>>=1
base=montgomeryReduce(m,base.mul(base));
}
println(montgomeryReduce(m,prod));
println("Library-based computation of x1 ^ x2 mod m: ",x1.powm(x2,m));</lang>
{{out}}
<pre>
Original x1: 540019781128412936473322405310
Recovererd from r1:540019781128412936473322405310
Original x2: 515692107665463680305819378593
Recovererd from r2:515692107665463680305819378593
Montgomery computation of x1 ^ x2 mod m: 151232511393500655853002423778
Library-based computation of x1 ^ x2 mod m: 151232511393500655853002423778
</pre>
| |||