Give a positive integer n, find modular multiplicative inverse of all integer from to n with respect to a big prime number, say, ‘prime’.

The of a is an integer ‘x’ such that.

 a x ≡ 1 (mod prime) 

Examples :

Input : n = , prime = 17
Output : 1 9 6 13 7 3 5 15 2 12
Explanation :
For 1, modular inverse is 1 as (1 * 1)%17 is 1
For 2, modular inverse is 9 as (2 * 9)%17 is 1
For 3, modular inverse is 6 as (3 * 6)%17 is 1
....... 

Input : n = 5, prime = 7
Output : 1  5 2 3

A simple solution is to one by one find modular inverse for every number.

// C++ program to find modular inverse of 
// all numbers from 1 to n using naive
// method
#include<iostream>
using namespace std;
 
// A naive method to find modular
// multiplicative inverse of 'a'
// under modulo 'prime'
int modInverse(int a, int prime)
{
    a = a % prime;
    for (int x=1; x<prime; x++)
       if ((a*x) % prime == 1)
          return x;
     
    return -1;
}

void printModIverses(int n, int prime)
{
    for (int i=1; i<=n; i++)
      cout << modInverse(i, prime) << " ";
}
 
// Driver Program
int main()
{
    int n = 10, prime = 17;
    printModIverses(n, prime);
    return 0;
}

Output:

1 9 6 13 7 3 5 15 2 12

An efficient solution is based on extended Euclid algorithm.

Extended Euclidean algorithm finds integer coefficients x and y such that:

  ax + by = gcd(a, b)

Let us put b = prime, we get
  ax + prime * y = gcd(a, prime)

We know gcd(a, prime) = 1 because
on of the numbers is prime. So we
know
  ax + prime * y = 1

Since prime * y is a multiple of prime,
x is modular multiplicative inverse of a.

 ax  ≡ 1 (mod prime) 
 

We can recursively find x using below expression (see extended Euclid algorithm for details).

The extended Euclidean algorithm results of gcd(a, b) using the results calculated by recursive call gcd(b%a, a). Let values of x and y calculated by the recursive call be xprev and yprev. x and y are updated using below expressions.

x = yprev - ⌊prime/a⌋ * xprev
y = xprev

We use above relation to compute inverse using previously computed values.

inverse(a) = (inverse(prime % a) *
              (prime - prime/a)) % prime

We use Dynamic approach that uses above recursive structure.

Dynamic Approach :
dp[1] = 1,
dp[2] = dp[17%2]*(17-17/2)%17 = 9
dp[3] = dp[17%3]*(17-17/3)%17 = 6

and so on..

C++

// CPP  to find modular inverse
// from 1 to n w.r.t a big prime number
#include <iostream>
using namespace std;

// Function to calculate modular
// inverse using D.P
void modularInverse(int n, int prime)
{
    int dp[n + 1];
    dp[0] = dp[1] = 1;
    for (int i = 2; i <= n; i++) 
        dp[i] = dp[prime % i] * 
               (prime - prime / i) % prime;    

    for (int i = 1; i <= n; i++) 
        cout << dp[i] << ' ';    
}

// Driver 
int main()
{
    int n = 10, prime = 17;
    modularInverse(n, prime);
    return 0;
}

Output:

1 9 6 13 7 3 5 15 2 12

Time Complexity : O(n)
Auxiliary Space : O(n)


- avatar - Modular multiplicative inverse from 1 to n

If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



Source link

LEAVE A REPLY

Please enter your comment!
Please enter your name here