Montgomery reduction: Difference between revisions
Content added Content deleted
m (Phix/mpfr) |
(Added Wren) |
||
Line 1,384: | Line 1,384: | ||
}</lang> |
}</lang> |
||
<!-- Not quite sure how to demonstrate this working; examples above aren't very clear… --> |
<!-- 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}}== |
=={{header|zkl}}== |