Incoming links: P (complexity)
P for quantum computing!
Heck, we know nothing about this class yet related to non quantum classes!
- conjectured not to intersect with NP-complete, because if it were, all NP-complete problems could be solved efficiently on quantum computers, and none has been found so far as of 2020.
- conjectured to be larger than P, but we don't have a single algorithm provenly there:
- it is believed that the NP complete ones can't be solved
- if they were neither NP-complete nor P, it would imply P != NP
- we just don't know if it is even contained inside NP!
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:
- expected not to be NP-complete because it would imply NP != Co-NP: cstheory.stackexchange.com/questions/167/what-are-the-consequences-of-factoring-being-np-complete#comment104849_169
- expected not to be in P because "could we be that dumb that we haven't found a solution after having tried for that long?
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:
- P: would be boring on quantum computer
- NP-complete: would likely be impossible on a quantum computer
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: and . How such large primes are found: how large primes are found for RSA.
The public key is made of:
n = p*q- a randomly chosen integer exponent between
1ande_max = lcm(p -1, q -1), wherelcmis the Least common multiple
Given a plaintext message This operation is called modular exponentiation can be calculated efficiently with the Extended Euclidean algorithm.
m, the encrypted ciphertext version is:c = m^e mod nThe inverse operation of finding the private
m from the public c, e and 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:
- www.comparitech.com/blog/information-security/rsa-encryption/ has a numeric example