However, this is much easier after Python 3.8. Normally, we can use extended Euclidean algorithm to find the multiplicative inverse. It comes with a greatest common divisor function.Īfter then, we need to find the multiplicative inverse of our private key for module phi. We can check the co-primeness of two integer with math module of python. Thereafter, we should pick a random integer that co-prime to phi. We do not want to spend that time! Private Public Key Pair Remember that n should be multiplication of two large primes. Otherwise, we can build a for loop to find positive integer numbers that co-prime to it but this requires O(n) complexity. In that way, we can find the phi with O(1) complexity. Instead of counting positive integer numbers that co-prime to it, we can find the multiplication of its multipliers’s totient function results. Herein, totient function is a multiplicative function. Even though, n is a prime number, it is the multiplication of two prime numbers.

However, we picked the n as the multiplication of two prime numbers. We know that if n is a prime number, then positive integer number that co-prime to it should be (n-1). Totient function of n counts the positive integer numbers that co-prime to n. These variables are coming from the Euler’s generalization of Fermat’s Little Theorem. Then, we will find the module n and totient n (or shortly phi) variables from p and q. If you set a non-prime number to p or q, then this program will raise an error.

A prime number must not be divided by another number less than it without remainder.

To have a safety net, we should check the primeness of this p and q pair. In a practical application, these should be large primes but we will use small ones in this example. The algorithm expects to pick two prime numbers first.

Decrypt message with rsa python 3