4 ms·
What Hot Dogs Can Teach Us About Number Theory
- miketery 5y agoThis was great. Now is there something like this for zk proofs?
- ghoda 5y agoWhat is a zk proof?
- forgotmypw17 5y ago"In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true, without conveying any information apart from the fact that the statement is indeed true. The essence of zero-knowledge proofs is that it is trivial to prove that one possesses knowledge of certain information by simply revealing it; the challenge is to prove such possession without revealing the information itself or any additional information." (Wikipedia) The "abstract examples" part of the article actually does a pretty good job of explaining the concept in a way I haven't encountered before, so I'm glad you asked this. https://en.wikipedia.org/wiki/Zero-knowledge_proof https://en.wikipedia.org/wiki/Zero-knowledge_proof
- gnicholas 5y agoDidn't know there was a term for two numbers that don't share a common factor, which is apparently called "relatively prime". I have not been able to succinctly refer to this concept when describing LCM calculations to my kid, so I'm excited to have learned about this term!
- aaaaaaaaaaab 5y agoIt's also called coprime. Usage: "10 and 9 are coprime" Edit: removed plural
- tromp 5y agoYou'd say 10 and 9 are coprime. Your plural incorrectly suggests that 10 is coprime and 9 is coprime.
- aaaaaaaaaaab 5y agoFair!
- DeathArrow 5y agoCompanies are using relative prime numbers to screw customers. My former phone provider had 30 days subscription periods, not accounting for 31, 29 and 28 days long months.
- FartyMcFarter 5y agoThe Chinese Remainder Theorem has a fascinating consequence, which is to enable the Residue Number System: https://en.wikipedia.org/wiki/Residue_number_system https://en.wikipedia.org/wiki/Residue_number_system For example, since 2 and 3 are coprime, if you store the residues of any number N modulo 2 and 3 separately, you can do additions, subtractions and multiplication modulo 6 by doing the same operations on the two residues (independently of each other). With this system it is possible to arithmetic on huge numbers in massively parallel fashion. The drawbacks are that division is hard (except when you know that the division is exact), overflow detection / comparison are hard, and converting from the residue number system to N is expensive.
- klyrs 5y agoA small gotcha you didn't mention: if you work modulo 2 and 3, then your results are only valid modulo 6 (generally, the product of your moduli). Unless you're happy with the assertion that 15*14==0, that is. I don't judge.
- FartyMcFarter 5y agoIf you know that you're working with numbers as big as 15 and 14, you could alternatively use more residues so that you can represent those numbers. If you don't know how big the numbers get, then you do run into the issue I mentioned of overflow detection being expensive.
- mensetmanusman 5y agoAnd Bagels about topology: http://georgehart.com/bagel/bagel.html http://georgehart.com/bagel/bagel.html
- ssivark 5y agoNice explanation! I wonder whether there are any generalizations of the remainder Chinese theorem to account for “noise” in the remainders (I.e. approximately correct residues), given redundancy of an overdetermined system. It’s easy to think about noise robustness if adding a little bit of noise changes the answer by a little, but with congruences, changing the residue by one can make the answer jump around all over the place!