modular inverse code

Try this (translated from C code):

Imports System

Module Program

Sub Main()

Console.Write("Enter integer : ")

Dim a As Integer = Int32.Parse(Console.ReadLine())

Console.Write("Enter modulus : ")

Dim b As Integer = Int32.Parse(Console.ReadLine())

Console.WriteLine("The modular inverse of {0} modulo {1} is {2}", a, b, ModInverse(a, b))

Console.ReadKey

End Sub

Function ModInverse (ByVal a As Integer, ByVal b As Integer) As Integer

Dim b0 As Integer = b

Dim t As Integer

Dim q As Integer

Dim x0 As Integer = 0

Dim x1 AS Integer = 1

If b = 1 Then Return 1

While a > 1

q = a \ b

t = b

b = a Mod b

a = t

t = x0

x0 = x1 - q * x0

x1 = t

End While

If x1 < 0 Then x1 += b0

Return x1

End Function

End Module

Some sample input and output:

Enter integer : 42
Enter modulus : 2017
The modular inverse of 42 modulo 2017 is 1969

1 Reply

Know the answer? Post it — somebody with the same question will find it here.