5 ms·
A new rare high-rank elliptic curve, and an orchard of Diophantine equations
- deleted 2y ago[deleted]
- miovoid 2y ago[deleted]
- madars 2y agoYour E/Fp has order 2^3 * 3 * 37991 * 21183269 * 373015308871 * 16071902378831708724506232718210977087913221837027589 and thus you can't hope for more than 86 bits of security due to Pohlig–Hellman, never mind cofactor attacks. encrypt() is also insecure (xor every byte of the message with the same shared secret byte), even if you chose a better curve.
- tptacek 2y agoThis is much better version of the sibling comment but I'm a message board nerd and can't keep myself from pointing out that this code is probably a little bit tongue-in-cheek.
- leijurv 2y ago`for char in message: encrypted_char = ord(char) ^ (shared_secret[0] % 256)` This is not real encryption, it picks only one byte of shared secret and XORs it into the plaintext. Therefore, there are only 256 possible decryption keys to check, which is trivial. Instead, you'd want to use the shared secret as a key to something strong and symmetric like AES.
- tptacek 2y agoI don't think it's meant to be real encryption.
- leijurv 2y agoI suspect it was, given that they've now deleted their comment.
- thechao 2y agoAny idiot knows not to use power-of-two! You gotta use "+13", which is prime and, therefore, *secure*.
- BobbyTables2 2y agoAnd Twice is nice!
- Jerrrrrrry 2y agoand more than thrice increases your chances of collision by
- deleted 2y ago[deleted]
- peter_d_sherman 2y ago[flagged]
- deleted 2y ago[deleted]
- Uptrenda 2y ago[flagged]
- Xcelerate 2y agoThis sounds very similar to the same process for Turing machines: https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/ https://www.quantamagazine.org/amateur-mathematicians-find-f... Determining the halting behavior of each successive Turing machine generally becomes harder and harder until eventually we reach a machine with Collatz-like behavior. The two problems are equivalent in some sense, but I wonder if there's an easy way to "port" over the work between the two projects.
- yorwba 2y agoThe equivalence of Diophantine equations and Turing machines is established by the MRDP theorem: https://en.wikipedia.org/wiki/Diophantine_set#Matiyasevich's_theorem https://en.wikipedia.org/wiki/Diophantine_set#Matiyasevich's... For every Diophantine equation P(x, y) = 0, where x is a tuple of integer parameters and y is a tuple of unknowns, there is a Turing machine that takes the parameters x as input and halts iff there is an integer solution y satisfying the equation (this direction is easy, just have the Turing machine test all tuples of integers in some order and halt iff it found a solution) and for every Turing machine, there is a Diophantine equation so that if x is an encoding of the Turing machine input, there is an integer solution y to the equation iff the the Turing machine halts for input x. (This direction is hard, you need to have y encode the execution history of the Turing machine somehow, and enforce the transition rules with the structure of the equation.)
- Xen9 2y agoI believe there is no better kind of feeling in all of mathematics & all of science than that which one may get from the knowledge that an an intuitive, possibly shaky idea they themselves suggested already exists as rigorous and useful theorem.
- fny 2y agoI feel like we’ve reached an era where information provenance is of paramount importance. This has always been an issue with fabricated data sets, but the ease at which anything can be fabricated—even a video—demands some new determinant of what is real and human born.
- fermigier 2y agoI broke the record back in 1992: Fermigier, Stéfane - Un exemple de courbe elliptique définie sur Q de rang ≥19. (French) [An example of an elliptic curve defined over Q with rank ≥19] C. R. Acad. Sci. Paris Sér. I Math. 315 (1992), no. 6, 719–722. And again in 1997: Fermigier, Stéfane - Une courbe elliptique définie sur Q de rang ≥22. (French) [An elliptic curve defined over Q of rank ≥22] Acta Arith. 82 (1997), no. 4, 359–363. Noam Elkies was already a major contributor to the field at the time. I dropped math to do computer stuff :)
- ykonstant 2y agoWhat kind of computer stuff are you doing now?
- anyon_fusion 2y agowhat made you drop math for computer stuff, if you don't mind sharing? (I'm in a similar boat)
- fermigier 2y agoI guess I thought that I could make a bigger dent in the universe as an open source entrepreneur than as a mathematician. Also, the fact that, at the time, the decision to switch course was not irreversible, given a new French law that had passed shortly before (i.e. I could go back to the university where I was already tenured if I didn't succeed in 6 years).
- ykonstant 2y agoGreat write-up; I need to review how GRH is used to prove bounds on the rank of elliptic curves. Also, the talk about polynomial parametrizations reminded me of the first Diophantine equation I solved in high school: (a^2+b^2)/(a+b) = (c^2+d^2)/(c+d). I had initially thought it had finitely many solutions, but then Nikos Tzanakis corrected me and told me I am missing many. So I toiled for two entire days and found the complete 2-parameter polynomial family of solutions.