ZK-Bootcamp - Homework 1 - Modular Arithematic

This post hosts my homework for my studies at the ZK Bootcamp conducted by Rareskills.

For all problems below, assume the finite field is p = 71.

Remember, this is done in a finite field so your answer should only contain numbers [0-70] inclusive. There should be no fractions or negative numbers.

    p = 71

Problem 1

Find the elements in a finite field that are congruent to the following values:

• -1

    pow(-1, -1, p)

• -4

    pow(-4, -1, p)

• -160

    pow(-160, -1, p)

• 500

    pow(500, -1, p)

Problem 2

Find the elements that are congruent to a = 5/6, b = 11/12, and c = 21/12

Verify your answer by checking that a + b = c (in the finite field)

    # a = 5/6 = 5 * 6^-1
    # 6^-1 = 6^(p-2) mod p - using Fermat's Little Theorem
    a = (5 * pow(6, p-2, p))%p
    # b = 11/12 = 11 * 12^-1
    # 12^-1 = 12^(p-2) mod p
    b = (11 * pow(12, p-2, p))%p
    # c = 21/12 = 21 * 12^-1
    # 12^-1 = 12^(p-2) mod p
    c = (21 * pow(12, p-2, p))%p
    
    assert (a + b)%p == c

Problem 3

Find the elements that are congruent to a = 2/3, b = 1/2, and c = 1/3.

Verify your answer by checking that a * b = c (in the finite field)

    # a = 2/3 = 2 * 3^-1
    # 3^-1 = 3^(p-2) mod p - using Fermat's Little Theorem
    a = (2 * pow(3, p-2, p))%p
    # b = 1/2 = 1 * 2^-1
    # 2^-1 = 2^(p-2) mod p
    b = (1 * pow(2, p-2, p))%p
    # c = 1/3 = 1 * 3^-1
    # 3^-1 = 3^(p-2) mod p
    c = (1 * pow(3, p-2, p))%p
    
    assert (a * b)%p == c

Problem 4

The inverse of a 2 x 2 matrix $A$ is

where $A$ is

And the determinant det is

Compute the inverse of the following matrix in the finite field:

Verify your answer by checking that

Where $I$ is the identity matrix.

    import numpy as np
    a = 1
    b = 1
    c = 1
    d = 4
    A = np.array([[a, b], [c, d]])
    det = (a * d - b * c) % p
    det_inv = pow(det, -1, p)
    A_inv = (det_inv * np.array([[d, -b], [-c, a]])) % p
    I = np.array([[1, 0], [0, 1]])
    assert (A @ A_inv % p == I).all()

Problem 5

What is the modular square root of 12?

Verify your answer by checking that x * x = 12 (mod 71)

Use brute force to find the answer (in Python)

    root = 0
    for i in range(1, p):
        square = (i * i) % p
        if square == 12:
            root = i
            break
    assert (root*root % p == 12)
    print(f"The square root of 12 mod {p} is {root}")

Problem 6

Suppose we have the following polynomials:

What is p(x) + q(x)? What is p(x) * q(x)?

Use the galois library in Python to find the roots of p(x) and q(x).

What are the roots of p(x)q(x)?

\(p(x)+q(x)=52x^2+24x+61 + 40x^2+40x+58\\ = (52+40)x^2 + (24+40)x + (61+58)\\ = 92x^2 + 64x + 119\\\) \(p(x)*q(x)=52x^2+24x+61 * 40x^2+40x+58\\ = 52x^2(40x^2+40x+58) + 24x(40x^2+40x+58) + 61(40x^2+40x+58)\\ = 2080x^4 + 2080x^3 + 3016x^2 + 960x^3 + 960x^2 + 1392x + 2440x^2 + 2440x + 3538\\ = 2080x^4 + (2080+960)x^3 + (3016+960+2440)x^2 + (1390+2440)x + 3538\\ = 2080x^4 + 3040x^3 + 6416x^2 + 3830x + 3538\)

    import galois
    
    GF = galois.GF(p)
    p = galois.Poly([52,24,61], field=GF)
    roots = p.roots() # 34, 42
    print(f"The roots of the polynomial {p} are {roots}") 
    q = galois.Poly([40,40,58], field=GF)
    roots = q.roots() # None
    print(f"The roots of the polynomial {q} are {roots}")
    pq = p * q
    roots = pq.roots() # 34, 42
    print(f"The roots of the polynomial {pq} are {roots}")

Problem 7

Find a polynomial f(x) that crosses the points (10, 15), (23, 29).

Since these are two points, the polynomial will be of degree 1 and be the equation for a line (y = ax + b).

Verify your answer by checking that f(10) = 15 and f(23) = 29.

    x1 = 10
    y1 = 15
    x2 = 23
    y2 = 29
    a = (y2 - y1)/(x2 - x1)
    b = y1 - a * x1
    poly = galois.Poly([a,b], field=GF)
    assert poly(10) == 15
    assert poly(23) == 29

Problem 8

What is Lagrange interpolation and what does it do?

Find a polynomial that crosses through the points (0, 1), (1, 2), (2, 1).

Use this Stackoverflow answer as a starting point: https://stackoverflow.com/a/73434775

Lagrange interpolation: If 2 points are on a a Cartesian plane, a line can be defined between them.

If d+1 points are on a Cartesian plane, we can define a polynomial of max d degree

    GF = galois.GF(p)
    x = GF([0,1,2])
    y = GF([1,2,1])
    galois.lagrange_poly(x,y)