Montgomery reduction: Difference between revisions
m
→{{header|Wren}}: Minor tidy
(Add Factor) |
m (→{{header|Wren}}: Minor tidy) |
||
(12 intermediate revisions by 7 users not shown) | |||
Line 16:
A ← A - m
Return (A)
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">T Montgomery
BigInt m
Int n
BigInt rrm
F (m)
.m = m
.n = bits:length(m)
.rrm = (BigInt(2) ^ (.n * 2)) % m
F reduce(t)
V a = t
L 0 .< .n
I (a % 2) == 1
a += .m
a I/= 2
I a >= .m
a -= .m
R a
V m = BigInt(‘750791094644726559640638407699’)
V x1 = BigInt(‘540019781128412936473322405310’)
V x2 = BigInt(‘515692107665463680305819378593’)
V mont = Montgomery(m)
V t1 = x1 * mont.rrm
V t2 = x2 * mont.rrm
V r1 = mont.reduce(t1)
V r2 = mont.reduce(t2)
V r = BigInt(2) ^ mont.n
print(‘b : 2’)
print(‘n : ’mont.n)
print(‘r : ’r)
print(‘m : ’mont.m)
print(‘t1: ’t1)
print(‘t2: ’t2)
print(‘r1: ’r1)
print(‘r2: ’r2)
print()
print(‘Original x1 : ’x1)
print(‘Recovered from r1 : ’mont.reduce(r1))
print(‘Original x2 : ’x2)
print(‘Recovered from r2 : ’mont.reduce(r2))
print("\nMontgomery computation of x1 ^ x2 mod m:")
V prod = mont.reduce(mont.rrm)
V base = mont.reduce(x1 * mont.rrm)
V ex = x2
L bits:length(ex) > 0
I (ex % 2) == 1
prod = mont.reduce(prod * base)
ex I/= 2
base = mont.reduce(base * base)
print(mont.reduce(prod))
print("\nAlternate computation of x1 ^ x2 mod m:")
print(pow(x1, x2, m))</syntaxhighlight>
{{out}}
<pre>
b : 2
n : 100
r : 1267650600228229401496703205376
m : 750791094644726559640638407699
t1: 323165824550862327179367294465482435542970161392400401329100
t2: 308607334419945011411837686695175944083084270671482464168730
r1: 440160025148131680164261562101
r2: 435362628198191204145287283255
Original x1 : 540019781128412936473322405310
Recovered from r1 : 540019781128412936473322405310
Original x2 : 515692107665463680305819378593
Recovered from r2 : 515692107665463680305819378593
Montgomery computation of x1 ^ x2 mod m:
151232511393500655853002423778
Alternate computation of x1 ^ x2 mod m:
151232511393500655853002423778
</pre>
=={{header|C}}==
<
#include <stdlib.h>
Line 134 ⟶ 219:
return 0;
}</
{{out}}
<pre>b : 2
Line 158 ⟶ 243:
=={{header|C sharp|C#}}==
{{trans|D}}
<
using System.Numerics;
Line 249 ⟶ 334:
}
}
}</
{{out}}
<pre>b : 2
Line 272 ⟶ 357:
=={{header|C++}}==
<
#include<conio.h>
using namespace std;
Line 357 ⟶ 442:
cout<<"Montgomery domain representation = "<<e;
return 0;
}</
=={{header|D}}==
{{trans|Kotlin}}
<
import std.stdio;
Line 459 ⟶ 544:
writeln("\nAlternate computation of x1 ^ x2 mod m :");
writeln(x1.modPow(x2, m));
}</
{{out}}
<pre>b : 2
Line 484 ⟶ 569:
{{trans|Sidef}}
{{works with|Factor|0.99 2020-08-14}}
<
prettyprint ;
Line 521 ⟶ 606:
"Library-based computation of x1^x2 mod m: " write
x1 x2 m ^mod .
]</
{{out}}
<pre>
Line 534 ⟶ 619:
=={{header|Go}}==
<
import (
Line 641 ⟶ 726:
fmt.Println("\nLibrary-based computation of x1 ^ x2 mod m:")
fmt.Println(new(big.Int).Exp(x1, x2, m))
}</
{{out}}
<pre>
Line 667 ⟶ 752:
=={{header|Java}}==
{{trans|Kotlin}}
<
public class MontgomeryReduction {
Line 744 ⟶ 829:
System.out.println(x1.modPow(x2, m));
}
}</
{{out}}
<pre>b : 2
Line 768 ⟶ 853:
=={{header|Julia}}==
{{trans|Python}}
<
struct Montgomery2
m::BigInt
Line 838 ⟶ 923:
testmontgomery2()
</
<pre>
b : 2
Line 863 ⟶ 948:
=={{header|Kotlin}}==
{{trans|Go}}
<
import java.math.BigInteger
Line 935 ⟶ 1,020:
println("\nLibrary-based computation of x1 ^ x2 mod m :")
println(x1.modPow(x2, m))
}</
{{out}}
Line 959 ⟶ 1,044:
151232511393500655853002423778
</pre>
=={{header|Nim}}==
{{trans|D}}
{{libheader|bignum}}
<syntaxhighlight lang="nim">import bignum
# Missing functions in "bignum".
template isOdd(val: Int): bool =
## Needed as bignum "odd" function crashes.
(val and 1) != 0
func exp(x, y, m: Int): Int =
## Missing "exp" function in "bignum".
if m == 1: return newInt(0)
result = newInt(1)
var x = x mod m
var y = y
while y > 0:
if y.isOdd:
result = (result * x) mod m
y = y shr 1
x = (x * x) mod m
type Montgomery = object
m: Int # Modulus; must be odd.
n: int # m.bitLen().
rrm: Int # (1<<2n) mod m.
const Base = 2
func initMontgomery(m: Int): Montgomery =
## Initialize a Mongtgomery object.
doAssert m > 0 and m.isOdd, "argument must be positive and odd."
result.m = m
result.n = m.bitLen
result.rrm = newInt(1) shl culong(result.n * 2) mod m
func reduce(mont: Montgomery; t: Int): Int =
## Montgomery reduction algorithm.
result = t
for i in 0..<mont.n:
if result.isOdd: inc result, mont.m
result = result shr 1
if result >= mont.m: dec result, mont.m
when isMainModule:
let
m = newInt("750791094644726559640638407699")
x1 = newInt("540019781128412936473322405310")
x2 = newInt("515692107665463680305819378593")
mont = initMontgomery(m)
t1 = x1 * mont.rrm
t2 = x2 * mont.rrm
r1 = mont.reduce(t1)
r2 = mont.reduce(t2)
r = newInt(1) shl culong(mont.n)
echo "b: ", Base
echo "n: ", mont.n
echo "r: ", r
echo "m: ", mont.m
echo "t1: ", t1
echo "t2: ", t2
echo "r1: ", r1
echo "r2: ", r2
echo()
echo "Original x1: ", x1
echo "Recovered from r1: ", mont.reduce(r1)
echo "Original x2: ", x2
echo "Recovered from r2: ", mont.reduce(r2)
echo "\nMontgomery computation of x1^x2 mod m:"
var
prod = mont.reduce(mont.rrm)
base = mont.reduce(x1 * mont.rrm)
e = x2
while e > 0:
if e.isOdd: prod = mont.reduce(prod * base)
e = e shr 1
base = mont.reduce(base * base)
echo mont.reduce(prod)
echo "\nAlternate computation of x1^x2 mod m:"
echo x1.exp(x2, m)</syntaxhighlight>
{{out}}
<pre>b: 2
n: 100
r: 1267650600228229401496703205376
m: 750791094644726559640638407699
t1: 323165824550862327179367294465482435542970161392400401329100
t2: 308607334419945011411837686695175944083084270671482464168730
r1: 440160025148131680164261562101
r2: 435362628198191204145287283255
Original x1: 540019781128412936473322405310
Recovered from r1: 540019781128412936473322405310
Original x2: 515692107665463680305819378593
Recovered from r2: 515692107665463680305819378593
Montgomery computation of x1^x2 mod m:
151232511393500655853002423778
Alternate computation of x1^x2 mod m:
151232511393500655853002423778</pre>
=={{header|Perl}}==
{{trans|Raku}}
{{libheader|ntheory}}
<
use ntheory qw(powmod);
Line 1,006 ⟶ 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,019 ⟶ 1,216:
{{trans|D}}
{{libheader|Phix/mpfr}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<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: #008080;">enum</span> <span style="color: #000000;">BASE</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">BITLEN</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">MODULUS</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">RRM</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">reduce</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">mont</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">mpz</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mont</span><span style="color: #0000FF;">[</span><span style="color: #000000;">BITLEN</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mont</span><span style="color: #0000FF;">[</span><span style="color: #000000;">MODULUS</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_odd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_fdiv_q_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_cmp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)>=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">mpz_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">r</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">Montgomery</span><span style="color: #0000FF;">(</span><span style="color: #004080;">mpz</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_sign</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)=-</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">crash</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"must be positive"</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">mpz_odd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">crash</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"must be odd"</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_sizeinbase</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">rrm</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_powm_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rrm</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rrm</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- BASE</span>
<span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- BITLEN</span>
<span style="color: #000000;">m</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- MODULUS</span>
<span style="color: #000000;">rrm</span> <span style="color: #000080;font-style:italic;">-- 1<<(n*2) % m</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"750791094644726559640638407699"</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">x1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"540019781128412936473322405310"</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">x2</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"515692107665463680305819378593"</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(),</span>
<span style="color: #000000;">t2</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">mont</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">Montgomery</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">[</span><span style="color: #000000;">RRM</span><span style="color: #0000FF;">])</span>
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">[</span><span style="color: #000000;">RRM</span><span style="color: #0000FF;">])</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">r1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">reduce</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t1</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">r2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">reduce</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t2</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">mpz_ui_pow_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">[</span><span style="color: #000000;">BITLEN</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;">"b : %d\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">[</span><span style="color: #000000;">BASE</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;">"n : %d\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">[</span><span style="color: #000000;">BITLEN</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;">"r : %s\n"</span><span style="color: #0000FF;">,</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>
<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;">"m : %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">[</span><span style="color: #000000;">MODULUS</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;">"t1: %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t1</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;">"t2: %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t2</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;">"r1: %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r1</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;">"r2: %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r2</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;">"\n"</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;">"Original x1 : %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x1</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;">"Recovered from r1 : %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">reduce</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r1</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;">"Original x2 : %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x2</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;">"Recovered from r2 : %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">reduce</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r2</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;">"\nMontgomery computation of x1 ^ x2 mod m :"</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">prod</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">reduce</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">[</span><span style="color: #000000;">RRM</span><span style="color: #0000FF;">])</span>
<span style="color: #7060A8;">mpz_mul</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;">mont</span><span style="color: #0000FF;">[</span><span style="color: #000000;">RRM</span><span style="color: #0000FF;">])</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">base</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">reduce</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">expn</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">while</span> <span style="color: #7060A8;">mpz_cmp_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">expn</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_odd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">expn</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">prod</span><span style="color: #0000FF;">,</span><span style="color: #000000;">prod</span><span style="color: #0000FF;">,</span><span style="color: #000000;">base</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">prod</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">reduce</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">,</span><span style="color: #000000;">prod</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_fdiv_q_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">expn</span><span style="color: #0000FF;">,</span><span style="color: #000000;">expn</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">base</span><span style="color: #0000FF;">,</span><span style="color: #000000;">base</span><span style="color: #0000FF;">,</span><span style="color: #000000;">base</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">base</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">reduce</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">,</span><span style="color: #000000;">base</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</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;">reduce</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mont</span><span style="color: #0000FF;">,</span><span style="color: #000000;">prod</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;">" alternate computation of x1 ^ x2 mod m :"</span><span style="color: #0000FF;">)</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>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 1,118 ⟶ 1,318:
=={{header|PicoLisp}}==
<
(let M 1
(loop
Line 1,170 ⟶ 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,190 ⟶ 1,390:
=={{header|Python}}==
{{todo|python|Update the output}}
{{trans|D}}
<syntaxhighlight lang
class Montgomery:
BASE = 2
Line 1,222 ⟶ 1,424:
r = 1 << mont.n
print(
f"b: {Montgomery.BASE}\n"
f"n: {mont.n}\n"
f"m: {mont.m}\n"
f"t1: {t1}\n"
f"t2: {t2}\n"
f"r1: {r1}\n"
f"r2: {r2}\n"
)
print
prod = mont.reduce(mont.rrm)
base = mont.reduce(x1 * mont.rrm)
Line 1,245 ⟶ 1,448:
exp = exp >> 1
base = mont.reduce(base * base)
print
print
</syntaxhighlight>
{{out}}
<pre>
b : 2
n : 100
r : 1267650600228229401496703205376
Line 1,267 ⟶ 1,471:
Alternate computation of x1 ^ x2 mod m :
151232511393500655853002423778
</pre>
=={{header|Quackery}}==
{{trans|Factor}}
<code>**mod</code> is defined at [[Modular exponentiation#Quackery]].
<syntaxhighlight lang="Quackery"> [ 0 swap [ dup while dip 1+ 1 >> again ] drop ] is bits ( n --> n )
[ 1 & ] is odd ( n --> b )
[ over bits times [ dup odd if [ over + ] 1 >> ] swap mod ] is monred ( n n --> n )
[ 750791094644726559640638407699 ] is m ( --> n )
[ 323165824550862327179367294465482435542970161392400401329100 ] is t1 ( --> n )
[ 440160025148131680164261562101 ] is r1 ( --> n )
[ 435362628198191204145287283255 ] is r2 ( --> n )
[ 540019781128412936473322405310 ] is x1 ( --> n )
[ 515692107665463680305819378593 ] is x2 ( --> n )
[ unrot dip
[ dip dup
over t1 rot / monred temp put
t1 monred ]
[ dup 0 != while
dup odd if
[ over temp take *
m swap monred
temp put ]
dip [ dup * m swap monred ]
1 >> again ]
2drop temp take monred ] is **mon ( n n n --> n )
say "Original x1: " x1 echo cr
say "Recovered from r1: " m r1 monred echo cr
cr
say "Original x2: " x2 echo cr
say "Recovered from r2: " m r2 monred echo cr
cr
say "Montgomery computation of x1^x2 mod m: " x1 x2 m **mon echo cr
say "Modular exponentiation of x1^x2 mod m: " x1 x2 m **mod echo cr</syntaxhighlight>
{{out}}
<pre>Original x1: 540019781128412936473322405310
Recovered from r1: 540019781128412936473322405310
Original x2: 515692107665463680305819378593
Recovered from r2: 515692107665463680305819378593
Montgomery computation of x1^x2 mod m: 151232511393500655853002423778
Modular exponentiation of x1^x2 mod m: 151232511393500655853002423778</pre>
=={{header|Racket}}==
<
(require math/number-theory)
Line 1,319 ⟶ 1,578:
(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,328 ⟶ 1,587:
{{trans|Sidef}}
<syntaxhighlight lang="raku"
for 0..$m.msb {
$a += $m if $a +& 1;
Line 1,360 ⟶ 1,619:
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,373 ⟶ 1,632:
=={{header|Sidef}}==
{{trans|zkl}}
<
{
a += m if a.is_odd
Line 1,406 ⟶ 1,665:
say(montgomeryReduce(m, prod))
say("Library-based computation of x1^x2 mod m: ", x1.powmod(x2, m))</
{{out}}
<pre>
Line 1,420 ⟶ 1,679:
=={{header|Tcl}}==
{{in progress|lang=Tcl|day=25|month=06|year=2012}}
<
proc montgomeryReduction {m mDash T n {b 2}} {
Line 1,434 ⟶ 1,693:
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#}}
<syntaxhighlight lang="vbnet">Imports System.Numerics
Imports System.Runtime.CompilerServices
Module Module1
<Extension()>
Function BitLength(v As BigInteger) As Integer
If v < 0 Then
v *= -1
End If
Dim result = 0
While v > 0
v >>= 1
result += 1
End While
Return result
End Function
Structure Montgomery
Shared ReadOnly BASE = 2
Dim m As BigInteger
Dim rrm As BigInteger
Dim n As Integer
Sub New(m As BigInteger)
If m < 0 OrElse m.IsEven Then
Throw New ArgumentException()
End If
Me.m = m
n = m.BitLength
rrm = (BigInteger.One << (n * 2)) Mod m
End Sub
Function Reduce(t As BigInteger) As BigInteger
Dim a = t
For i = 1 To n
If Not a.IsEven Then
a += m
End If
a >>= 1
Next
If a >= m Then
a -= m
End If
Return a
End Function
End Structure
Sub Main()
Dim m = BigInteger.Parse("750791094644726559640638407699")
Dim x1 = BigInteger.Parse("540019781128412936473322405310")
Dim x2 = BigInteger.Parse("515692107665463680305819378593")
Dim mont As New Montgomery(m)
Dim t1 = x1 * mont.rrm
Dim t2 = x2 * mont.rrm
Dim r1 = mont.Reduce(t1)
Dim r2 = mont.Reduce(t2)
Dim r = BigInteger.One << mont.n
Console.WriteLine("b : {0}", Montgomery.BASE)
Console.WriteLine("n : {0}", mont.n)
Console.WriteLine("r : {0}", r)
Console.WriteLine("m : {0}", mont.m)
Console.WriteLine("t1: {0}", t1)
Console.WriteLine("t2: {0}", t2)
Console.WriteLine("r1: {0}", r1)
Console.WriteLine("r2: {0}", r2)
Console.WriteLine()
Console.WriteLine("Original x1 : {0}", x1)
Console.WriteLine("Recovered from r1 : {0}", mont.Reduce(r1))
Console.WriteLine("Original x2 : {0}", x2)
Console.WriteLine("Recovered from r2 : {0}", mont.Reduce(r2))
Console.WriteLine()
Console.WriteLine("Montgomery computation of x1 ^ x2 mod m :")
Dim prod = mont.Reduce(mont.rrm)
Dim base = mont.Reduce(x1 * mont.rrm)
Dim exp = x2
While exp.BitLength > 0
If Not exp.IsEven Then
prod = mont.Reduce(prod * base)
End If
exp >>= 1
base = mont.Reduce(base * base)
End While
Console.WriteLine(mont.Reduce(prod))
Console.WriteLine()
Console.WriteLine("Alternate computation of x1 ^ x2 mod m :")
Console.WriteLine(BigInteger.ModPow(x1, x2, m))
End Sub
End Module</syntaxhighlight>
{{out}}
<pre>b : 2
n : 100
r : 1267650600228229401496703205376
m : 750791094644726559640638407699
t1: 323165824550862327179367294465482435542970161392400401329100
t2: 308607334419945011411837686695175944083084270671482464168730
r1: 440160025148131680164261562101
r2: 435362628198191204145287283255
Original x1 : 540019781128412936473322405310
Recovered from r1 : 540019781128412936473322405310
Original x2 : 515692107665463680305819378593
Recovered from r2 : 515692107665463680305819378593
Montgomery computation of x1 ^ x2 mod m :
151232511393500655853002423778
Alternate computation of x1 ^ x2 mod m :
151232511393500655853002423778</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-big}}
<
class Montgomery {
Line 1,506 ⟶ 1,884:
System.print(mont.reduce(prod))
System.print("\nLibrary-based computation of x1 ^ x2 mod m :")
System.print(x1.modPow(x2, m))</
{{out}}
Line 1,534 ⟶ 1,912:
{{Trans|Go}}
Uses GMP (GNU Multi Precision library).
<
fcn montgomeryReduce(modulus,T){
Line 1,545 ⟶ 1,923:
if(a>=modulus) a.sub(modulus);
a
}</
<
//b:= 2;
//n:= 100;
Line 1,580 ⟶ 1,958:
}
println(montgomeryReduce(m,prod));
println("Library-based computation of x1 ^ x2 mod m: ",x1.powm(x2,m));</
{{out}}
<pre>
|