4 ms·

Will the solution(s) to ABC proof be a nightmare to all security protocols relying on prime number factorization, such as RSA?

vhf 14y ago
No, it should not.
sold 14y ago
Whether ABC (or a similar conjecture) is proven has practically no cryptographic impact. This is because you can already write and execute algorithms (whose correctness depends on unsolved conjectures) without proving the conjectures. See http://math.stackexchange.com/questions/69540/would-a-proof-to-the-riemann-hypothesis-affect-security http://math.stackexchange.com/questions/69540/would-a-proof-...
cperciva 14y ago
No. A proof is a nice thing to have, but everybody assumes that ABC is true already.
kainosnoema 14y ago
Initially I had the same concern, but after digging a bit deeper, I don't believe this would be an immediate outcome. From the little I can gather, the ABC conjecture is really just a statement about the relationship between the operations of addition and multiplication on triples of coprime positive integers. While prime factors are involved in the conjecture, it doesn't seem that the proof of the conjecture would naturally lead to prime factorization in polynomial time. I'm not a mathematician though, and given how radical Mochizuki's proof sounds, I imagine it may (if it stands) eventually lead to more efficient factorization algorithms. Advances in computing power seem to be a more worrisome threat to RSA, especially for RSA-1024 whose factorization is probably already feasible (http://www.cs.tau.ac.il/~tromer/papers/cbtwirl.pdf http://www.cs.tau.ac.il/~tromer/papers/cbtwirl.pdf). And once advances in quantum computing become reality, quantum algorithms should be able to very quickly break even RSA-2048 (http://en.wikipedia.org/wiki/Shors_algorithm http://en.wikipedia.org/wiki/Shors_algorithm).
- Evbn 14y ago
  Are there practical reasons we couldn't switch to RSA-65536?
smegel 14y ago
Apart from cryptography, has prime number research and theorization produced any other practical applications?
- duaneb 14y ago
  Apart from the single technology that allows open communication and allowed the Internet to e.g. become a business haven...
- sold 14y ago
  Finite fields, essential to error-correcting codes, are based on properties of primes. This forms the basics of efficient data transfer, whether Internet, CDs or communication with spacecrafts. The book "Number Theory in Science and Communication" mentions that finite fields were used in verification of the fourth prediction of general relativity. See that book for more examples. Here's one from http://mathoverflow.net/questions/2556 http://mathoverflow.net/questions/2556: There is a gamma ray telescope design using mod p quadratic residues to construct a mask. Gamma rays cannot be focused, so this design uses a redundant array of detectors separated from the mask to reconstruct directional information. Cicidas have a cyclic life spanning a prime number of years. It is supposed that this is because a predator has harder job aligning with the cycle. http://en.wikipedia.org/wiki/Predator_satiation http://en.wikipedia.org/wiki/Predator_satiation I believe that the Möbius function is important in advanced physics: http://en.wikipedia.org/wiki/Mobius_function#Physics http://en.wikipedia.org/wiki/Mobius_function#Physics There's a legend that generals used the Chinese remainer theorem to count soldiers. Elementary number theory was a motivating factor and foundation for development of the whole mathematics - algebra, analysis, even logic. Did you know that proving Godel's incompleteness theorem requires using primes? http://mathoverflow.net/questions/19857/has-decidability-got-something-to-do-with-primes http://mathoverflow.net/questions/19857/has-decidability-got... Transcendence of pi also needs primes. http://mathoverflow.net/questions/21367/proof-that-pi-is-transcendental-that-doesnt-use-the-infinitude-of-primes http://mathoverflow.net/questions/21367/proof-that-pi-is-tra.... I did not realize that earlier. Usage of primes is often invisible. Even if there was no cryptography or ECCs, it would be silly to demand practical applications from this subject - it is a foundation for almost everything in mathematics, sometimes rather concealed.

vhf 14y ago

No, it should not.

sold 14y ago

Whether ABC (or a similar conjecture) is proven has practically no cryptographic impact. This is because you can already write and execute algorithms (whose correctness depends on unsolved conjectures) without proving the conjectures. See http://math.stackexchange.com/questions/69540/would-a-proof-to-the-riemann-hypothesis-affect-security http://math.stackexchange.com/questions/69540/would-a-proof-...

cperciva 14y ago

No. A proof is a nice thing to have, but everybody assumes that ABC is true already.

kainosnoema 14y ago

Initially I had the same concern, but after digging a bit deeper, I don't believe this would be an immediate outcome. From the little I can gather, the ABC conjecture is really just a statement about the relationship between the operations of addition and multiplication on triples of coprime positive integers. While prime factors are involved in the conjecture, it doesn't seem that the proof of the conjecture would naturally lead to prime factorization in polynomial time. I'm not a mathematician though, and given how radical Mochizuki's proof sounds, I imagine it may (if it stands) eventually lead to more efficient factorization algorithms. Advances in computing power seem to be a more worrisome threat to RSA, especially for RSA-1024 whose factorization is probably already feasible (http://www.cs.tau.ac.il/~tromer/papers/cbtwirl.pdf http://www.cs.tau.ac.il/~tromer/papers/cbtwirl.pdf). And once advances in quantum computing become reality, quantum algorithms should be able to very quickly break even RSA-2048 (http://en.wikipedia.org/wiki/Shors_algorithm http://en.wikipedia.org/wiki/Shors_algorithm).

Evbn 14y ago
Are there practical reasons we couldn't switch to RSA-65536?

smegel 14y ago

Apart from cryptography, has prime number research and theorization produced any other practical applications?

duaneb 14y ago
Apart from the single technology that allows open communication and allowed the Internet to e.g. become a business haven...
sold 14y ago
Finite fields, essential to error-correcting codes, are based on properties of primes. This forms the basics of efficient data transfer, whether Internet, CDs or communication with spacecrafts. The book "Number Theory in Science and Communication" mentions that finite fields were used in verification of the fourth prediction of general relativity. See that book for more examples. Here's one from http://mathoverflow.net/questions/2556 http://mathoverflow.net/questions/2556: There is a gamma ray telescope design using mod p quadratic residues to construct a mask. Gamma rays cannot be focused, so this design uses a redundant array of detectors separated from the mask to reconstruct directional information. Cicidas have a cyclic life spanning a prime number of years. It is supposed that this is because a predator has harder job aligning with the cycle. http://en.wikipedia.org/wiki/Predator_satiation http://en.wikipedia.org/wiki/Predator_satiation I believe that the Möbius function is important in advanced physics: http://en.wikipedia.org/wiki/Mobius_function#Physics http://en.wikipedia.org/wiki/Mobius_function#Physics There's a legend that generals used the Chinese remainer theorem to count soldiers. Elementary number theory was a motivating factor and foundation for development of the whole mathematics - algebra, analysis, even logic. Did you know that proving Godel's incompleteness theorem requires using primes? http://mathoverflow.net/questions/19857/has-decidability-got-something-to-do-with-primes http://mathoverflow.net/questions/19857/has-decidability-got... Transcendence of pi also needs primes. http://mathoverflow.net/questions/21367/proof-that-pi-is-transcendental-that-doesnt-use-the-infinitude-of-primes http://mathoverflow.net/questions/21367/proof-that-pi-is-tra.... I did not realize that earlier. Usage of primes is often invisible. Even if there was no cryptography or ECCs, it would be silly to demand practical applications from this subject - it is a foundation for almost everything in mathematics, sometimes rather concealed.