5 ms·
I didn't down vote you but here are a few remarks about your comment: >> [..] but it is a lot more efficient for some of them. > Technically correct Not quit
by weinzierl 10y ago
I didn't down vote you but here are a few remarks about your comment:
>> [..] but it is a lot more efficient for some of them.
> Technically correct
Not quite.
We know algorithms which have better time complexity on a quantum than any known classical algorithm that solves the same problem. Shor's algorithm is an example. We are not sure if a classical algorithm with the same time complexity exists.
>Factorization for example, that's why public key encryption works (we can't brute force it), but a quantum computer could.
Most (all?) modern public key algorithms are not based on the integer factorization problem.
- cyphar 10y ago> >Factorization for example, that's why public key encryption works (we can't brute force it), but a quantum computer could. > Most (all?) modern public key algorithms are not based on the integer factorization problem. There are analogues for Shor's algorithm for the discrete logarithm and other similar problems.
- PeCaN 10y agoShor's algorithm covers discrete logarithm also. But most modern asymmetric algorithms are based on elliptic curves and other problems that quantum computers don't help with.
- serendipitous 10y agoThe ECC algorithms used today rely on the "Elliptic Curve Discrete Logarithm Problem" and are very much vulnerable to (a version of) Shor's algorithm. Some would even say they are more vulnerable than RSA due to the much smaller key sizes (requiring less qubits).