Revenge

第一次差分 记

第二次差分,消掉b 记 那么 于是 所以 对任意两个求gcd+爆破，得到m

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
d = [beta[i]*k[i+1] - beta[i+1]*k[i] for i in range(len(beta)-2)]
m = []
for i in d:
    for j in d:
        if i!=j:
          m.append(gcd(i,j))
m1 = []
for i in m:
    for j in m:
        if i!=j:
          m1.append(gcd(i,j))
km = min(m1)
for i in range(2,2^22):
    if km%i == 0 and km//i < 2**528 and km//i % 65536 == 0:
        m = km//i

求出m之后 由于k_1和m有公因数，得除掉 求出a

1
2
3
4
5
d = gcd(k[0],m)
k1 = k[0]//d
b1 = beta[0]//d
m1 = m // d
a = b1*inverse(k1,m1)%m

类似的求出b，c

1
2
3
d = gcd(y[0],m)
b = (y[1]//d*inverse(y[0]//d,m//d) - a*(x[0]+x[1]))%m
c = (x[1]-a*x[0]^2 - b*x[0])%m

然后解二次同余方程 $$
x_0 \equiv aseed^2+bseed+c \mod m
由于不是素数，得
x_0 \equiv aseed^2+bseed+c \mod 65536 \
x_0 \equiv aseed^2+bseed+c \mod \frac{m}{65536}
$$ 前者直接枚举爆破65536就行

后者是有限域二次同余方程，都能解

crt合一起，就求出seed