牛顿恒等式

牛顿恒等式Newton’s Identities - 知乎 (zhihu.com)

牛顿恒等式（Newton’s Identities）研究多项式方程值和系数之间的关系：

如果$x_1,x_2,…,x_n$是$n$次多项式方程的$n$个根，定义：

一元二次牛顿恒等式

对于一元二次多项式：

两个零点为$\alpha_1,\alpha_2$，定义：

对于$i\geq2$，定义$A=-\frac ba,B=\frac ca$，满足：

可以用韦达定理证明。

例如，计算$P(x)=x^2-2x+6$的两个根为$a,b$时的$a^{10}+b^{10}$：

递推求得：$P_{10}=7552$。

1
2
3
4
5
6
7
8
9
10
11
12
13
def Newton2(i, A, B):
    if i == 1:
        return A
    elif i == 2:
        return A * A - 2 * B
    P1 = A
    P2 = A * A - 2 * B
    for _ in range(i - 2):
        P = A * P2 - B * P1
        P1, P2 = P2, P
    return P

print(Newton2(10, 2, 6))

一元三次牛顿恒等式

对于一元三次多项式：

三个零点为$\alpha_1,\alpha_2,\alpha_3$，根据韦达定理有：

有定理：

例如，计算$P(x)=x^3-3x^2+6x-9$的三个根为$a,b,c$时的$a^{5}+b^{5}+c^5$：
递推求得：$P_{5}=108$。

一般化牛顿恒等式

对于一元$k$次多项式：

$k$个顶点为$\alpha_1,\alpha_2,\cdots,\alpha_k$，定义以下参数：

同理可推导：

对于$i\geq k$：

相同的，如果我们知道给定$k$个幂次和，就可以恢复以这些值对应的多项式的所有系数$a$。

相关题目

blurred memory

来自2023TPCTF：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from secret import flag

assert flag[:6] == 'TPCTF{' and flag[-1] == '}'
flag = flag[6:-1]

assert len(set(flag)) == len(flag)

xs = []
for i, c in enumerate(flag):
    xs += [ord(c)] * (i + 1)

p = 257
print('output =', [sum(pow(x, k, p) for x in xs) % p for k in range(1, len(xs) + 1)])

# output = [125, 31, 116, 106, 193, 7, 38, 194, 186, 33, 180, 189, 53, 126, 134, 237, 123, 65, 179, 196, 99, 74, 101, 153, 84, 74, 233, 5, 105, 32, 75, 168, 161, 2, 147, 18, 68, 68, 162, 21, 94, 194, 249, 179, 24, 60, 71, 12, 40, 198, 79, 92, 44, 72, 189, 236, 244, 151, 56, 93, 195, 121, 211, 26, 73, 240, 76, 70, 133, 186, 165, 48, 31, 39, 3, 219, 96, 14, 166, 139, 24, 206, 93, 250, 79, 246, 256, 199, 198, 131, 34, 192, 173, 35, 0, 171, 160, 151, 118, 24, 10, 100, 93, 19, 101, 15, 190, 74, 10, 117, 4, 41, 135, 45, 107, 155, 152, 95, 222, 214, 174, 139, 117, 211, 224, 120, 219, 250, 1, 110, 225, 196, 105, 96, 52, 231, 59, 70, 95, 56, 58, 248, 171, 16, 251, 165, 54, 4, 211, 60, 210, 158, 45, 96, 105, 116, 30, 239, 96, 37, 175, 254, 157, 26, 151, 141, 43, 110, 227, 199, 223, 135, 162, 112, 4, 45, 66, 228, 162, 238, 165, 158, 27, 18, 76, 36, 237, 107, 84, 57, 233, 96, 72, 6, 114, 44, 119, 174, 59, 82, 202, 26, 216, 35, 55, 159, 113, 98, 4, 74, 2, 128, 34, 180, 191, 8, 101, 169, 157, 120, 254, 158, 97, 227, 79, 151, 167, 64, 195, 42, 250, 207, 213, 238, 199, 111, 149, 18, 194, 240, 53, 130, 3, 188, 41, 100, 255, 158, 21, 189, 19, 214, 127]

题目的加密提供了非常多组式子的结果，总共有$253$组式子：

我们所学习的牛顿恒等式形式应该是幂次和形式，但是，如果我们把所有的系数拆开，也可以把等式写成这种形式：

这样就可以得到牛顿恒等式的幂次和形式，出现的重根还可以帮助我们转化每个解密出的flag的位置。

根据一般形式的牛顿恒等式，我们如果想逆回去得到多项式，首先可以根据迭代的$P$反向求得$e$：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *

output = [125, 31, 116, 106, 193, 7, 38, 194, 186, 33, 180, 189, 53, 126, 134, 237, 123, 65, 179, 196, 99, 74, 101, 153, 84, 74, 233, 5, 105, 32, 75, 168, 161, 2, 147, 18, 68, 68, 162, 21, 94, 194, 249, 179, 24, 60, 71, 12, 40, 198, 79, 92, 44, 72, 189, 236, 244, 151, 56, 93, 195, 121, 211, 26, 73, 240, 76, 70, 133, 186, 165, 48, 31, 39, 3, 219, 96, 14, 166, 139, 24, 206, 93, 250, 79, 246, 256, 199, 198, 131, 34, 192, 173, 35, 0, 171, 160, 151, 118, 24, 10, 100, 93, 19, 101, 15, 190, 74, 10, 117, 4, 41, 135, 45, 107, 155, 152, 95, 222, 214, 174, 139, 117, 211, 224, 120, 219, 250, 1, 110, 225, 196, 105, 96, 52, 231, 59, 70, 95, 56, 58, 248, 171, 16, 251, 165, 54, 4, 211, 60, 210, 158, 45, 96, 105, 116, 30, 239, 96, 37, 175, 254, 157, 26, 151, 141, 43, 110, 227, 199, 223, 135, 162, 112, 4, 45, 66, 228, 162, 238, 165, 158, 27, 18, 76, 36, 237, 107, 84, 57, 233, 96, 72, 6, 114, 44, 119, 174, 59, 82, 202, 26, 216, 35, 55, 159, 113, 98, 4, 74, 2, 128, 34, 180, 191, 8, 101, 169, 157, 120, 254, 158, 97, 227, 79, 151, 167, 64, 195, 42, 250, 207, 213, 238, 199, 111, 149, 18, 194, 240, 53, 130, 3, 188, 41, 100, 255, 158, 21, 189, 19, 214, 127]
p = 257
P = output

e = []

for i in range(253):
    temp = 0
    for j in range(i):
        temp += (-1)**j * e[j] * P[i-j-1]
        temp %= p
    temp = (P[i] - temp) % p
    ei = temp * inverse((-1)^i*(i+1), p) % p
    e.append(ei)

得到$e$之后，根据$e$的生成式子可以反向得到$a$：

这里为了计算方便，我们默认还原的式子为一个首一多项式，这样就可直接得到$a_k=1$，所有的计算$e$都直接和前面的负一计算即可。

1
2
3
a = [1]
for i in range(len(e)):
    a.append((-1)^(i+1) * e[i] % p)

得到所有的$a$就相当于得到了这个多项式，我们直接用sage求根根据重根次数即可依次还原flag，附上wp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from Crypto.Util.number import *

output = [125, 31, 116, 106, 193, 7, 38, 194, 186, 33, 180, 189, 53, 126, 134, 237, 123, 65, 179, 196, 99, 74, 101, 153, 84, 74, 233, 5, 105, 32, 75, 168, 161, 2, 147, 18, 68, 68, 162, 21, 94, 194, 249, 179, 24, 60, 71, 12, 40, 198, 79, 92, 44, 72, 189, 236, 244, 151, 56, 93, 195, 121, 211, 26, 73, 240, 76, 70, 133, 186, 165, 48, 31, 39, 3, 219, 96, 14, 166, 139, 24, 206, 93, 250, 79, 246, 256, 199, 198, 131, 34, 192, 173, 35, 0, 171, 160, 151, 118, 24, 10, 100, 93, 19, 101, 15, 190, 74, 10, 117, 4, 41, 135, 45, 107, 155, 152, 95, 222, 214, 174, 139, 117, 211, 224, 120, 219, 250, 1, 110, 225, 196, 105, 96, 52, 231, 59, 70, 95, 56, 58, 248, 171, 16, 251, 165, 54, 4, 211, 60, 210, 158, 45, 96, 105, 116, 30, 239, 96, 37, 175, 254, 157, 26, 151, 141, 43, 110, 227, 199, 223, 135, 162, 112, 4, 45, 66, 228, 162, 238, 165, 158, 27, 18, 76, 36, 237, 107, 84, 57, 233, 96, 72, 6, 114, 44, 119, 174, 59, 82, 202, 26, 216, 35, 55, 159, 113, 98, 4, 74, 2, 128, 34, 180, 191, 8, 101, 169, 157, 120, 254, 158, 97, 227, 79, 151, 167, 64, 195, 42, 250, 207, 213, 238, 199, 111, 149, 18, 194, 240, 53, 130, 3, 188, 41, 100, 255, 158, 21, 189, 19, 214, 127]
p = 257
P = output

e = []

for i in range(253):
    temp = 0
    for j in range(i):
        temp += (-1)**j * e[j] * P[i-j-1]
        temp %= p
    
    temp = (P[i] - temp) % p
    ei = temp * inverse((-1)^i*(i+1), p) % p
    e.append(ei)

a = [1]
for i in range(len(e)):
    a.append((-1)^(i+1) * e[i] % p)

PR.<x> = PolynomialRing(Zmod(p))
f = 0
for i in range(253):
    f += x^(253-i)*a[i]
f += a[-1]
res = f.roots()

print('TPCTF{'+''.join(chr(i[0])for i in res)+'}')