Montgomery reduction: Difference between revisions

{{trans|Python}}

BigInt m

Int n

print(mont.reduce(prod))

print("\nAlternate computation of x1 ^ x2 mod m:")

{{out}}

=={{header|C}}==

#include <stdlib.h>

return 0;

{{out}}

<pre>b : 2

=={{header|C sharp|C#}}==

{{trans|D}}

using System.Numerics;

}

}

{{out}}

<pre>b : 2

=={{header|C++}}==

#include<conio.h>

using namespace std;

cout<<"Montgomery domain representation = "<<e;

return 0;

=={{header|D}}==

{{trans|Kotlin}}

import std.stdio;

writeln("\nAlternate computation of x1 ^ x2 mod m :");

writeln(x1.modPow(x2, m));

{{out}}

<pre>b : 2

{{trans|Sidef}}

{{works with|Factor|0.99 2020-08-14}}

prettyprint ;

"Library-based computation of x1^x2 mod m: " write

x1 x2 m ^mod .

{{out}}

<pre>

=={{header|Go}}==

import (

fmt.Println("\nLibrary-based computation of x1 ^ x2 mod m:")

fmt.Println(new(big.Int).Exp(x1, x2, m))

{{out}}

<pre>

=={{header|Java}}==

{{trans|Kotlin}}

public class MontgomeryReduction {

System.out.println(x1.modPow(x2, m));

}

{{out}}

<pre>b : 2

=={{header|Julia}}==

{{trans|Python}}

struct Montgomery2

m::BigInt

testmontgomery2()

<pre>

b : 2

=={{header|Kotlin}}==

{{trans|Go}}

import java.math.BigInteger

println("\nLibrary-based computation of x1 ^ x2 mod m :")

println(x1.modPow(x2, m))

{{out}}

{{trans|D}}

{{libheader|bignum}}

# Missing functions in "bignum".

echo mont.reduce(prod)

echo "\nAlternate computation of x1^x2 mod m:"

{{out}}

{{trans|Raku}}

{{libheader|ntheory}}

use ntheory qw(powmod);

print montgomery_reduce($m, $prod) . "\n";

{{out}}

<pre>Original x1: 540019781128412936473322405310

{{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>

<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>

=={{header|PicoLisp}}==

(let M 1

(loop

Base (reduce (* Base Base)) ) )

(prinl (reduce Prod))

{{out}}

<pre>b : 2

=={{header|Python}}==

{{trans|D}}

BASE = 2

print mont.reduce(prod)

print "\nAlternate computation of x1 ^ x2 mod m :"

{{out}}

<pre>b : 2

=={{header|Racket}}==

(require math/number-theory)

(define mr (montgomery-reduce-fn m b))

(check-equal? (mr R1 n) x1)

Tests, which are courtesy of #Go implementation, all pass.

{{trans|Sidef}}

for 0..$m.msb {

$a += $m if $a +& 1;

say montgomery-reduce($m, $prod);

{{out}}

<pre>Original x1: 540019781128412936473322405310

=={{header|Sidef}}==

{{trans|zkl}}

{

a += m if a.is_odd

say(montgomeryReduce(m, prod))

{{out}}

<pre>

=={{header|Tcl}}==

{{in progress|lang=Tcl|day=25|month=06|year=2012}}

proc montgomeryReduction {m mDash T n {b 2}} {

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

End Sub

{{out}}

<pre>b : 2

{{trans|Kotlin}}

{{libheader|Wren-big}}

class Montgomery {

System.print(mont.reduce(prod))

System.print("\nLibrary-based computation of x1 ^ x2 mod m :")

{{out}}

{{Trans|Go}}

Uses GMP (GNU Multi Precision library).

fcn montgomeryReduce(modulus,T){

if(a>=modulus) a.sub(modulus);

a

//b:= 2;

//n:= 100;

}

println(montgomeryReduce(m,prod));

{{out}}

<pre>