若智签到题我做不出来

题 (from SekaiCTF 2025)：

import random, osp = 2 ** 256 - 189
FLAG = os.getenv("FLAG", "SEKAI{}")def challenge(secret):t = int(input())assert 20 <= t <= 50, "Number of parties not in range"f = gen(t, secret)for i in range(t):x = int(input())assert 0 < x < p, "Bad input"print(poly_eval(f, x))if int(input()) == secret:print(FLAG)exit(0)else:print(":<")def gen(degree, secret):poly = [random.randrange(0, p) for _ in range(degree + 1)]index = random.randint(0, degree)poly[index] = secretreturn polydef poly_eval(f, x):return sum(c * pow(x, i, p) for i, c in enumerate(f)) % pif __name__ == "__main__":secret = random.randrange(0, p)for _ in range(2):challenge(secret)

简单分析：用 n 个点插值 n+1 个系数，插牛魔呢

牛魔：注意到 \(\varphi(2 ^{256} - 189)\) 有一个因子 29，于是我们轻松构造一个 29 次单位根来跑 NTT。（也就是个循环卷积）

然后就轻松得到 \(a_0 + a_{29}\) 以及其它所有系数了。也是插值。

很无聊，所以写了这篇博客，我的人生现在究竟在干什么