Montgomery reduction: Difference between revisions
→{{header|Wren}}
(Add Factor) |
|||
Line 1,436:
}</lang>
<!-- Not quite sure how to demonstrate this working; examples above aren't very clear… -->
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<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</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|Wren}}==
| |||