import os
import sys
from math import ceil
from math import log2
from math import sqrt
from sage.all import QQ
from sage.all import matrix
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.lattice import shortest_vectors
def attack(a, s):
"""
Tries to find e_i values such that sum(e_i * a_i) = s.
This attack only works if the density of the a_i values is < 0.9048.
More information: Coster M. J. et al., "Improved low-density subset sum algorithms"
:param a: the a_i values
:param s: the s value
:return: the e_i values, or None if the e_i values were not found
"""
n = len(a)
d = n / log2(max(a))
N = ceil(1 / 2 * sqrt(n))
assert d < 0.9408, f"Density should be less than 0.9408 but was {d}."
L = matrix(QQ, n + 1, n + 1)
for i in range(n):
L[i, i] = 1
L[i, n] = N * a[i]
L[n] = [1 / 2] * n + [N * s]
for v in shortest_vectors(L):
s_ = 0
e = []
for i in range(n):
ei = 1 - (v[i] + 1 / 2)
if ei != 0 and ei != 1:
break
ei = int(ei)
s_ += ei * a[i]
e.append(ei)
if s_ == s:
return e
