Skip to main content

Prerequisite Understanding Questions

You should be reasonably confident that you'd be able to solve most of the problems below, given some time and a bit of Googling.

If you're comfortable solving these problems, you should have the necessary background for writing ZK circuits!

Here is a good reference for number theory topics.

Modular arithmetic

  1. Without using a calculator, compute the remainder when 20212017220212017^2 is divided by 2021202220212022.
  2. Cycles
    1. What is the third-smallest positive value of xx for which 2x3(mod13)2^x \equiv 3 \pmod{13}?
    2. What is the fourth-smallest positive value of xx for which 2x8(mod101)2^x \equiv 8 \pmod{101}?
  3. Chinese Remainder Theorem
    1. Describe all integers nn such that n3(mod5)n \equiv 3 \pmod{5} and n6(mod7)n \equiv 6 \pmod{7}.
    2. Describe all integers nn such that n5(mod6)n \equiv 5 \pmod{6}, n6(mod7)n \equiv 6 \pmod{7}, and n7(mod8)n \equiv 7 \pmod{8}.
  4. Modular inverses
    1. Describe all integers nn such that 5n+72(mod13)5n + 7 \equiv 2 \pmod{13}.
    2. Describe all integers nn such that 3n+94(mod12)3n + 9 \equiv 4 \pmod{12}.
    3. Describe all integers nn such that 3n+93(mod12)3n + 9 \equiv 3 \pmod{12}.
    4. Describe all integers nn such that 19n1(mod257)19n \equiv 1 \pmod{257}.

Polynomials

  1. Solve for xx: (x1)(x+2)(x3)(x+4)>0(x-1)(x+2)(x-3)(x+4) > 0.
  2. Describe all nn such that (n2)(n3)0(mod97)(n-2)(n-3) \equiv 0 \pmod{97}.
  3. Describe all nn such that (n2)(n3)0(mod72)(n-2)(n-3) \equiv 0 \pmod{72}.
  4. Suppose that f(x)f(x) is a polynomial with leading coefficient 11 such that f(0)=10f(0) = 10. What is the product of the roots of f(x)f(x), if f(x)f(x) has an even degree? What if f(x)f(x) has an odd degree? If f(x)f(x) had leading coefficient 55, how would this change?
  5. Find the sum of the squares of the roots of the polynomial x43x3+12x2x+15=0x^4 - 3x^3 + 12x^2 - x + 15 = 0.

Miscellaneous

  1. Suppose you had an efficient algorithm to factor arbitrarily large numbers. How could you use such an algorithm to decrypt messages not meant for you, that are encrypted with an RSA encryption scheme?
  2. Many online services which require user authentication store hashed passwords, rather than plaintext passwords.
    1. Explain the rainbow attack: an attack by which an attacker can derive a substantial fraction of plaintext passwords from a leaked table of hashed passwords.
    2. Explain how to use salting to prevent a rainbow attack.
  3. What is the difference between a Merkle tree and a hash list? When would you want to use a Merkle tree instead of a hash list?