solv.sage

from tqdm import tqdm

q = 7937
F = GF(q)
P.<X> = PolynomialRing(F)
R.<Xbar> = P.quotient(X^256 + 1)

zeta = 2805
points = [4074, 1455, 891, 5096, 28, 6122, 2068, 704, 4580, 6480, 4182, 5243, 2685, 1102, 2504, 3812, 211, 1006, 7596, 1530, 799, 5539, 727, 3313, 1335, 1226, 6120, 2296, 2504, 447, 1902, 3393, 6614, 3827, 1532, 116, 5742, 7236, 80, 2688, 7754, 1563, 1918, 3739, 6177, 6805, 4307, 2005, 5423, 611, 2984, 7520, 1011, 6977, 4891, 3979, 5721, 539, 4055, 4990, 2175, 564, 4938, 4655, 6569, 7444, 6491, 2228, 4736, 1548, 5946, 6654, 4460, 4072, 6491, 7305, 2156, 2147, 3373, 4322, 6628, 4691, 6763, 6320, 37, 4509, 7870, 4644, 4028, 7076, 2827, 1921, 2992, 7316, 4806, 1375, 7264, 1471, 7446, 3743, 4069, 7613, 1284, 7933, 3439, 6909, 4150, 1543, 2862, 3452, 5114, 131, 246, 1700, 5230, 6932, 7176, 6984, 6837, 183, 2960, 2006, 6865, 1741, 3669, 7709, 7777, 5212, 6425, 3948, 5257, 7185, 4391, 4539, 2458, 1407, 2293, 1669, 3473, 5785, 6692, 7882, 4209, 4828, 3434, 4506, 5839, 6578, 6587, 7797, 2449, 6569, 3129, 1508, 4449, 6797, 1769, 4347, 7250, 751, 3892, 4899, 2216, 1746, 926, 1803, 3985, 705, 7416, 7029, 3965, 732, 4212, 175, 5538, 5673, 7441, 1352, 233, 1949, 7343, 2137, 3740, 1802, 3616, 6728, 5792, 433, 606, 6487, 4409, 4080, 1699, 967, 2789, 6314, 3146, 7452, 510, 4973, 1970, 5900, 5413, 1254, 146, 7665, 5124, 3622, 6258, 4063, 3456, 5228, 1387, 7359, 5885, 997, 3072, 884, 2780, 0, 222, 4840, 1193, 4913, 984, 2608, 2291, 1551, 6595, 7810, 5811, 7147, 682, 5000, 4413, 7743, 6106, 4231, 4336, 6047, 3478, 1935, 6396, 2303, 4407, 6919, 4488, 5276, 2171, 5376, 7662, 700, 3059, 1277, 4674]

def br(x):
  y = 0
  for i in range(7):
    y <<= 1
    y |= (x >> i) & 1
  return y

M = [X^2 - zeta^(2*br(i) + 1) for i in range(128)]
for x0 in tqdm(range(q)):
  f = P.lagrange_polynomial([(0, x0)] + [(i+1, y) for i, y in enumerate(points)])
  fl = list(f)
  twos = [P(fl[i:i+2]) for i in range(0, 256, 2)]
  g = crt(twos, M)
  w = [c // 61 for c in list(g)]
  if all(0 < c < 256 for c in w):
    print(bytes(w).decode())
    break