Math and stuff
-
Modern Cryptography and Elliptic Curves: Chinese Remainder Theorem (r=2)
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...
-
What is Zero Knowledge Proof: Part 2
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...
-
What is Zero Knowledge Proof: Part 1
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...
-
Modern Cryptography and Elliptic Curves: Integer Solutions to 987654319=x2+y2+z2
Exercise from P.62 of Modern Cryptography and Elliptic Curves - A Beginner’s Guide. Are there integer solutions to 987654319=x2+y2+z2 No. By checking (4n+k)2(mod8) for each k=0,⋯,3, it becomes obvious that $m^2 \equiv 0, 1, 4 \pmod...
-
Modern Cryptography and Elliptic Curves: Examples of Division
Exercise from P.50 of Modern Cryptography and Elliptic Curves - A Beginner’s Guide. Show that 3∣0, but 0∤3. 3∣0⟺0/3=0∈Z. 3/0 is undefined, so 3/0∉Z. Show that if a∣b and b∣c,...