Montgomery reduction: Difference between revisions
m
šyntax highlighting fixup automation
Thundergnat (talk | contribs) m (šyntax highlighting fixup automation) |
|||
Line 20:
{{trans|Python}}
<
BigInt m
Int n
Line 77:
print(mont.reduce(prod))
print("\nAlternate computation of x1 ^ x2 mod m:")
print(pow(x1, x2, m))</
{{out}}
Line 103:
=={{header|C}}==
<
#include <stdlib.h>
Line 219:
return 0;
}</
{{out}}
<pre>b : 2
Line 243:
=={{header|C sharp|C#}}==
{{trans|D}}
<
using System.Numerics;
Line 334:
}
}
}</
{{out}}
<pre>b : 2
Line 357:
=={{header|C++}}==
<
#include<conio.h>
using namespace std;
Line 442:
cout<<"Montgomery domain representation = "<<e;
return 0;
}</
=={{header|D}}==
{{trans|Kotlin}}
<
import std.stdio;
Line 544:
writeln("\nAlternate computation of x1 ^ x2 mod m :");
writeln(x1.modPow(x2, m));
}</
{{out}}
<pre>b : 2
Line 569:
{{trans|Sidef}}
{{works with|Factor|0.99 2020-08-14}}
<
prettyprint ;
Line 606:
"Library-based computation of x1^x2 mod m: " write
x1 x2 m ^mod .
]</
{{out}}
<pre>
Line 619:
=={{header|Go}}==
<
import (
Line 726:
fmt.Println("\nLibrary-based computation of x1 ^ x2 mod m:")
fmt.Println(new(big.Int).Exp(x1, x2, m))
}</
{{out}}
<pre>
Line 752:
=={{header|Java}}==
{{trans|Kotlin}}
<
public class MontgomeryReduction {
Line 829:
System.out.println(x1.modPow(x2, m));
}
}</
{{out}}
<pre>b : 2
Line 853:
=={{header|Julia}}==
{{trans|Python}}
<
struct Montgomery2
m::BigInt
Line 923:
testmontgomery2()
</
<pre>
b : 2
Line 948:
=={{header|Kotlin}}==
{{trans|Go}}
<
import java.math.BigInteger
Line 1,020:
println("\nLibrary-based computation of x1 ^ x2 mod m :")
println(x1.modPow(x2, m))
}</
{{out}}
Line 1,048:
{{trans|D}}
{{libheader|bignum}}
<
# Missing functions in "bignum".
Line 1,134:
echo mont.reduce(prod)
echo "\nAlternate computation of x1^x2 mod m:"
echo x1.exp(x2, m)</
{{out}}
Line 1,160:
{{trans|Raku}}
{{libheader|ntheory}}
<
use ntheory qw(powmod);
Line 1,203:
print montgomery_reduce($m, $prod) . "\n";
printf "Built-in op computation x1**x2 mod m: %s\n", powmod($x1, $x2, $m);</
{{out}}
<pre>Original x1: 540019781128412936473322405310
Line 1,216:
{{trans|D}}
{{libheader|Phix/mpfr}}
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
Line 1,296:
<span style="color: #7060A8;">mpz_powm</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)})</span>
<!--</
{{out}}
<pre>
Line 1,318:
=={{header|PicoLisp}}==
<
(let M 1
(loop
Line 1,370:
Base (reduce (* Base Base)) ) )
(prinl (reduce Prod))
(prinl "Montgomery computation of x1 \^ x2 mod m : " (**Mod X1 X2 M)) )</
{{out}}
<pre>b : 2
Line 1,391:
=={{header|Python}}==
{{trans|D}}
<
BASE = 2
Line 1,447:
print mont.reduce(prod)
print "\nAlternate computation of x1 ^ x2 mod m :"
print pow(x1, x2, m)</
{{out}}
<pre>b : 2
Line 1,471:
=={{header|Racket}}==
<
(require math/number-theory)
Line 1,519:
(define mr (montgomery-reduce-fn m b))
(check-equal? (mr R1 n) x1)
(check-equal? (mr R2 n) x2)))</
Tests, which are courtesy of #Go implementation, all pass.
Line 1,528:
{{trans|Sidef}}
<syntaxhighlight lang="raku"
for 0..$m.msb {
$a += $m if $a +& 1;
Line 1,560:
say montgomery-reduce($m, $prod);
say "Built-in op computation x1**x2 mod m: ", $x1.expmod($x2, $m);</
{{out}}
<pre>Original x1: 540019781128412936473322405310
Line 1,573:
=={{header|Sidef}}==
{{trans|zkl}}
<
{
a += m if a.is_odd
Line 1,606:
say(montgomeryReduce(m, prod))
say("Library-based computation of x1^x2 mod m: ", x1.powmod(x2, m))</
{{out}}
<pre>
Line 1,620:
=={{header|Tcl}}==
{{in progress|lang=Tcl|day=25|month=06|year=2012}}
<
proc montgomeryReduction {m mDash T n {b 2}} {
Line 1,634:
set A [expr {$A / ($b ** $n)}]
return [expr {$A >= $m ? $A - $m : $A}]
}</
<!-- Not quite sure how to demonstrate this working; examples above aren't very clear… -->
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Imports System.Runtime.CompilerServices
Line 1,734:
End Sub
End Module</
{{out}}
<pre>b : 2
Line 1,759:
{{trans|Kotlin}}
{{libheader|Wren-big}}
<
class Montgomery {
Line 1,825:
System.print(mont.reduce(prod))
System.print("\nLibrary-based computation of x1 ^ x2 mod m :")
System.print(x1.modPow(x2, m))</
{{out}}
Line 1,853:
{{Trans|Go}}
Uses GMP (GNU Multi Precision library).
<
fcn montgomeryReduce(modulus,T){
Line 1,864:
if(a>=modulus) a.sub(modulus);
a
}</
<
//b:= 2;
//n:= 100;
Line 1,899:
}
println(montgomeryReduce(m,prod));
println("Library-based computation of x1 ^ x2 mod m: ",x1.powm(x2,m));</
{{out}}
<pre>
| |||