2 ms·

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 E

• bjoli 6mo ago
  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.
• lima 6mo ago
  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.
• raverbashing 6mo ago
  > 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)
• pseudohadamard 6mo ago
  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.