有限域上的多项式

Ruan Xingzhi -

　　本文先介绍要用到的数学工具，再讨论有限域 $GF(p^d)$，再讨论基于多项式的 RSA 加密。

群、环、域

　　抽象代数是研究密码学的有力工具。其中有三种代数系统群、环、域，是通过满足的性质来划分的。相关性质如下：

A1 加法封闭性：如果 $a$ 和 $b$ 属于$G$，则 $ a+b $ 也属于 $ G $
A2 加法结合律：对 $ G $ 中的任意元素 $ a,b,c $ ， $ a+(b+c) = (a+b)+c $
A3 加法单位元：G中存在一个元素 $ 0 $ ，使得对于 $ G $ 中的任意元素 $ a $ ，有 $ a+0=a $
A4 加法逆元：对于 $ G $ 中的任意元素 $ a $ ， $ G $ 中一定存在一个元素 $ a $ ，使得 $ a+(-a) = 0 $
A5 加法交换律：对于 $  G $ 中任意元素 $ a $ 和 $ b $ ，有 $ a+b = b+a $

M1 乘法封闭性：如果 $ a $ 和 $ b $ 属于 $ G $ ，则 $ ab $ 也属于 $ G $
M2 乘法结合律：对于  $ G $ 中任意元素 $ a,b,c $ ，有 $ a(bc) = (ab)c $
M3 乘法分配律：对于 $ G $ 中的任意元素 $ a,b,c $ ，有 $ a(b+c) = ab+ac  $
M4 乘法交换律：对于 $ G $ 中任意元素 $ a,b  $ ，有 $ ab = ba $
M5 乘法单位元：对于 $ G $ 中任意元素 $ a $ ，在 $ G $ 中存在一个元素 $ 1 $ ，使得 $ a1 = a $
M6 无零因子：对于  $ G $ 中的元素 $ a,b $ ，若 $ ab = 0 $ ，则必有 $ a=0 $ 或 $ b=0 $
M7 乘法逆元：如果 $ a \in G $ ，且 $ a \neq 0 $ ，则 $ G $ 中存在一个元素 $ a^{-1} $ ，使得 $ aa^{-1} = a^{-1}a = 1 $

　　上述性质中，

  • 满足 A1-A4 的，称为群 (group).
  • 满足 A1-A5 的，称为交换群 / 阿贝尔群 (commutative group, Abelian group).
  • 满足 A1-M3 的，称为环 (ring).
  • 满足 A1-M4 的，称为交换环 (commutative ring).
  • 满足 A1-M6 的，称为整环 (integral domain).
  • 满足 A1-M7 的，称为域 (field).

　　可见，群支持一种运算；环支持两种运算（乘法、加法）并拥有分配律；域支持加、减、乘、除。让我们来看几个例子：

  • $(\mathbb{Q}, +, *)$ 是一个域。每一个非零元都有乘法逆元。
  • $(\mathbb{Z}, +, *)$ 是一个环。其中仅仅 $1, -1$ 拥有乘法逆元，故它不是域。
  • $(\mathbb{Z}/n\mathbb{Z}, +, *)$ 是一个环。而且如果 $n$ 是质数，它还是个域。
  • $(\mathbb{F}_p, +, *)$ 是一个域（其中 $p$ 为质数）。
  • 系数取自 $\mathbb{Z}$ 的全体多项式，构成一个环。记为 $\mathbb{Z}[x]$, 即$$\mathbb{Z}[x] = \{a_0 + a_1 x + a_2 x^2 +\cdots +a_nx ^ n ~ : ~ n\geq 0 ~\text{and} ~ a_0 , a _ 1, \dots, a_n \in \mathbb{Z}\}$$
  • 推而广之，如果 $R$ 是个环，则系数取自 $R$ 的多项式也是一个环。例如 $ R = \mathbb{Z}/q\mathbb{Z}$ 或  $\mathbb{F}_p$.

除法和商环

　　我们详细地研究过 $\mathbb{Z}$ 这个环，现在我们把它上面的整除、取模那一套理论推广到任意环 $R$：

[定义：整除] 若 $a,b \in R$ 且 $b\neq 0$. 则称 “$b$ 整除 $a$” 当且仅当存在 $c\in R$, 使得$$a = b\cdot c$$记为 $b \mid a$. 如果 $b$ 不能整除 $a$，则记为 $b\nmid a$.

　　显然，对任何 $b\neq 0$ 恒有 $b \mid 0$. 但不是所有环都有 “若 $a,b\neq 0$, 则 $ab\neq 0$”这条性质。例如，环 $\mathbb{Z}/6\mathbb{Z}$ 上，$2,3$ 均非零，但是 $2\cdot 3 = 0$. 只有整环才拥有这条性质。

　　在整数域上，任何数 $n$ 都有平凡因子 $1, -1, n, -n$. 为什么 $1$ 和 $-1$ 是所有数的因子呢？不难注意到，若 $a$ 有逆元，则 $a$ 是环上每一个数的平凡因子，因为任何数 $n$ 都可以写成 $n = a \cdot (a ^ {-1} n)$, 从而 $a \mid n$. 拥有逆元的数是其他所有数的因子；有些数可能仅拥有平凡因子。给它们分别起个名字。

[定义：单元] 设 $R$ 为环。$u \in R$ 被称为“单元(unit)”，当且仅当它拥有乘法逆元。
[定义：不可约] 设 $R$ 为环。称 $a \in R$ 是“不可约(irreducible)”的，当且仅当 $a$ 本身不是 unit，且对于 $a$ 的每个分解 $a=b\cdot c$，要么 $b$ 是 unit，要么 $c$ 是 unit.

　　现在所有的环上都有了 “质数” 和 “平凡因子” 的概念，于是可以考虑取模。整数域上的模意义也可以推广：

[定义：恒等] 设 $R$ 为环，$m \in R$ 不为$0$. 我们称“ $a, b$在模 $m$ 意义下全等($a, b$ are congruent modulo m)”，当且仅当 $a-b$ 可以被 $m$ 整除。记为$$a \equiv b \pmod m$$

　　显然，模 $m$ 的每一个等价类，在加法、乘法上表现出相同的性质：$$a_1\equiv a_2, b_1\equiv b_2\quad \Rightarrow \quad a_1\pm b_1 \equiv a_2\pm b_2, a_1\cdot b_1 \equiv a_2 \cdot b_2 \pmod m$$

　　正如一个集合可以被等价关系划分为几个等价类，一个环当然也能被全等关系划分为几个等价类，它们形成新的环。我们把造出来的这个环称为商环。

[定义：商环] 设 $R$ 为环，$m \in R$ 不为$0$. 对任意 $a\in R$, 记 $\overline a$ 为全体满足 $a'\equiv a \pmod m$ 的 $a'$ 的集合。$\overline a$ 称为 $a$ 的等价类。记全体等价类构成的集合为 $R/(m)$ 或者 $R/mR$. 即$$R/(m) = R/mR = \{\overline a ~ : ~ a\in R\}$$显然有 $$\overline a + \overline  b = \overline {a+b},\quad \overline a \cdot \overline  b = \overline {ab}$$
我们将 $R/(m)$ 称为 $R$ 除以 $m$ 的商环(quotient ring). 不难证明 $R/mR$ 仍然具有环的性质。

多项式环

　　如果 $R$ 是一个环，那么系数取自 $R$ 的全体多项式也会构成一个环。记为$$R[x] = \{a_0 + a_1 x + a_2 x^2 +\cdots +a_nx ^ n ~ : ~ n\geq 0 ~\text{and} ~ a_0 , a _ 1, \dots, a_n \in R\}$$

　　对于一个多项式$A(x)$，我们把最高项的次数作为这个多项式的度数(degree). 记为 $\deg(A)$.

　　回顾除法和取模运算：余数一定是严格小于除数的，而且一个数除以另一个数，会得到唯一的商和余数。我们把拥有 “带余除法” 操作的环称为“欧几里得整环(Euclidean domain)”. 则有：

[环 $\mathbb{F}[x]$ 是欧几里得整环] 设 $\mathbb{F}$ 是域，设 $A, B\in \mathbb{F}[x], B\neq 0$. 那么有$$A = B\cdot K + R$$其中 $K, R$ 是多项式，且要么 $R=0$, 要么 $\deg R < \deg B$. 我们称 $A$ 除以 $B$ 得到商 $K$ 和余数 $R$.

　　既然有了带余除法，那么最大公约数(greatest common divisors)的概念显然也可以套用在$\mathbb{F}[x]$上。

[定义：最大公约数] 设 $a,b\in \mathbb{F}[x]$，若 $d$ 可以整除 $a,b$ ，且 $a,b$ 的所有公因子都整除 $d$，则称 $d$ 为 $a, b$ 的最大公约数。将最高项系数为 1 的这种最大公约数记为 $\gcd(a, b)$. 不难证明其唯一性。

　　举个例子：$\gcd(x^2-1, x^3+1)=x+1$. 并不是所有环上的任意两个数都拥有gcd，例如环 $\mathbb{Z}[x]$ 上的两个多项式就可能不存在gcd. 但如果 $\mathbb{F}$ 是一个域，则 $\mathbb{F}[x]$ 内两个多项式的 gcd 必存在。

[ $\mathbb{F}[x]$ 上的扩展欧几里得算法] 设 $\mathbb{F}$ 是域，$a, b\in \mathbb{F}, b\neq 0$. 则 $a,b$ 的最大公约数 $d$ 存在，且 $\mathbb{F}[x]$ 内存在 $u, v$ 使得 $$a\cdot u + b\cdot v = d$$

　　举个例子：域 $GF(13)$ 内，$\gcd(x^5 -1, x^3+2x-3) = 9x+4 = x-1 = x+12$.

R.<x> = PolynomialRing(GF(13))
xgcd(x^5-1, x^3+2*x-3)

# (x + 12, 12*x + 10, x^3 + 3*x^2 + 11*x + 10)
多项式的 exgcd 算法

　　类似于 $\mathbb{Z}$ 上的唯一分解定理，若$\mathbb{F}$是一个域，则 $\mathbb{F}[x]$ 内的非零多项式的分解也是唯一的。这里的“唯一”指“可以唯一表示成首项为1的若干个多项式之积”。

多项式的商环

　　之前说过，环可以用全等关系生成商环。多项式环显然也是可以的。我们有下面的定理：

[定理] 设 $\mathbb{F}$ 是域，$m\in \mathbb{F}[x]$非零。则每一个 $\overline a \in F[x]/(m)$ 都拥有一个唯一的代表元，满足 $$\deg r < \deg m, \quad a\equiv r\pmod m$$
若 $\mathbb{F}_p$ 是有限域，设 $m \in \mathbb{F}_p[x]$ 是非零多项式，度数 $d \geq 1$. 则商环 $\mathbb{F}_p[x]/(m)$ 恰包含 $p^d$ 个元素。

　　按照乘法原理，这个是很显然的。现在来考察 $\mathbb{F}_p$ 里面的 unit. 有如下定理：

[定理] 设 $\mathbb{F}$ 是域，$a, m\in \mathbb{F}[x], m\neq 0$. 则 $\overline a$ 是商环 $\mathbb{F}[x]/(m)$ 内的unit, 当且仅当$$\gcd(a, m)  = 1$$

　　于是我们发现，多项式的逆元存在条件与整数域上的可逆条件非常相似。类似于 $GF(p)$ 内的每个非零元素都有乘法逆元，我们也有：

[定理] 设 $\mathbb{F}$ 是域，$m\in \mathbb{F}[x], m\neq 0$是不可约的。则商环 $\mathbb{F}[x] / (m)$ 是一个域，每个非零元都有乘法逆元。
若 $\mathbb{F}_p$ 为有限域，设 $m\in \mathbb{F}_p[x]$ 不可约，度数 $d \geq 1$. 则 $\mathbb{F}_p[x] / (m)$ 是一个恰有 $p^d$ 个元素的域。

　　现在，来考察有限域上的几个性质：

设 $\mathbb{F}_p$ 是有限域。
- 对于每一个 $d\geq 1$，存在一个度数为 $d$ 的不可约多项式 $m\in\mathbb{F}_p[x]$.
- 对于每一个 $d\geq 1$，存在一个恰有 $p^d$ 个元素的有限域。
- 若有限域 $\mathbb{F}$ 和 $\mathbb{F}'$ 元素数量相同，则 $\mathbb{F}$ 与 $\mathbb{F}'$ 同构！

　　最后这条性质指明了大小相同的各种有限域的本质等价性。既然凡是拥有 $p^d$ 个元素的有限域都同构，那我们只需要选择其中的任何一个进行研究，就可以得到所有这类有限域的性质。

　　上面所述的域包含了全体有限域。因为任何一个有限域，大小必定是某个质数的某次幂。于是所有的有限域，要么与 $F(p)$ 同构，可以通过研究整数运算来研究这些域；要么同构于 $GF(p^d)$, 可以通过研究多项式来研究这些域。

　　最后给出有限域的“费马小定理”和“原根”：

[定理] 设 $\mathbb{F}$ 是有限域，有 $q$ 个元素。那么由于每个 $\mathbb{F}$ 内的非零元都有乘法逆元，则由 $\mathbb{F}$ 内的 unit 构成的群 $\mathbb{F}^*$ 的阶是 $q-1$. 由拉格朗日定理，有限群内元素的阶可以整除群的阶，于是对于 $\mathbb{F}$ 内的所有 $a$ 都有$$a^{q-1} = 1$$
存在一个 $g \in \mathbb{F}$ 是 $\mathbb{F}$ 的原根，即$$\mathbb{F}^ * = \{1, g, g^2, g ^ 3, \dots, g ^ {q-2}\}$$

　　终于把所需要的数学工具说完了……来看一道题吧。

BUUCTF: [watevrCTF 2019]Swedish RSA

【附件】

　　给出了生成器：

flag = bytearray(raw_input())
flag = list(flag)
length = len(flag)
bits = 16

## Prime for Finite Field.
p = random_prime(2^bits-1, False, 2^(bits-1))

file_out = open("downloads/polynomial_rsa.txt", "w")
file_out.write("Prime: " + str(p) + "\n")

## Univariate Polynomial Ring in y over Finite Field of size p
R.<y> = PolynomialRing(GF(p))

## Analogous to the primes in Z
def gen_irreducable_poly(deg):
    while True:
        out = R.random_element(degree=deg)
        if out.is_irreducible():
            return out


## Polynomial "primes"
P = gen_irreducable_poly(ZZ.random_element(length, 2*length))
Q = gen_irreducable_poly(ZZ.random_element(length, 2*length))

## Public exponent key
e = 65537

## Modulus
N = P*Q
file_out.write("Modulus: " + str(N) + "\n")

## Univariate Quotient Polynomial Ring in x over Finite Field of size 659 with modulus N(x)
S.<x> = R.quotient(N)

## Encrypt
m = S(flag)
c = m^e

file_out.write("Ciphertext: " + str(c))
file_out.close()

　　然后给出了很壮观的 $p, N, c$：

Prime: 43753
Modulus: 34036*y^177 + 23068*y^176 + 13147*y^175 + 36344*y^174 + 10045*y^173 + 41049*y^172 + 17786*y^171 + 16601*y^170 + 7929*y^169 + 37570*y^168 + 990*y^167 + 9622*y^166 + 39273*y^165 + 35284*y^164 + 15632*y^163 + 18850*y^162 + 8800*y^161 + 33148*y^160 + 12147*y^159 + 40487*y^158 + 6407*y^157 + 34111*y^156 + 8446*y^155 + 21908*y^154 + 16812*y^153 + 40624*y^152 + 43506*y^151 + 39116*y^150 + 33011*y^149 + 23914*y^148 + 2210*y^147 + 23196*y^146 + 43359*y^145 + 34455*y^144 + 17684*y^143 + 25262*y^142 + 982*y^141 + 24015*y^140 + 27968*y^139 + 37463*y^138 + 10667*y^137 + 39519*y^136 + 31176*y^135 + 27520*y^134 + 32118*y^133 + 8333*y^132 + 38945*y^131 + 34713*y^130 + 1107*y^129 + 43604*y^128 + 4433*y^127 + 18110*y^126 + 17658*y^125 + 32354*y^124 + 3219*y^123 + 40238*y^122 + 10439*y^121 + 3669*y^120 + 8713*y^119 + 21027*y^118 + 29480*y^117 + 5477*y^116 + 24332*y^115 + 43480*y^114 + 33406*y^113 + 43121*y^112 + 1114*y^111 + 17198*y^110 + 22829*y^109 + 24424*y^108 + 16523*y^107 + 20424*y^106 + 36206*y^105 + 41849*y^104 + 3584*y^103 + 26500*y^102 + 31897*y^101 + 34640*y^100 + 27449*y^99 + 30962*y^98 + 41434*y^97 + 22125*y^96 + 24314*y^95 + 3944*y^94 + 18400*y^93 + 38476*y^92 + 28904*y^91 + 27936*y^90 + 41867*y^89 + 25573*y^88 + 25659*y^87 + 33443*y^86 + 18435*y^85 + 5934*y^84 + 38030*y^83 + 17563*y^82 + 24086*y^81 + 36782*y^80 + 20922*y^79 + 38933*y^78 + 23448*y^77 + 10599*y^76 + 7156*y^75 + 29044*y^74 + 23605*y^73 + 7657*y^72 + 28200*y^71 + 2431*y^70 + 3860*y^69 + 23259*y^68 + 14590*y^67 + 33631*y^66 + 15673*y^65 + 36049*y^64 + 29728*y^63 + 22413*y^62 + 18602*y^61 + 18557*y^60 + 23505*y^59 + 17642*y^58 + 12595*y^57 + 17255*y^56 + 15316*y^55 + 8948*y^54 + 38*y^53 + 40329*y^52 + 9823*y^51 + 5798*y^50 + 6379*y^49 + 8662*y^48 + 34640*y^47 + 38321*y^46 + 18760*y^45 + 13135*y^44 + 15926*y^43 + 34952*y^42 + 28940*y^41 + 13558*y^40 + 42579*y^39 + 38015*y^38 + 33788*y^37 + 12381*y^36 + 195*y^35 + 13709*y^34 + 31500*y^33 + 32994*y^32 + 30486*y^31 + 40414*y^30 + 2578*y^29 + 30525*y^28 + 43067*y^27 + 6195*y^26 + 36288*y^25 + 23236*y^24 + 21493*y^23 + 15808*y^22 + 34500*y^21 + 6390*y^20 + 42994*y^19 + 42151*y^18 + 19248*y^17 + 19291*y^16 + 8124*y^15 + 40161*y^14 + 24726*y^13 + 31874*y^12 + 30272*y^11 + 30761*y^10 + 2296*y^9 + 11017*y^8 + 16559*y^7 + 28949*y^6 + 40499*y^5 + 22377*y^4 + 33628*y^3 + 30598*y^2 + 4386*y + 23814
Ciphertext: 5209*x^176 + 10881*x^175 + 31096*x^174 + 23354*x^173 + 28337*x^172 + 15982*x^171 + 13515*x^170 + 21641*x^169 + 10254*x^168 + 34588*x^167 + 27434*x^166 + 29552*x^165 + 7105*x^164 + 22604*x^163 + 41253*x^162 + 42675*x^161 + 21153*x^160 + 32838*x^159 + 34391*x^158 + 832*x^157 + 720*x^156 + 22883*x^155 + 19236*x^154 + 33772*x^153 + 5020*x^152 + 17943*x^151 + 26967*x^150 + 30847*x^149 + 10306*x^148 + 33966*x^147 + 43255*x^146 + 20342*x^145 + 4474*x^144 + 3490*x^143 + 38033*x^142 + 11224*x^141 + 30565*x^140 + 31967*x^139 + 32382*x^138 + 9759*x^137 + 1030*x^136 + 32122*x^135 + 42614*x^134 + 14280*x^133 + 16533*x^132 + 32676*x^131 + 43070*x^130 + 36009*x^129 + 28497*x^128 + 2940*x^127 + 9747*x^126 + 22758*x^125 + 16615*x^124 + 14086*x^123 + 13038*x^122 + 39603*x^121 + 36260*x^120 + 32502*x^119 + 17619*x^118 + 17700*x^117 + 15083*x^116 + 11311*x^115 + 36496*x^114 + 1300*x^113 + 13601*x^112 + 43425*x^111 + 10376*x^110 + 11551*x^109 + 13684*x^108 + 14955*x^107 + 6661*x^106 + 12674*x^105 + 21534*x^104 + 32132*x^103 + 34135*x^102 + 43684*x^101 + 837*x^100 + 29311*x^99 + 4849*x^98 + 26632*x^97 + 26662*x^96 + 10159*x^95 + 32657*x^94 + 12149*x^93 + 17858*x^92 + 35805*x^91 + 19391*x^90 + 30884*x^89 + 42039*x^88 + 17292*x^87 + 4694*x^86 + 1497*x^85 + 1744*x^84 + 31071*x^83 + 26246*x^82 + 24402*x^81 + 22068*x^80 + 39263*x^79 + 23703*x^78 + 21484*x^77 + 12241*x^76 + 28821*x^75 + 32886*x^74 + 43075*x^73 + 35741*x^72 + 19936*x^71 + 37219*x^70 + 33411*x^69 + 8301*x^68 + 12949*x^67 + 28611*x^66 + 42654*x^65 + 6910*x^64 + 18523*x^63 + 31144*x^62 + 21398*x^61 + 36298*x^60 + 27158*x^59 + 918*x^58 + 38601*x^57 + 4269*x^56 + 5699*x^55 + 36444*x^54 + 34791*x^53 + 37978*x^52 + 32481*x^51 + 8039*x^50 + 11012*x^49 + 11454*x^48 + 30450*x^47 + 1381*x^46 + 32403*x^45 + 8202*x^44 + 8404*x^43 + 37648*x^42 + 43696*x^41 + 34237*x^40 + 36490*x^39 + 41423*x^38 + 35792*x^37 + 36950*x^36 + 31086*x^35 + 38970*x^34 + 12439*x^33 + 7963*x^32 + 16150*x^31 + 11382*x^30 + 3038*x^29 + 20157*x^28 + 23531*x^27 + 32866*x^26 + 5428*x^25 + 21132*x^24 + 13443*x^23 + 28909*x^22 + 42716*x^21 + 6567*x^20 + 24744*x^19 + 8727*x^18 + 14895*x^17 + 28172*x^16 + 30903*x^15 + 26608*x^14 + 27314*x^13 + 42224*x^12 + 42551*x^11 + 37726*x^10 + 11203*x^9 + 36816*x^8 + 5537*x^7 + 20301*x^6 + 17591*x^5 + 41279*x^4 + 7999*x^3 + 33753*x^2 + 34551*x + 9659

　　来看生成器。大概意思就是：造两个 $GF(p)$ 内的不可约多项式 $P, Q$, 它们的度数比 flag 的长度更高。然后取多项式 $N = P\cdot Q$, 得到商集 $S = R / (N)$. 生成一个多项式 $m$，系数为 $flag$ 的各个字节，然后在 $S$ 内求出 $m^e$ 作为密文。

　　由于 $N$ 是两个不可约多项式的积，所以 $m$ 几乎肯定是个unit，这个加密应该是可逆的。那么如何从 $c$ 算出 $m$，也就是 flag 呢？这里 $N$ 的次数只有177，因此可以分解出 $P, Q$：

R.<y> = PolynomialRing(GF(p))
N = 34036*y^177 + 23068*y^176 + 13147*y^175 + 36344*y^174 + 10045*y^173 + 41049*y^172 + 17786*y^171 + 16601*y^170 + 7929*y^169 + 37570*y^168 + 990*y^167 + 9622*y^166 + 39273*y^165 + 35284*y^164 + 15632*y^163 + 18850*y^162 + 8800*y^161 + 33148*y^160 + 12147*y^159 + 40487*y^158 + 6407*y^157 + 34111*y^156 + 8446*y^155 + 21908*y^154 + 16812*y^153 + 40624*y^152 + 43506*y^151 + 39116*y^150 + 33011*y^149 + 23914*y^148 + 2210*y^147 + 23196*y^146 + 43359*y^145 + 34455*y^144 + 17684*y^143 + 25262*y^142 + 982*y^141 + 24015*y^140 + 27968*y^139 + 37463*y^138 + 10667*y^137 + 39519*y^136 + 31176*y^135 + 27520*y^134 + 32118*y^133 + 8333*y^132 + 38945*y^131 + 34713*y^130 + 1107*y^129 + 43604*y^128 + 4433*y^127 + 18110*y^126 + 17658*y^125 + 32354*y^124 + 3219*y^123 + 40238*y^122 + 10439*y^121 + 3669*y^120 + 8713*y^119 + 21027*y^118 + 29480*y^117 + 5477*y^116 + 24332*y^115 + 43480*y^114 + 33406*y^113 + 43121*y^112 + 1114*y^111 + 17198*y^110 + 22829*y^109 + 24424*y^108 + 16523*y^107 + 20424*y^106 + 36206*y^105 + 41849*y^104 + 3584*y^103 + 26500*y^102 + 31897*y^101 + 34640*y^100 + 27449*y^99 + 30962*y^98 + 41434*y^97 + 22125*y^96 + 24314*y^95 + 3944*y^94 + 18400*y^93 + 38476*y^92 + 28904*y^91 + 27936*y^90 + 41867*y^89 + 25573*y^88 + 25659*y^87 + 33443*y^86 + 18435*y^85 + 5934*y^84 + 38030*y^83 + 17563*y^82 + 24086*y^81 + 36782*y^80 + 20922*y^79 + 38933*y^78 + 23448*y^77 + 10599*y^76 + 7156*y^75 + 29044*y^74 + 23605*y^73 + 7657*y^72 + 28200*y^71 + 2431*y^70 + 3860*y^69 + 23259*y^68 + 14590*y^67 + 33631*y^66 + 15673*y^65 + 36049*y^64 + 29728*y^63 + 22413*y^62 + 18602*y^61 + 18557*y^60 + 23505*y^59 + 17642*y^58 + 12595*y^57 + 17255*y^56 + 15316*y^55 + 8948*y^54 + 38*y^53 + 40329*y^52 + 9823*y^51 + 5798*y^50 + 6379*y^49 + 8662*y^48 + 34640*y^47 + 38321*y^46 + 18760*y^45 + 13135*y^44 + 15926*y^43 + 34952*y^42 + 28940*y^41 + 13558*y^40 + 42579*y^39 + 38015*y^38 + 33788*y^37 + 12381*y^36 + 195*y^35 + 13709*y^34 + 31500*y^33 + 32994*y^32 + 30486*y^31 + 40414*y^30 + 2578*y^29 + 30525*y^28 + 43067*y^27 + 6195*y^26 + 36288*y^25 + 23236*y^24 + 21493*y^23 + 15808*y^22 + 34500*y^21 + 6390*y^20 + 42994*y^19 + 42151*y^18 + 19248*y^17 + 19291*y^16 + 8124*y^15 + 40161*y^14 + 24726*y^13 + 31874*y^12 + 30272*y^11 + 30761*y^10 + 2296*y^9 + 11017*y^8 + 16559*y^7 + 28949*y^6 + 40499*y^5 + 22377*y^4 + 33628*y^3 + 30598*y^2 + 4386*y + 23814
factor(N)
# (34036) * (y^65 + 39688*y^64 + 22199*y^63 + 41942*y^62 + 7803*y^61 + 19710*y^60 + 14794*y^59 + 41388*y^58 + 2418*y^57 + 19208*y^56 + 39941*y^55 + 36392*y^54 + 19813*y^53 + 33864*y^52 + 29099*y^51 + 15484*y^50 + 27185*y^49 + 27721*y^48 + 31508*y^47 + 19404*y^46 + 10134*y^45 + 43481*y^44 + 3899*y^43 + 32849*y^42 + 3534*y^41 + 32086*y^40 + 14221*y^39 + 42982*y^38 + 1403*y^37 + 1619*y^36 + 36054*y^35 + 33615*y^34 + 6628*y^33 + 31709*y^32 + 6968*y^31 + 28517*y^30 + 12938*y^29 + 21124*y^28 + 10400*y^27 + 28889*y^26 + 7273*y^25 + 36442*y^24 + 14935*y^23 + 29365*y^22 + 4869*y^21 + 43562*y^20 + 6435*y^19 + 4403*y^18 + 32311*y^17 + 7575*y^16 + 28199*y^15 + 28065*y^14 + 23870*y^13 + 37314*y^12 + 15299*y^11 + 7082*y^10 + 36230*y^9 + 18367*y^8 + 12531*y^7 + 25906*y^6 + 26878*y^5 + 43073*y^4 + 11582*y^3 + 4482*y^2 + 35044*y + 31388) * (y^112 + 31097*y^111 + 15815*y^110 + 17170*y^109 + 43684*y^108 + 16873*y^107 + 17269*y^106 + 10853*y^105 + 10690*y^104 + 24864*y^103 + 10224*y^102 + 28704*y^101 + 16049*y^100 + 1154*y^99 + 40034*y^98 + 29922*y^97 + 27404*y^96 + 32514*y^95 + 40962*y^94 + 32858*y^93 + 36590*y^92 + 41302*y^91 + 20803*y^90 + 43521*y^89 + 13746*y^88 + 19857*y^87 + 21539*y^86 + 36888*y^85 + 16032*y^84 + 35825*y^83 + 24705*y^82 + 31143*y^81 + 22088*y^80 + 6686*y^79 + 37947*y^78 + 5661*y^77 + 29405*y^76 + 36071*y^75 + 35492*y^74 + 28985*y^73 + 36015*y^72 + 24095*y^71 + 34920*y^70 + 6615*y^69 + 9606*y^68 + 4255*y^67 + 22981*y^66 + 3910*y^65 + 23897*y^64 + 22711*y^63 + 23350*y^62 + 7969*y^61 + 8558*y^60 + 8001*y^59 + 8431*y^58 + 3314*y^57 + 23364*y^56 + 39391*y^55 + 32722*y^54 + 2543*y^53 + 22196*y^52 + 24189*y^51 + 19420*y^50 + 10649*y^49 + 19070*y^48 + 23863*y^47 + 19597*y^46 + 39699*y^45 + 7620*y^44 + 25067*y^43 + 29912*y^42 + 14998*y^41 + 14492*y^40 + 31322*y^39 + 43145*y^38 + 32006*y^37 + 38976*y^36 + 32534*y^35 + 6972*y^34 + 37351*y^33 + 30104*y^32 + 6032*y^31 + 33729*y^30 + 27110*y^29 + 5268*y^28 + 2974*y^27 + 2985*y^26 + 31610*y^25 + 28364*y^24 + 34924*y^23 + 17414*y^22 + 28813*y^21 + 43680*y^20 + 32175*y^19 + 18248*y^18 + 25171*y^17 + 31185*y^16 + 30125*y^15 + 36836*y^14 + 7218*y^13 + 11292*y^12 + 31123*y^11 + 40360*y^10 + 34093*y^9 + 39606*y^8 + 2788*y^7 + 27277*y^6 + 21835*y^5 + 1331*y^4 + 32614*y^3 + 25020*y^2 + 20981*y + 12108)

P = (34036) * (y^65 + 39688*y^64 + 22199*y^63 + 41942*y^62 + 7803*y^61 + 19710*y^60 + 14794*y^59 + 41388*y^58 + 2418*y^57 + 19208*y^56 + 39941*y^55 + 36392*y^54 + 19813*y^53 + 33864*y^52 + 29099*y^51 + 15484*y^50 + 27185*y^49 + 27721*y^48 + 31508*y^47 + 19404*y^46 + 10134*y^45 + 43481*y^44 + 3899*y^43 + 32849*y^42 + 3534*y^41 + 32086*y^40 + 14221*y^39 + 42982*y^38 + 1403*y^37 + 1619*y^36 + 36054*y^35 + 33615*y^34 + 6628*y^33 + 31709*y^32 + 6968*y^31 + 28517*y^30 + 12938*y^29 + 21124*y^28 + 10400*y^27 + 28889*y^26 + 7273*y^25 + 36442*y^24 + 14935*y^23 + 29365*y^22 + 4869*y^21 + 43562*y^20 + 6435*y^19 + 4403*y^18 + 32311*y^17 + 7575*y^16 + 28199*y^15 + 28065*y^14 + 23870*y^13 + 37314*y^12 + 15299*y^11 + 7082*y^10 + 36230*y^9 + 18367*y^8 + 12531*y^7 + 25906*y^6 + 26878*y^5 + 43073*y^4 + 11582*y^3 + 4482*y^2 + 35044*y + 31388)
Q = (y^112 + 31097*y^111 + 15815*y^110 + 17170*y^109 + 43684*y^108 + 16873*y^107 + 17269*y^106 + 10853*y^105 + 10690*y^104 + 24864*y^103 + 10224*y^102 + 28704*y^101 + 16049*y^100 + 1154*y^99 + 40034*y^98 + 29922*y^97 + 27404*y^96 + 32514*y^95 + 40962*y^94 + 32858*y^93 + 36590*y^92 + 41302*y^91 + 20803*y^90 + 43521*y^89 + 13746*y^88 + 19857*y^87 + 21539*y^86 + 36888*y^85 + 16032*y^84 + 35825*y^83 + 24705*y^82 + 31143*y^81 + 22088*y^80 + 6686*y^79 + 37947*y^78 + 5661*y^77 + 29405*y^76 + 36071*y^75 + 35492*y^74 + 28985*y^73 + 36015*y^72 + 24095*y^71 + 34920*y^70 + 6615*y^69 + 9606*y^68 + 4255*y^67 + 22981*y^66 + 3910*y^65 + 23897*y^64 + 22711*y^63 + 23350*y^62 + 7969*y^61 + 8558*y^60 + 8001*y^59 + 8431*y^58 + 3314*y^57 + 23364*y^56 + 39391*y^55 + 32722*y^54 + 2543*y^53 + 22196*y^52 + 24189*y^51 + 19420*y^50 + 10649*y^49 + 19070*y^48 + 23863*y^47 + 19597*y^46 + 39699*y^45 + 7620*y^44 + 25067*y^43 + 29912*y^42 + 14998*y^41 + 14492*y^40 + 31322*y^39 + 43145*y^38 + 32006*y^37 + 38976*y^36 + 32534*y^35 + 6972*y^34 + 37351*y^33 + 30104*y^32 + 6032*y^31 + 33729*y^30 + 27110*y^29 + 5268*y^28 + 2974*y^27 + 2985*y^26 + 31610*y^25 + 28364*y^24 + 34924*y^23 + 17414*y^22 + 28813*y^21 + 43680*y^20 + 32175*y^19 + 18248*y^18 + 25171*y^17 + 31185*y^16 + 30125*y^15 + 36836*y^14 + 7218*y^13 + 11292*y^12 + 31123*y^11 + 40360*y^10 + 34093*y^9 + 39606*y^8 + 2788*y^7 + 27277*y^6 + 21835*y^5 + 1331*y^4 + 32614*y^3 + 25020*y^2 + 20981*y + 12108)

assert P*Q == N

　　现在 $P,Q$ 到手。常规的攻击RSA，分解出 $p, q$ 是为了获取 $\varphi(pq)$；那么多项式下有没有类似的 “欧拉函数” 呢？我们想找到这样的 $k$，满足：$$m ^ {k} = 1$$如果有这样的 $k$，那么$$c ^ {\text{inv}(e, k)} = m ^ {e \cdot \text{inv}(e, k)} = m ^ 1$$就可以直接解密了。所以当务之急很明确：找到使得 $m ^ {k} = 1$ 成立的整数 $k = \varphi(N)$.

　　欧拉函数的定义：$\varphi(n)$ 表示“小于 $n$ 的数里面与 $n$ 互质的数的个数”。我们直接往多项式上套用欧拉函数的定义。显然度数小于 $\deg P$ 的多项式都与 $P$ 互质，从而$\varphi(P) = p^{\deg P }-1$. 这个减掉的 1 是因为 $0$ 与 $P$ 不互质。猜想一下，可能有$\varphi(PQ) = \varphi(P)\cdot \varphi(Q)$. 验证如下：

S.<x> = R.quotient(N)

phi = (p^P.degree() - 1) * (p^Q.degree() - 1)
assert 1 == S([1,2,3,4,5,6,7,8,9,10]) ^ phi

　　多项式的欧拉函数居然真的满足积性。于是问题迎刃而解：

c = 5209*x^176 + 10881*x^175 + 31096*x^174 + 23354*x^173 + 28337*x^172 + 15982*x^171 + 13515*x^170 + 21641*x^169 + 10254*x^168 + 34588*x^167 + 27434*x^166 + 29552*x^165 + 7105*x^164 + 22604*x^163 + 41253*x^162 + 42675*x^161 + 21153*x^160 + 32838*x^159 + 34391*x^158 + 832*x^157 + 720*x^156 + 22883*x^155 + 19236*x^154 + 33772*x^153 + 5020*x^152 + 17943*x^151 + 26967*x^150 + 30847*x^149 + 10306*x^148 + 33966*x^147 + 43255*x^146 + 20342*x^145 + 4474*x^144 + 3490*x^143 + 38033*x^142 + 11224*x^141 + 30565*x^140 + 31967*x^139 + 32382*x^138 + 9759*x^137 + 1030*x^136 + 32122*x^135 + 42614*x^134 + 14280*x^133 + 16533*x^132 + 32676*x^131 + 43070*x^130 + 36009*x^129 + 28497*x^128 + 2940*x^127 + 9747*x^126 + 22758*x^125 + 16615*x^124 + 14086*x^123 + 13038*x^122 + 39603*x^121 + 36260*x^120 + 32502*x^119 + 17619*x^118 + 17700*x^117 + 15083*x^116 + 11311*x^115 + 36496*x^114 + 1300*x^113 + 13601*x^112 + 43425*x^111 + 10376*x^110 + 11551*x^109 + 13684*x^108 + 14955*x^107 + 6661*x^106 + 12674*x^105 + 21534*x^104 + 32132*x^103 + 34135*x^102 + 43684*x^101 + 837*x^100 + 29311*x^99 + 4849*x^98 + 26632*x^97 + 26662*x^96 + 10159*x^95 + 32657*x^94 + 12149*x^93 + 17858*x^92 + 35805*x^91 + 19391*x^90 + 30884*x^89 + 42039*x^88 + 17292*x^87 + 4694*x^86 + 1497*x^85 + 1744*x^84 + 31071*x^83 + 26246*x^82 + 24402*x^81 + 22068*x^80 + 39263*x^79 + 23703*x^78 + 21484*x^77 + 12241*x^76 + 28821*x^75 + 32886*x^74 + 43075*x^73 + 35741*x^72 + 19936*x^71 + 37219*x^70 + 33411*x^69 + 8301*x^68 + 12949*x^67 + 28611*x^66 + 42654*x^65 + 6910*x^64 + 18523*x^63 + 31144*x^62 + 21398*x^61 + 36298*x^60 + 27158*x^59 + 918*x^58 + 38601*x^57 + 4269*x^56 + 5699*x^55 + 36444*x^54 + 34791*x^53 + 37978*x^52 + 32481*x^51 + 8039*x^50 + 11012*x^49 + 11454*x^48 + 30450*x^47 + 1381*x^46 + 32403*x^45 + 8202*x^44 + 8404*x^43 + 37648*x^42 + 43696*x^41 + 34237*x^40 + 36490*x^39 + 41423*x^38 + 35792*x^37 + 36950*x^36 + 31086*x^35 + 38970*x^34 + 12439*x^33 + 7963*x^32 + 16150*x^31 + 11382*x^30 + 3038*x^29 + 20157*x^28 + 23531*x^27 + 32866*x^26 + 5428*x^25 + 21132*x^24 + 13443*x^23 + 28909*x^22 + 42716*x^21 + 6567*x^20 + 24744*x^19 + 8727*x^18 + 14895*x^17 + 28172*x^16 + 30903*x^15 + 26608*x^14 + 27314*x^13 + 42224*x^12 + 42551*x^11 + 37726*x^10 + 11203*x^9 + 36816*x^8 + 5537*x^7 + 20301*x^6 + 17591*x^5 + 41279*x^4 + 7999*x^3 + 33753*x^2 + 34551*x + 9659
e = 65537

phi = (p^P.degree() - 1) * (p^Q.degree() - 1)
d = inverse_mod(e, phi)
''.join(map(chr, filter(lambda x:x, (c^d).list())))

# 'watevr{RSA_from_ikea_is_fun_but_insecure#k20944uehdjfnjd335uro}'