Montgomery reduction: Difference between revisions

A ← A - m

Return (A)

 

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

151232511393500655853002423778

</pre>

 

=={{header|Perl}}==

{{trans|Raku}}

{{libheader|ntheory}}

use ntheory qw(powmod);

 

 

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

{{out}}

<pre>Original x1: 540019781128412936473322405310

{{trans|D}}

{{libheader|Phix/mpfr}}

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

 

r = 1 << mont.n

 

 

prod = mont.reduce(mont.rrm)

base = mont.reduce(x1 * mont.rrm)

exp = exp >> 1

base = mont.reduce(base * base)

{{out}}

n : 100

r : 1267650600228229401496703205376

 

Alternate computation of x1 ^ x2 mod m :

 

=={{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|Wren}}==

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