# Problem set 2: Introduction to polynomials commitments tutorial

## Modular arithmatic

### Show number space
Write a program that prints x % p for all x in X [0, p]

def show_space(x, p):
    out = []
    for i in x: 
        out.append(i % p)

### Make a table that shows the multiplitive results for x * y % p for all x and y.

#### Example x * y % 3

| | 1 | 2|
| -------- | -------- | -------- |
| 1 | 1 | 2 |
| 2 | 2 | 1 |

#### Write a program to evaluate x** 6 + x** 4 + x**2 + x + 1 % p, at the point x = 2

How many multiplications do you need to do ?

## Eliptic curve
### Implement the eliptic curve point addition


Don't forget the modulo 😉.
`a` and `d` are constants that Barry didn't give us.

### Test vectors

Set `a` = `d` = 1, and `p` = 7, then you should get:
* (2, 1) + (3, 4) = (1, 2)
* (0, 1) + (1, 0) = (1, 0)

Note, these have only been checked by GPT4 - should confirm with a human 🧠

---

## KZG
#### NOTE: Use the [PY-ECC lib in python](https://github.com/ethereum/py_ecc) for multiplication

from py_ecc import bn128
multiply = bn128.bn128_curve.multiply

### Implement Powers of tau

Using Multiplicaions

Anyone have a link that explains what this is?
Barry didn't give us any spec, but the [KZG Summonooors](https://github.com/ethereum/kzg-ceremony-specs) did!

### Remainder trick

KZG uses this remainder trick to make sure something is part of a polynomial.

Use the same remainder trick to check if an int is part of a bigger int.

# check if x is in y

if x/y == floor(x/y):
    print("no remainder")
else: 
    print("remainder")
    

Use this to test various numbers.

### Polynomials remainders

#### Check if $Q(x)\frac{x^2 + x + 1}{x+1}$ has a remainder ?

#### Check if $R(x)\frac{x^2 + x + 1}{x+2}$ has a remainder ?

### User KZG to commit to A(x)

$A(x) = x^3 + 5x^2 + 4x + 2 $

### Open A(x) at point x = 2

$QX = \frac{AX - 6 }{x+2}$

$QX * (x+2) = AX - 6 $

What did you learn by trying to commit to both of them ?

## Fri
### Statistical proofs

We are going to simulate the merkle tree stuff to make it easier to move fast ;)

Its trivial to make it non interactive and succinct with merkle proof s

#### Make a function that evaluates

P(x) = $x^3 + x^2 + x + 1$

at a point x

#### Evaluate this function at 10 random points

#### Use this to do polynomial addition
P(x) + p(x)

#### Use this to do polynomail multplicaion
P(x) * P(x)

### Fri

#### Make degree reduction using

X(x) = x*P(x) + R(x)

#### Check the degree reduction using statisitical proofs

### Optional homework

Add merkle proofs

## IPA commitments

`5x**3 + 2x**2 + 6x + 888`

`5*G3 + 2*G2 + 6*G1 + 888*G0 `