Java Modular Multiplicative Inverse

Question

I cannot for the life of me figure out how to find the modular multiplicative inverse mod 5. I have read all the wiki articles, watched videos, and even looked for help from classmates and cannot find a solution to this. Everything I have found is either in another programming language in which I can't translate to Java (new to programming) and/or uses doubles instead of integers, which I can only use integers per my professor's specs. Here is the class I have written so far, can't do the divide() method until I figure out the inverse() method:

public class ModInt {

    /**
     * the integer modulo base
     */
    private int base;

    /**
    *  the number
    */
    private int number;

    /**
     * creates the modulo 2 number 0
     */
    public ModInt()
    {
        base = 2;
        number = 0;
    }

    /**
     * creates a modulo b number n
     * @param n the number
     * @param b the base
     */
    public ModInt(int n, int b)
    {
       number = n;
       base = b;
    }

    /**
     * creates an equivalent number in the same integer modulo base as the specified integer modulo number.
     * @param m an integer modulo number
     */
    public ModInt(ModInt m)
    {
       number = m.number;
       base = m.base;
    }

    /**
     * gives the number of the integer modulo number.
     * @return the number
     */
    public int getNumber()
    {
        return number;
    }

    /**
     * gives the base of the specified integer modulo number.
     * @return the base
     */
    public int getBase()
    {
        return base;
    }

    /**
     * modifies the integer modulo number using the specified parameters
     * @param n the new number
     * @param b the new base
     */
    public void setModInt(int n, int b)
    {
       number = n;
       base = b;
    }

    /**
     * adds this integer modulo number and the specified integer modulo number
     * @param m an integer modulo number
     * @return the sum of this number and the specified number
     */
    public ModInt add(ModInt m)
    {
       return new ModInt((number + m.number) % base, base);     
    }

    /**
     * subtracts this integer modulo number and the specified integer modulo number
     * @param m an integer modulo number
     * @return the difference this number and the specified number
     */
    public ModInt subtract(ModInt m)
    {
        return new ModInt(((base - number + m.number) % base, base);
    }

    /**
     * multiplies this integer modulo number and the specified integer modulo number
     * @param m an integer modulo number
     * @return the product of this number and the specified number
     */
    public ModInt multiply(ModInt m)
    {
       return new ModInt((number * m.number) % base, base);
    }    

    /**
     * computes the inverse of this integer modulo number
     * @return the inverse of this number
     */
    public ModInt inverse()
    {
       return new ModInt();
    }

    /**
     * divides this integer modulo number and the specified integer modulo number
     * @param m an integer modulo number
     * @return the quotient of this number and the specified number
     */
    public ModInt divide(ModInt m)
    {
       return new ModInt();
    }    

    /**
     * give the string representation of an integer modulo number in the format
     * n(mod b), where n is the number and b is the base
     * @return a string representation of the integer modulo number in the format
     * n(mod b); for example 3(mod 5) is the representation of the number 
     * 3 in integer modulo base 5
     */
    public String toString()
    {
       return String.format("%d(mod %d)", number, base);
    }

}

I am trying to write the inverse() method so it returns the inverse of the integer modulo number (mod 5). For now, I have it returning just the default constructor so the error would go away when running the code. Can anyone attempt to explain how to find the modular multiplicative inverse using ONLY integer types, no doubles or any other types? Here is my professor's explanation of it, but I don't understand it:

The multiplicative inverse or simply the inverse of a number n, denoted n^(−1), in integer modulo base b, is a number that when multiplied by n is congruent to 1; that is, n × n^(−1) ≡ 1(mod b). For example, 5^(−1) integer modulo 7 is 3 since (5 × 3) mod 7 = 15 mod 7 ≡ 1. The number 0 has no inverse. Not every number is invertible. For example, 2^(−1) integer modulo 4 is indeterminate since no integer in {0, 1, 2, 3} can be multiplied by 2 to obtain 1.

Any help is appreciated, thanks.

Answer 1

I have a method that can calculate the mode inverse of a. TC O(logm) SC O(logm). We are using Euclid algorithm: “a and m are co-primes if GCD(a,m) == 1”.

Code: Github

public class ModInverse {

    public static void main(String[] args) {
        System.out.printf("Mode inverse of %d in mode %d is %d. \n", 3, 11, ModInverse.getModInverse(3, 11));
        System.out.printf("Mode inverse of %d in mode %d is %d. \n", 10, 17, ModInverse.getModInverse(10, 17));
    }

    /**
     * A method that returns the mod inverse of a in a specific mod. This method uses Euclid algorithm:
     * and m are co-primes if GCD(a, m) == 1
     * Time complexity O(logm)
     * Space complexity O(logm)
     *
     * @param a   The input
     * @param mod The mod
     * @return Inverse mod of a in the mod
     */
    public static int getModInverse(int a, int mod) {
        int originalMod = mod, x = 1, y = 0;
        if (mod == 1) return 0;
        while (a > 1) { // Euclid algorithm: a and m are co-primes if gcd(a,m)==1
            int quotient = a / mod;
            int temp = mod;
            mod = a % mod;
            a = temp;
            temp = y;
            y = x - quotient * y;
            x = temp;
        }
        return x < 0 ? x + originalMod : x; // Make x positive if it is negative
    }

}

Unit test: Github

import org.junit.Assert;
import org.junit.Test;

public class ModInverseTest {

    @Test
    public void testGetModInverse() {
        Assert.assertEquals(4, ModInverse.getModInverse(3, 11));
        Assert.assertEquals(12, ModInverse.getModInverse(10, 17));
    }

}

Answer 2

you can try this one code and you will find out the answer:

//package CNS;

import java.util.Scanner;

public class extended_eculidean {

    public static void extended_eculidean(int m,int b){
        int a1=1,a2=0,a3=b;
        int b1=0,b2=1,b3=m;
        int count=0;

        while(b3!=1 && b3!=0)
        {
            int  q=a3/b3;
            int  t1=(a1-(q*b1));
            int t2=(a2-(q*b2));
            int  t3=(a3-(q*b3));
            //copying values of previous b1,b2,b3 into current a1,a2,a3
            a1=b1;
            a2=b2;
            a3=b3;
            b1=t1;
            b2=t2;
            b3=t3;
        }

        if(b3==0)
        {
            System.out.println("Inverse can not found");
        }
        else
        {
            if(b2<0) {
                b2=b2+m;
            }
        }
        System.out.println("the inverse found : that is the answer");
        System.out.println( b2);
    }

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        System.out.println("enter the number :");
        int b=sc.nextInt();

        System.out.println("enter the number of galois field");
        int m=sc.nextInt();

        System.out.println("this is the answer" );
        extended_eculidean(m,b);
    }
}

Output:

enter the number :
17
enter the number of galois field
29
this is the answer
the inverse found: that is the answer
22

Answer 3

Here are some facts before proceeding to multiplicative inverse.

Given the equation :

has multiplication inverse of a if and only if n>1 , gcd(a,n) = 1. and b =1

Hence the equation becomes :

where a^{-1} is multiplicative inverse of a.

Using the extended Eculid algorithm given two integers a,b; the gcd(a,b) can be written as the liner combination of a and b so the equation becomes:

We need to find the value of x which will be the multiplicative inverse of a.

If the value of x is negative add n to make it positive by using the following property of modular arithmetic.

Here is the java code to do the same :

import java.math.BigInteger;

public class ExtendedEculid {

    public static int[] egcd(int a, int b) {
        if (b == 0)
            return new int[] { a, 1, 0 };
        else {
            int[] arr = egcd(b, a % b);

            int gcd = arr[0];
            int X = arr[2];
            int Y = arr[1] - (a / b) * arr[2];

            return new int[] { gcd, X, Y };
        }
    }

    public static int multiplicativeInverse(int a, int modulo) {

        int[] egcdValues = egcd(a, modulo);

        // since multiplicative inverse exist iff gcd(a,modulo) =1
        // if no inverse exist then return 0

        if (egcdValues[0] != 1)
            return 0;
        if (egcdValues[1] > 0)
            return egcdValues[1];
        else
            return egcdValues[1] + modulo;
    }
    
    
    public static void main(String[] args) {
        
        System.out.println(multiplicativeInverse(5, 7));
        
        // using BigInteger
        BigInteger a = new BigInteger("5");
        BigInteger m = new BigInteger("7");
        System.out.println(a.modInverse(m));
        
    }
}

Edit : java.math.BigInteger has a method modInverse here . You can use it as well ,code snippet added for it.

References : CLRS ,Introductions to algorithms ,3rd ed, Chapter 31

Answer 4

This should do it. If a and m are not relatively prime (i.e. have a common divisor that isn't 1), this will return a -1.

I included a call to a gcd method prior to iteration from 1 to m to short circuit the process if a and m are not relatively prime.

     public static int mod(int a, int m) {
        if (gcd(a,m) != 1) {
            return -1;
        }
        int x;
        for (x = 1; x < m; x++) {
            if ((a * x) % m == 1) {
                break;
            }
        }
        return x;
    }
    public static int gcd(int r, int s) {
        while (s != 0) {
           int t = s;
           s = r % s;
           r = t;
        }
        return r;
    }

for more info check out Modular Multiplicative Inverse

Answer 5

I took the brute force algorithm from https://comeoncodeon.wordpress.com/2011/10/09/modular-multiplicative-inverse/, it’s in C++ but almost compiles as Java. So most of my work was tailoring it to fit into your class. This is the result:

/**
 * computes the inverse of this integer modulo number
 * 
 * @return the inverse of this number
 */
public ModInt inverse() {
    int a = number % base;
    for (int x = 1; x < base; x++) {
        if ((a * x) % base == 1) {
            return new ModInt(x, base);
        }
    }
    throw new ArithmeticException("No inverse of " + toString());
}