Ciro Santilli @cirosantilli 37

P for quantum computing!

Heck, we know nothing about this class yet related to non quantum classes!

Based on the fact that we don't have a P algorithm for the discrete logarithm of the cyclic group as of 2020, but we do have an efficient algorithm for modular exponentiation. But nor do we have proof that one does not exist! Living on the edge as usual for public-key cryptography.

Complexity: NP-intermediate as of 2020:

The basis of RSA: RSA. But not proved NP-complete, which leads to:

This is the most interesting class of problems for BQP as we haven't proven that they are neither:

Big list: cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/460#460

Interesting because of the Cook-Levin theorem: if only a single NP-complete problem were in P, then all NP-complete problems would also be P!

We all know the answer for this: either false or independent.

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: