Finding multiplicative inverse modulo n

When working with modular arithmetic, finding the multiplicative inverse modulo n can be a common task. The multiplicative inverse of a number a modulo n is another number b such that (a * b) % n = 1. In this article, we will explore three different ways to solve this problem using Julia programming language.

Option 1: Brute Force

The simplest approach to finding the multiplicative inverse modulo n is to try all possible values of b until we find the one that satisfies the equation (a * b) % n = 1. We can implement this using a loop that iterates through all numbers from 1 to n-1 and checks the condition.

function multiplicative_inverse(a, n)
    for b in 1:n-1
        if (a * b) % n == 1
            return b
        end
    end
    return -1  # No multiplicative inverse found
end

This brute force approach works for any value of n, but it can be inefficient for large values of n. The time complexity of this algorithm is O(n), which means it will take a long time to compute the multiplicative inverse for large values of n.

Option 2: Extended Euclidean Algorithm

The Extended Euclidean Algorithm is a more efficient way to find the multiplicative inverse modulo n. It is based on the Euclidean Algorithm for finding the greatest common divisor (GCD) of two numbers. The algorithm calculates the GCD of a and n, and then uses the GCD to find the multiplicative inverse.

function extended_euclidean_algorithm(a, n)
    if n == 0
        return (1, 0)
    else
        q, r = divrem(a, n)
        s, t = extended_euclidean_algorithm(n, r)
        return (t, s - q * t)
    end
end

function multiplicative_inverse(a, n)
    x, _ = extended_euclidean_algorithm(a, n)
    return mod(x, n)
end

The Extended Euclidean Algorithm has a time complexity of O(log n), which makes it much faster than the brute force approach for large values of n.

Option 3: Fermat’s Little Theorem

Fermat’s Little Theorem states that if p is a prime number and a is not divisible by p, then a^(p-1) % p = 1. We can use this theorem to find the multiplicative inverse modulo n when n is a prime number.

function multiplicative_inverse(a, n)
    return mod(a^(n-2), n)
end

This approach works only when n is a prime number. If n is not prime, the result may not be correct. However, when n is prime, this method is the fastest with a time complexity of O(1).

After comparing the three options, the best choice depends on the specific requirements of the problem. If efficiency is a concern and n is prime, using Fermat’s Little Theorem is the fastest option. If n is not prime or efficiency is not a major concern, the Extended Euclidean Algorithm provides a good balance between simplicity and efficiency. The brute force approach should only be used for small values of n or when simplicity is the main requirement.