Hacker News Reader

Comment by smj-edison | Hacker News Reader

Wait, the article mentions that Shor's algorithm is factoring (which is what I understood), but then it's talking about elliptic curve cryptography? I thought ECC didn't use the same mathematical foundations of RSA, and RSA has been slowly phased out anyways...

View on HN

Shor published multiple quantum algorithms, including one for discrete logarithms. The term is sometimes used interchangeably.

They're closely related, ECC and RSA are both instances of the hidden subgroup problem.

Quite the contrary. Shor's algorithm actually works better for the shorter keys of ECC. The rule of thumb is 2n qbits for RSA keys and 6n qbits for ecc. I believe it has something to do with hownit applies to the hidden subgroup problem of finite abelian groups rather than factorisation, but I am really not a cryptographer not especially mathsy. I just asked the same question you did, and someone in the know pointed me to that.

> I thought ECC didn't use the same mathematical foundations of RSA

It kinda does, it just uses them differently

The basis here is the discrete inverse logarithm in a specific group (elliptic curves over rationals or multiplicative group module n)

It doesn't, but it's much harder to cheat with the DLP than it is with the IFP, which is what RSA is, which is why everyone announces records for RSA and ignores the fact that the actual problem to solve is the DLP. An example of how to cheat with the IFP is the "compiled Shor's algorithm" which produces the answer by non-quantum means and then throws in a quantum of quantum to make it look like magic happened.

Reply on news.ycombinator.com