Hacker News Reader

Comment by throawaybong | Hacker News Reader

> it would require 13 × 10^6 physical qubits

It's 13 million qubits. It's weird they write it in scientific notation, it makes it look larger. If qubits got to the moore-like-bandwagon, that is not many multiplications away from current amount.

View on HN

Well, except that the approximate time for an additional "stable" qubit is currently plateauing, so outside a very lucky breakthrough, it's still unlikely. The official record for an actual running Shor's algorithm is 21 (not bits, just the number 21), which is still puny (there was an attempt to factor out 35 (again 35 as in 5×7), but it ended in failure due to quantum noise).

But Shor's algorithm is for prime factorization, right? Are there equally faster algorithms available for elliptic curves?

Shor's algorithm generalizes to any hidden subgroup problem for finite Abelian groups [1], which includes integer factoring and elliptic curve discrete log.

[1] https://en.wikipedia.org/wiki/Hidden_subgroup_problem

I don't believe there's a publicly-available algorithm that's faster than Shor's for breaking EC, and to clarify any misconception you can also use Shor's for EC (EC is actually easier to break with Shor's than RSA, but EC has the advantage of shorter keys for longer brute-forcing using known classical methods).

scientific notation would look more like "1.3 x 10*5" (only one leading digit: https://en.wikipedia.org/wiki/Scientific_notation#Normalized...)

Don't you mean 1.3 x 10 ^ 7?

Probably :)

Yes. It looks more like engineering notation (up to three digits to the left of the decimal and the power of 10 divisible by 3).

Reply on news.ycombinator.com