Hacker News Reader

Comment by wavegeek | Hacker News Reader

At one point I thought I had found a fast factoring algorithm but I found that the internet no longer much depends on the difficulty of factoring large numbers and stopped work on the project.

Elliptic Curve encryption for example does not depend (AFAIK) on the difficulty of factoring. (please tell me if this is wrong)

View on HN

Elliptic curve crypto (the kind that is in common use, like ECDH) is just as broken by quantum computers as RSA.

The quantum algorithm that breaks RSA (Shor's algorithm) does it by efficiently solving the hidden subgroup problem[1] for finite Abelian groups. This can be used for factoring integers (which breaks RSA) and also for solving discrete logarithms (which breaks elliptic curve crypto).

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

The other answers have given good info, but speaking to your supposed factoring algorithm in particular - most of the internet's public key cryptography still relies on factoring problems. Your algorithm would be enormously useful and dangerous. You would likely be able to break anything that reduces to the hidden subgroup problem using it, which means you'd be breaking both elliptic curve and non-elliptic curve systems.

Kind of. Elliptic Curve can be reduced to the Discrete Logarithm problem, which a variant of Shor’s Algorithm solves in polynomial time.

There are many applications of a fast factoring algorithm in number theory, and many people who would love to get their hands on one for that reason. You'd be exceptionally famous if you developed a very fast algorithm for this. That is to say nothing of the fact that it would say something about the fundamental complexity of various problems.

Certificates very much do use RSA. The ephemeral handshake commonly uses ECDH.

At some time we shall discover that Shor’s algorithm is polynomial but the greatest monomial has a constant of size 10^30000 and we shall go on living.

Elliptic curves are even more vulnerable to known quantum algorithms

Reply on news.ycombinator.com