Montgomery reduction: Difference between revisions
Added Wren
m (Phix/mpfr) |
(Added Wren) |
||
Line 1,384:
}</lang>
<!-- Not quite sure how to demonstrate this working; examples above aren't very clear… -->
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-big}}
<lang ecmascript>import "/big" for BigInt
class Montgomery {
static base { 2 }
construct new(m) {
if (m <= BigInt.zero || !m.testBit(0)) {
Fiber.abort("Argument must be a positive, odd big integer.")
}
_m = m
_n = m.bitLength.toSmall
_rrm = (BigInt.one << (n*2)) % m
}
m { _m }
n { _n }
rrm { _rrm }
reduce(t) {
var a = t.copy()
for (i in 0..._n) {
if (a.testBit(0)) a = a + _m
a = a >> 1
}
if (a >= _m) a = a - _m
return a
}
}
var m = BigInt.new("750791094644726559640638407699")
var x1 = BigInt.new("540019781128412936473322405310")
var x2 = BigInt.new("515692107665463680305819378593")
var mont = Montgomery.new(m)
var t1 = x1 * mont.rrm
var t2 = x2 * mont.rrm
var r1 = mont.reduce(t1)
var r2 = mont.reduce(t2)
var r = BigInt.one << (mont.n)
System.print("b : %(Montgomery.base)")
System.print("n : %(mont.n)")
System.print("r : %(r)")
System.print("m : %(mont.m)")
System.print("t1: %(t1)")
System.print("t2: %(t2)")
System.print("r1: %(r1)")
System.print("r2: %(r2)")
System.print()
System.print("Original x1 : %(x1)")
System.print("Recovered from r1 : %(mont.reduce(r1))")
System.print("Original x2 : %(x2)")
System.print("Recovered from r2 : %(mont.reduce(r2))")
System.print("\nMontgomery computation of x1 ^ x2 mod m :")
var prod = mont.reduce(mont.rrm)
var base = mont.reduce(x1 * mont.rrm)
var exp = x2
while (exp.bitLength > 0) {
if (exp.testBit(0)) prod = mont.reduce(prod * base)
exp = exp >> 1
base = mont.reduce(base * base)
}
System.print(mont.reduce(prod))
System.print("\nLibrary-based computation of x1 ^ x2 mod m :")
System.print(x1.modPow(x2, m))</lang>
{{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
Library-based computation of x1 ^ x2 mod m :
151232511393500655853002423778
</pre>
=={{header|zkl}}==
| |||