---
# System prepended metadata

title: 'Problem set 2: Introduction to polynomials commitments tutorial'

---

# 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]

``` python3 
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 

![](https://i.imgur.com/pnTdfRQ.png)

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. 

``` python

# 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 `

