Write a program to find multiplicative inverse modulo n, using Extended Euclid’s algorithm. Information and Network Security (2170709) GTU

Algorithm/Steps:

The Extended Euclidean Algorithm determines, if present, the inverse of b modulo n:

1. b0 = b

2. n0 = n

3. t0 = 0

4. t = 1

5. q = n0 / b0 (rounded off)

6. r = n0 - q * b0

7. while r > 0 do

8. temp = t0 - q * t

9. if temp >= 0 then temp = temp mod n

10. if temp < 0 then temp = n - (( -temp) mod n)

11. t0 = t

12. t = temp

13. n0 = b0

14. b0 = r

15. q = n0 / b0 (abgerundet)

16. r = n0 - q * b0

17. if b0 != 1 then

           b has no inverse modulo n

     else

           b-1 = t mod n

Code:

import java.util.*;

import java.lang.*;

public class Extended_euclid

 {

   //  return array [d, a, b] such that d = gcd(p, q), ap + bq = d

   static int[] gcd(int p, int q)

    {

      if (q == 0)

         return new int[] { p, 1, 0 };

      int[] vals = gcd(q, p % q);

      int d = vals[0];

      int a = vals[2];

      int b = vals[1] - (p / q) * vals[2];

      return new int[] { d, a, b };

   }

   public static void main(String[] args)

    {

                        Scanner s1=new Scanner(System.in);

                        System.out.println("Enter first number : ");

                        int p=Integer.parseInt(s1.nextLine());

                        System.out.println("Enter second number : ");

                        int q=Integer.parseInt(s1.nextLine());

                        int vals[] = gcd(p, q);

                        System.out.println("\ngcd(" + p + ", " + q + ") = " + vals[0]);

                        System.out.println(vals[1] + "(" + p + ") + " + vals[2] + "(" + q + ") = " + vals[0]);

                        System.out.println("x: "+vals[1]+"\t y: "+vals[2]);

   }

}