4 ms·

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

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)

pfortuny 8y ago
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.
the8472 8y ago
Certificates very much do use RSA. The ephemeral handshake commonly uses ECDH.
silur 8y ago
Elliptic curves are even more vulnerable to known quantum algorithms
ShaneCurran 8y ago
Kind of. Elliptic Curve can be reduced to the Discrete Logarithm problem, which a variant of Shor’s Algorithm solves in polynomial time.
moefh 8y ago
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 https://en.wikipedia.org/wiki/Hidden_subgroup_problem
wbhart 8y ago
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.
throwawaymath 8y ago
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.

pfortuny 8y ago

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.

the8472 8y ago

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

silur 8y ago

Elliptic curves are even more vulnerable to known quantum algorithms

ShaneCurran 8y ago

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

moefh 8y ago

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 https://en.wikipedia.org/wiki/Hidden_subgroup_problem

wbhart 8y ago

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.

throwawaymath 8y ago

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.