Flag - printer#

• encoded.txt
• flag_printer.py

import galois
import numpy as np
MOD = 7514777789

points = []

for line in open('encoded.txt', 'r').read().strip().split('\n'):
    x, y = line.split(' ')
    points.append((int(x), int(y)))

GF = galois.GF(MOD)

matrix = []
solution = []
for point in points:
    x, y = point
    solution.append(GF(y % MOD))

    row = []
    for i in range(len(points)):
        row.append(GF((x ** i) % MOD))
    
    matrix.append(GF(row))

open('output.bmp', 'wb').write(bytearray(np.linalg.solve(GF(matrix), GF(solution)).tolist()[:-1]))

Solution#

Ta thấy rằng file encoded.txt bao gồm tập hợp các điểm với $x$ nằm từ 0 —> 1769610 và giá trị y random. Và code mẫu đề bài cho là thực hiện giải ma trận dưới đây, tuy nhiên nó chạy rất chậm và độ phức tạp là $O(n^3)$

$\begin{bmatrix} a_0 \\ a_1 \\ a_2 \\ a_3 \\ \vdots \\ a_n \\ \end{bmatrix} \begin{bmatrix} 0^0 & 0^1 & 0^2 & 0^3 & \dots & 0^n \\ 1^0 & 1^1 & 1^2 & 1^3 & \dots & 1^n \\ 2^0 & 2^1 & 2^2 & 2^3 & \dots & 2^n \\ 3^0 & 3^1 & 3^2 & 3^3 & \dots & 3^n \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ n^0 & n^1 & n^2 & n^3 & \dots & n^n \\ \end{bmatrix} = \begin{bmatrix} y_0 \\ y_1 \\ y_2 \\ y_3 \\ \vdots \\ y_n \\ \end{bmatrix}$

Sau một lúc osint thì ta nhận thấy rằng đây là ma trận Vandermonde và nó liên quan đến Larange interpolation (nội suy larange). Và ta có được công thức:

$f(x)=\sum_{i=1}^{n+1} f(x_i) * \prod_{j\neq i \ j = 1}^{n+1} \frac{x-x_j}{x_i-x_j}$

Cùng với đó ta cũng tìm thấy được một blog: https://codeforces.com/blog/entry/94143

Đầu tiên ta sẽ giảm độ phức tạp của việc tính $\prod_{j\neq i}(x_i-x_j)$

Thay vì với mỗi vòng lặp ta sẽ chạy lại để tính thì ta có thể làm như sau:

$\prod_{j\neq i}(x_i-x_j)$ = $\lim_{x\to x_i}\frac{\prod_{j=1}^{n+1} (x-x_j)}{x-x_i}$

Ở đây to có thể nhân hết vào và chia đi $x_i - x_i$. Điều tuyệt vời là ta có thể sử dụng lim để xử lý việc $x_i - x_i = 0$

$\lim_{x\to x_i}\frac{\prod_{j=1}^{n+1} (x-x_j)}{x-x_i}=\lim_{x\to x_i}\frac{d}{dx}(\prod_{i=1}^{n+1} x-x_j)$

Thế nên việc của ta là chỉ cần tìm $P'(x)$ với $P(x) = \prod_{i=1}^{n+1} x-x_j$ rồi thế từng $x_i$ vô.

Tiếp theo ta sẽ đến giảm độ phức tạp của việc nhân nhiều đa thức

Ta biết rằng nhân đa thức trong sage có $O(n \ log(n))$

Giả sử có m đa thức thì nếu nhân từ từ từng đa thức lại với nhau ta sẽ mất $O(m * n log(n))$

Còn nếu ta sử dụng chia để trị để nhân đa thức thì ta sẽ mất $(nlog(n) * log(m))$

Giờ việc cuối cùng của ta là là thiết lập công thức

Đặt $v_i=\frac{y_i}{P'(x_i)}$

—> $f(x)=\sum_{i=1}^{n+1} v_i\prod_{j\neq i}(x-x_j)$

$f(x)=f_0(x)P_1(x)+f_1(x)P_0(x)$ với:

• $f_0(x)=\sum_{i=1}^{\lfloor\frac{n+1}{2}\rfloor} v_i\prod_{j\neq i,1\leq j\leq \lfloor\frac{n+1}{2}\rfloor}(x-x_j)$
• $f_1(x)=\sum_{i=\lfloor\frac{n+1}{2}+1\rfloor}^{n+1} v_i\prod_{j\neq i,\lfloor\frac{n+1}{2}\rfloor\leq j\leq n+1}(x-x_j)$
• $P_0(x)=\prod_{1\leq j\leq \lfloor\frac{n+1}{2}\rfloor}(x-x_j)$
• $P_1(x)=\prod_{\lfloor\frac{n+1}{2}\rfloor\leq j\leq n+1}(x-x_j)$

Code dưới đây đã mất tầm 6 - 7 tiếng để chạy và mình đã để chạy qua đêm để ra FLAG. (huhu)

from tqdm import tqdm

MOD = 7514777789

points = []

for line in open('encoded.txt', 'r').read().strip().split('\n'):
    x, y = line.split(' ')
    points.append((int(x), int(y)))

F = GF(MOD)
R.<x> = F['x']

def multiply_poly_list(poly_list):
    if len(poly_list) == 1:
        return poly_list[0]
    n = len(poly_list) // 2
    return multiply_poly_list(poly_list[:n]) * multiply_poly_list(poly_list[n:])

P = multiply_poly_list([x - i for i in range(len(points))])
d_P = derivative(P)

def calc_poly(points, start_index, bar):
    bar.update(int(1))
    n = len(points)
    if n == 1:
        x_i = points[0][0]
        y_i = points[0][1]
        v = y_i / d_P(x_i)
        return v


    f0 = calc_poly(points[:n//2], start_index, bar)
    f1 = calc_poly(points[n//2:], start_index + n//2, bar)

    p0 = multiply_poly_list([x - (i + start_index) for i in range(n//2)])
    p1 = multiply_poly_list([x - (i + start_index) for i in range(n//2, n)])
    return f0 * p1 + f1 * p0

n = 2 * len(points) - 1
bar = tqdm(total=int(n))
poly = calc_poly(points, 0, bar)
coeffs = poly.numerator().list()

with open('out.txt', 'w') as f:
    f.write('\n'.join([str(i) for i in coeffs]))

print("Finished")

listarr = [int(_) for _ in open("out.txt", "r").read().strip().split('\n')]

print(listarr)

open('output.bmp', 'wb').write(bytearray(listarr[:-1]))