modular inverse code

Question

modular inverse code can any one help me . fast alogorithm code please help

Vulpes · Answer

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 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