Montgomery reduction: Difference between revisions

=={{header|11l}}==

{{trans|Python}}

<lang 11l>T Montgomery

BigInt m

Int n

BigInt rrm

F (m)

.m = m

.n = bit_length(m)

.rrm = (BigInt(2) ^ (.n * 2)) % m

F reduce(t)

V a = t

L(i) 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 bit_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))</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

Alternate computation of x1 ^ x2 mod m:

151232511393500655853002423778

</pre>