$2$ Optional: approximate GCD problem: GCD attack and lattice

attack

The Partial Approximate Common Divisor problem consists in recovering $p,$ given $x_0=p*q_0$

and polynomially many $x_i=p*q_i+r_i.$

Implement the brute force attack on the noise.

Implement the improved attack from $[3].$

Implement the lattice attack.

Compare the practical complexities of these attacks.