What Hot Dogs Can Teach Us About Number Theory | Hacker News Reader

What Hot Dogs Can Teach Us About Number Theory

quantamagazine.org

38 pointspseudolus13 comments

The Chinese Remainder Theorem has a fascinating consequence, which is to enable the 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.

A 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.

If 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.

Didn'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!

It's also called coprime.

Usage: "10 and 9 are coprime"

Edit: removed plural

You'd say 10 and 9 are coprime.

Your plural incorrectly suggests that 10 is coprime and 9 is coprime.

Fair!

This was great. Now is there something like this for zk proofs?

What is a zk proof?

"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

Nice 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!

Companies 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.

And Bagels about topology:

http://georgehart.com/bagel/bagel.html

Reply on news.ycombinator.com