Cubic Math#

1
secret = randrange(2**256)
2

3
primes = []
4
p = secret
5
while len(primes) < 10:
6
    p = next_prime(p)
7
    primes.append(p)
8

9
for _ in range(50):
10
    a, b = map(int, input("a, b = ").split(","))
11
    if a == secret:
12
        print(FLAG)
13
        exit()
14
    if not (-2**31 <= a < 2**31 and -2**31 <= b < 2**31):
15
        exit(1)
16

17
    res = []
18
    for p in primes:
19
        R.<x> = PolynomialRing(GF(p))
20
        if (x^3+a*x+b).is_irreducible():
21
            res.append(p-secret)
22
    print(res)

这题的逻辑很简单，给十个连续的素数，每次询问一个三次多项式 $x^3+ax+b$ 模 $p_i$ 下是否可约，如果不可约就输出到 secret 的距离。

首先这题看起来跟椭圆曲线很像，实则毫无关系，因为椭圆曲线这个是否可约没啥性质。所以我们直接来考察三次多项式的可约性。

我们可以从两个角度考察三次多项式。首先，可约等价于它在模$p$下有一个根，这可以用gcd(x**p-x, ?)来判断。但我们不知道secret，所以行不通。所以我们只能从三次方程求根公式想办法。

对于方程 $x^3+px+q=0$，它的解长这样

对称的 $\omega u_1+\omega^2u_2$ 和 $\omega^2 u_1+\omega u_2$ 也都是解。

首先，模$p$下的三次剩余现在仍然没做完，所以能不惹就先不惹。那我们就先考虑 $\sqrt{\frac{q^2}{4} + \frac{p^3}{27}}$ 这个二次剩余的部分。三次方程有一个判别式 $\Delta=-(4p^3+27q^2)$，当 $\Delta\geq 0$ 时，方程有三个实根；当 $\Delta<0$ 时，方程有一个实根和两个共轭复根。这个式子在模 $p$ 下也有意义，我们可以认为 $\Delta\geq 0$ 相当于模 $p$ 下是二次剩余。而 $\Delta<0$ 相当于模 $p$ 下不是二次剩余，会产生一个扩域。所以 $\Delta$ 不是二次剩余时，在扩域上有一对共轭的根，这个二次项是不可约的，然后剩下的一个根就不得不回退到 $F_p$，故而可约。

所以判别式相当于告诉了我们这样一件事，如果这个多项式不可约，那么 $\Delta$ 是二次剩余，但反之则不成立。这已经提供了足够的信息，如果可以询问无限多次的话，我们可以这样做：

• 选取小素数$q$，枚举出若干个 $\Delta=k^2q$，因为可约不代表 $\Delta$ 不是二次剩余，所以需要多次询问，确定每个$p$模$q$下的二次剩余。
• 通过二次互反律，得知 $p$ 模这个小素数的二次剩余，根据这些素数的offset来查表得知secret模$q$的值。
• CRT解出secret。

但是这道题只有50次询问，平均每一次询问需要获取 $5$ bit 的信息。但因为判别式只在不可约的时候可以获取信息，而不可约的概率只有 $\frac{1}{3}$，所以是不够 $5$ bit 的。

在判别式寄了之后，剩下的方法只剩下用三次剩余了。好消息是，三次剩余并不是完全没有研究，至少三次互反律是存在的，这给了我们用三次互反律来CRT的可能。

三次剩余需要使用 $\mathbb{Z}(\omega)$ 的高斯整数环来构造。这个环也是唯一分解整环，如果素数 $p\equiv 2\pmod{3}$，那么它在 $\mathbb{Z}(\omega)$ 中也是不可约的。如果素数 $p\equiv 1\pmod{3}$，那么它可以分解为共轭的两个素数 $p=(a+b\omega)(a+b\omega^2)$。然后我们称一个素数是 primary 的如果 $a+b\omega$ 的 $b$ 是 $3$ 的倍数。然后 $N(a+b\omega)=a^2-ab+b^2$ 是模长且一定模 $3$ 余 $1$。跟二次剩余类似，三次剩余也可以定义

取值一定是三次单位根的一个。对任意两个 primary 的素数 $\alpha,\pi$，有三次互反律 $\left(\frac{\alpha}{\pi}\right)_3=\left(\frac{\pi}{\alpha}\right)_3$ 成立。

如果我们想要在三次方程中使用三次互反律，首先要处理的就是在开立方根之前的那个二次剩余。如果我们随意地选数，不同模 $p$ 的开根会乱成一团，所以我们要直接构造 $a,b$ 使开根的数是平方数。这也意味着判别式跟一个平方数只差一个 $-3$，无法给信息了。一个不错的选择是把根设置为 $x=\sqrt[3]{5}+\sqrt[3]{25}$的所有共轭。这样我们只需要研究 $5$ 的三次剩余，而且 $5$ 模 $3$ 余 $2$，所以它在 $\mathbb{Z}(\omega)$ 中也是素数。

看着十分美好，但实操却发现了很大的问题。因为 $p$ 模 $3$ 余 $2$ 时所有数都有立方根，所以我们需要再一开始赌有很多素数模 $3$ 余 $1$。而且就算对模 $3$ 余 $1$ 的素数分析，也会遇到它自己又不是 $\mathbb{Z}(\omega)$ 上的素数的问题。如果我们要对这个强行算类似 Jacobi 符号的东西，会直接永远是 $1$ 寄掉。

以上是我在比赛时的思路，一看不太行就就转头开始继续对判别式做概率分析然后一头撞死。

比赛结束后，作者也发了他的解法，其实没太看懂为什么，但第一步是在单位根域上找一个三次的子域，比如 $7$ 次单位根对应的就是 $x^3-21x-7=0$，然后转到我的做法是算 $7(-1+3\omega)$ 的三次剩余。这里就发现问题了，他实际在开根的时候保留了一个 $\sqrt{-3}$ 然后直接转换到了整环上。这样就算对模 $3$ 余 $1$ 的素数分析也能得到一个非平凡的 Jacobi 符号。然后就可以直接用三次互反律来做了。

随便写了一个脚本来验证这个思路的正确性，就不完整做了。

1
from sage.all import *
2

3
w = polygen(ZZ, 'w')
4
K = NumberField(w**2+w+1, 'w')
5
w = K.gen()
6

7
p = random_prime(2**8)
8
while p % 3 != 1:
9
    p = random_prime(2**8)
10
a = list(K(p).factor())[-1][0]
11

12
def is_primary(a):
13
    # stupid primary ideal check
14
    u, v = a.parts()
15
    v = ZZ(2*v)
16
    return v % 3 == 0
17

18
a = next(a for a in [a, a*w, a*w**2] if is_primary(a))
19
print(a, a.norm())
20
norm = ZZ(a.norm())
21
ret = {}
22

23
for i in range(norm):
24
    if i == 0:
25
        continue
26
    b = random_prime(2**20)
27
    while b % norm != i:
28
        b = random_prime(2**20)
29
    b = K(b)
30
    assert b.residue_symbol(K.ideal(a), 3) == a.residue_symbol(K.ideal(b), 3)
31
    ret[ZZ(b)%norm] = a.residue_symbol(K.ideal(b), 3)
32

33
print(ret)
34
while True:
35
    b = random_prime(2**40)
36
    b = K(b)
37
    print(b, ZZ(b)%norm, ret[ZZ(b)%norm], b.residue_symbol(K.ideal(a), 3), a.residue_symbol(K.ideal(b), 3))
38
    assert ret[ZZ(b)%norm] == b.residue_symbol(K.ideal(a), 3) and ret[ZZ(b)%norm] == a.residue_symbol(K.ideal(b), 3)