import sage.all
from sage.modules.free_module_integer import IntegerLattice
import os
import sys

Q = 31337
P = 2**64
W = 31337
MIDDLE_LETTER = ord("n")


def poly_hash(a):
    if type(a) == str:
        a = a.encode()
    h = 0
    for el in a:
        h = (h * Q + el) % P
    return h


def string_for_target_hash(target: int, string_len: int = 200) -> bytes:
    known = [MIDDLE_LETTER] * string_len
    known_hash = poly_hash(known)
    L = IntegerLattice(
        [
            [W * Q ** (len(known) - i - 1)]
            + [1 if j == i else 0 for j in range(len(known))]
            for i in range(len(known))
        ]
        + [[W * P] + [0] * len(known)]
    )
    vector = L.approximate_closest_vector(
        [W * (target - known_hash)] + [0] * len(known)
    )
    print(vector)
    return bytes(k + v for k, v in zip(known, vector[1:]))