Processing math: 100%
  • 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 30, but 03. 300/3=0Z. 3/0 is undefined, so 3/0Z. Show that if ab and bc,...