Ciro Santilli @cirosantilli 37

Can be calculated efficiently with the Extended Euclidean algorithm.

The beauty of this algorithm is that because exponentiation grows really fast, there is no hope that we can ever learn all the digits of an exponential, as there is simply not enough time or memory for that. Therefore, a natural sub-question is if we can know some part of that number, and knowing the smallest digits is the most natural version of that question.

Based on the fact that we don't have a P algorithm for integer factorization as of 2020. But nor proof that one does not exist!

The private key is made of two randomly generated prime numbers: $p$ and $q$. How such large primes are found: how large primes are found for RSA.

The public key is made of:

Given a plaintext message m, the encrypted ciphertext version is:This operation is called modular exponentiation can be calculated efficiently with the Extended Euclidean algorithm.

The inverse operation of finding the private m from the public c, e and $n$ is however believed to be a hard problem without knowing the factors of n.

However, if we know the private p and q, we can solve the problem. As follows.

First we calculate the modular multiplicative inverse. TODO continue.

Bibliography: