import logging
import os
import sys
from itertools import product
from math import gcd
from sage.all import ZZ
path = os.path.dirname(os.path.dirname(os.path.dirname(os.path.realpath(os.path.abspath(__file__)))))
if sys.path[1] != path:
sys.path.insert(1, path)
from shared import small_roots
def attack(N, a, rho, t=1, k=1, roots_method="groebner"):
"""
Solves the ACD problem using the multivariate polynomial approach.
More information: Galbraith D. S. et al., "Algorithms for the Approximate Common Divisor Problem" (Section 5)
:param N: N = p * q0
:param a: the a samples, with ai = p * qi + ri
:param rho: the bit length of the r values
:param t: the parameter t (default: 1)
:param k: the parameter k (default: 1)
:param roots_method: the method to use to find roots (default: "groebner")
:return: the secret integer p and a list containing the r values, or None if p could not be found
"""
assert len(a) > 0, "At least one a value is required."
assert t >= k, "t must be greater than or equal to k."
R = 2 ** rho
pr = ZZ[tuple(f"x{i}" for i in range(len(a)))]
x = pr.gens()
X = [R] * len(x)
logging.debug("Generating shifts...")
shifts = []
for i in product(*[range(t + 1) for _ in x]):
if sum(i) <= t:
l = max(k - sum(i), 0)
fi = N ** l
for m in range(len(i)):
fi *= (x[m] - a[m]) ** i[m]
shifts.append(fi)
B, monomials = small_roots.create_lattice(pr, shifts, X)
B = small_roots.reduce_lattice(B)
polynomials = small_roots.reconstruct_polynomials(B, None, N ** k, monomials, X)
for roots in small_roots.find_roots(pr, polynomials, method=roots_method):
r = [roots[xi] for xi in x]
if all(-R < ri < R for ri in r):
return int(gcd(N, a[0] - r[0])), r
