Timeline for Examples of common false beliefs in mathematics
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 4, 2019 at 1:24 | comment | added | TMM | @JohannesHahn I'd say the difference is that in cryptography, there do exist plenty reductions for other schemes proving that breaking these schemes implies solving the underlying well-studied hard problems. The whole hardness-hierarchy at least gives us some faith that some problems are probably really hard, but the RSA decoding problem is not connected to factoring in this hierarchy, let alone to any NP-hard problems. | |
| Apr 2, 2019 at 23:46 | comment | added | TMM | @KConrad This answer is referring to the fact that, unlike for the mentioned Rabin variant, the RSA problem is not known to be as hard as factoring: given an oracle that decrypts ciphertexts, there is no efficient way known to use this oracle to recover the factorization of the modulus. This in contrast to many other schemes and protocols, for which such an oracle would immediately yield the solution for the hard problem it is presumed to rely on. (And many would disagree with you that such oracle reductions are "not math"...) | |
| Feb 25, 2019 at 11:36 | comment | added | KConrad | ... "Breaking RSA" means somehow determining $d$ from $m$ and $e$, then you know $ed - 1$, which is a positive multiple of $\varphi(m)$, and there is a probabilistic algorithm that with over 50% probability of success each time will lead to a nontrivial factor of $m$ starting with a random choice of an integer from 1 to $m-1$. See Theorem 5.6 of kconrad.math.uconn.edu/blurbs/ugradnumthy/RSAnotes.pdf. If "Breaking RSA" means "a wizard tells you how to decode each message without explaining how it is done" then that's not math and thus can't be judged as being a false belief in math. | |
| Feb 25, 2019 at 11:33 | comment | added | KConrad | Unless you say what the term "breaking RSA" is supposed to mean then it's impossible to evaluate whether that is a false belief or not. For example, say $m = pq$ is an RSA modulus with two different primes $p$ and $q$ and $e$ and $d$ are encryption and decryption exponents for that modulus (so $e$ an$d$ are positive integers such that $ed \equiv 1 \bmod \varphi(m)$). In practice $e > 1$ and $d > 1$, and also in practice $p$ and $q$ are both odd. If "Breaking RSA" means somehow determining $\varphi(m)$ from $m$ and $e$ then you can factor $m$ from knowing $\varphi(m)$ and $m$. If (cont.) ... | |
| Mar 16, 2018 at 22:56 | comment | added | Johannes Hahn | I would put this on the same level as the "false belief" that NP-complete problems really are hard. Nobody knows for sure if it actually is false or not, but given the current state of affairs it is a somewhat reasonable conjecture. And the very fact that nobody knows how to do it means that in practical applications NP-complete problems really are hard to solve and breaking RSA really does require factorisation of the modulus. | |
| S Feb 20, 2018 at 18:52 | history | answered | TMM | CC BY-SA 3.0 | |
| S Feb 20, 2018 at 18:52 | history | made wiki | Post Made Community Wiki by TMM |