Find Inverse of E Mod N Calculator

Finding the inverse of e mod n is a fundamental operation in modular arithmetic, particularly important in cryptography and number theory. This calculator helps you compute the modular inverse efficiently while explaining the underlying concepts.

What is the inverse of e mod n?

The inverse of e modulo n is a number x such that:

e × x ≡ 1 mod n

This means that when e is multiplied by x, the result is congruent to 1 modulo n. The inverse exists only if e and n are coprime (their greatest common divisor is 1).

In cryptography, modular inverses are used in RSA encryption to decrypt messages. The inverse helps reverse the encryption process by transforming the ciphertext back to the original plaintext.

How to find the inverse of e mod n

To find the inverse of e mod n, you can use the Extended Euclidean Algorithm, which efficiently computes both the greatest common divisor (GCD) and the coefficients (x and y) that satisfy Bézout's identity:

e × x + n × y = GCD(e, n)

If the GCD is 1, then x is the modular inverse of e mod n. If the GCD is not 1, the inverse does not exist.

Steps to compute the inverse:

Compute the GCD of e and n using the Euclidean algorithm.
If the GCD is not 1, the inverse does not exist.
If the GCD is 1, use the Extended Euclidean Algorithm to find x and y.
Take x mod n to ensure the result is positive and within the range [0, n-1].

This process is implemented in the calculator below for quick and accurate results.

Example calculation

Let's find the inverse of 7 mod 26:

Compute GCD(7, 26). Since 7 and 26 share no common divisors other than 1, the inverse exists.
Apply the Extended Euclidean Algorithm:
- 26 = 3 × 7 + 5
- 7 = 1 × 5 + 2
- 5 = 2 × 2 + 1
- 2 = 2 × 1 + 0
Working backwards:
- 1 = 5 - 2 × 2
- 2 = 7 - 1 × 5
- 1 = 5 - 2 × (7 - 1 × 5) = 3 × 5 - 2 × 7
- 5 = 26 - 3 × 7
- 1 = 3 × (26 - 3 × 7) - 2 × 7 = 3 × 26 - 11 × 7
The coefficient of 7 is -11. Taking -11 mod 26 gives 15.

Therefore, the inverse of 7 mod 26 is 15, because 7 × 15 ≡ 1 mod 26.

FAQ

What if the inverse doesn't exist?: The inverse of e mod n exists only if e and n are coprime (GCD(e, n) = 1). If they share a common factor greater than 1, the inverse cannot be found.
How is the inverse used in cryptography?: In RSA encryption, the inverse is used to decrypt messages. The public key contains e, and the private key contains the inverse of e mod φ(n), where φ(n) is Euler's totient function.
Can the inverse be negative?: Mathematically, the inverse can be negative, but in modular arithmetic, we typically take the positive equivalent by computing x mod n.
What if n is prime?: If n is prime, any number e from 1 to n-1 will have an inverse mod n, since all numbers are coprime with a prime.
How does the calculator handle large numbers?: The calculator uses efficient algorithms to handle large numbers, but very large values may take longer to compute.