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

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

a x ≡ 1 (mod prime)

Examples :

Input : n = 10, 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 4 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 updates 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 x_{prev} and y_{prev}. x and y are updated using below expressions.

x = y_{prev}- ⌊prime/a⌋ * x_{prev}y = x_{prev}

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

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

We use Dynamic Programming 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 code 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 code 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)

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.

more link ADS

Blockchain, bitcoin, ethereum, blockchain technology, cryptocurrencies

Information Security, latest Hacking News, Cyber Security, Network Sec

Information Security, latest Hacking News, Cyber Security, Network Security

Blog! Development Software and Application Mobile

Development apps, Android, Ios anh Tranning IT, data center, hacking

Car News, Reviews, Pricing for New & Used Cars, car reviews and news, concept cars