Montgomery reduction: Difference between revisions
Added 11l
m (→{{header|Phix}}: added syntax colouring the hard way) |
Alextretyak (talk | contribs) (Added 11l) |
||
Line 16:
A ← A - m
Return (A)
=={{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>
=={{header|C}}==
| |||