Math and stuff

Exercise from P.71 of Modern Cryptography and Elliptic Curves - A Beginner’s Guide. Let $m, n > 1$ be coprime integers, and let $a, b$ be arbitrary integers. Then the following system of congruences has a unique solution modulo $mn$. \[\begin{align*} x &\equiv a \pmod m \\ x &\equiv b...

This post is inspired by “Why and How zk-SNARK Works: Definitive Explanation” by Maksym Petkus. Proof that you know a polynomial The last post explains a (over) simplified version of what ZK is. Also, we talked about how polynomials are secretly important. We will first develop a baby approach that...

This post is inspired by “Why and How zk-SNARK Works: Definitive Explanation” by Maksym Petkus. What is Zero Knowledge Proof (ZKP)? Zero-knowledge proof is a field in cryptography that allows people to communicate something without additional information. Here’s a simplified, watered-down version of the famous problem called the Ali Baba...

Exercise from P.62 of Modern Cryptography and Elliptic Curves - A Beginner’s Guide. Are there integer solutions to $987654319 = x^2 + y^2 + z^2$ No. By checking $(4n + k)^2 \pmod 8$ for each $k = 0, \cdots, 3$, it becomes obvious that $m^2 \equiv 0, 1, 4 \pmod...

Exercise from P.50 of Modern Cryptography and Elliptic Curves - A Beginner’s Guide. Show that $3 \mid 0$, but $0 \not\mid 3$. $3 \mid 0 \iff 0/3 = 0 \in \mathbb{Z}$. $3 / 0$ is undefined, so $3/0 \not\in \mathbb{Z}$. Show that if $a \mid b$ and $b \mid c$,...