4378187236568178488156374902954033554168817612809876836185687985356955098509507459200406211027348332345207938363733672019865513005277165462577884966531159self.b

5998166089683146776473147900393246465728273146407202321254637450343601143170006002385750343013383427197663710513197549189847700541599566914287390375415919self.c

4686793799228153029935979752698557491405526130735717565192889910432631294797555886472384740255952748527852713105925980690986384345817550367242929172758571self.d

4434206240071905077800829033789797199713643458206586525895301388157719638163994101476076768832337473337639479654350629169805328840025579672685071683035027self.modulus

modulusdef

1):coefficients.append(rng.next())shares

[]for

p=12670098302188507742440574100120556372985016944156009521523684257469947870807586552014769435979834701674318132454810503226645543995288281801918123674138911

Share_1=(1,

6435837956013280115905597517488571345655611296436677708042037032302040770233786701092776352064370211838708484430835996068916818951183247574887417224511655)

显然抽象一下就是要你求一个多项式的根。

但是我突然意识到我完全不知道怎么求多项式的根，因为我发现我好像连二次剩余都不会求（或者说

最后在大力掉库后轻松通过了这题，不过调库也调了半天，因为我意识到我根本不知道关于多项式求根的哪些事情是容易求的，而且

sage

12670098302188507742440574100120556372985016944156009521523684257469947870807586552014769435979834701674318132454810503226645543995288281801918123674138911

'x').gen()class

4378187236568178488156374902954033554168817612809876836185687985356955098509507459200406211027348332345207938363733672019865513005277165462577884966531159self.b

5998166089683146776473147900393246465728273146407202321254637450343601143170006002385750343013383427197663710513197549189847700541599566914287390375415919self.c

4686793799228153029935979752698557491405526130735717565192889910432631294797555886472384740255952748527852713105925980690986384345817550367242929172758571self.d

4434206240071905077800829033789797199713643458206586525895301388157719638163994101476076768832337473337639479654350629169805328840025579672685071683035027def

(self.a

1):coefficients.append(rng.next())return

10f

6435837956013280115905597517488571345655611296436677708042037032302040770233786701092776352064370211838708484430835996068916818951183247574887417224511655print(f.any_root())

其实后来我才知道这个多项式有两个根，这随便输出了一个出解了可以说是运气好（

inline">\(\mathbb{F}_q\)

个元素的域，有一些有限域唯一啥的定理，由于我的抽象代数基础过于烂，这部分等我下学期学了抽象代数之后再来研究吧。

\mathbb{F}_{p^n}\)，简单来说就是

inline">\(\mathbb{F}_{p^n}\)

同构于模

然后好像还需要一些代数扩张的知识，但是我仍然不会，所以我要口胡一些东西，哈哈。

个解。

这个扩张的过程也可以放到有限域上，具体细节我没学，总之对于一个

inline">\(\mathbb{F}_{q^n}[x]\)

inline">\(\mathbb{F}_{p^n}\)

inline">\(\mathbb{F}_{p^m}\)，前者是后者的子域当且仅当

m\)。

所以如果一个多项式有若干因子，只需要对这些因子的次数求一个

inline">\(\mathrm{lcm}\)，然后放到

inline">\(\mathbb{F}_{q^\mathrm{lcm}}[x]\)

inline">\(\mathbb{F}_q[x]\)

inline">\(\mathbb{F}_q[x]\)

次不可约多项式的乘积（这和前面代数扩张应该是相同道理的？

）。

其实求根就是要找到多项式所有一次的因子，而我们知道所有一次的因子的乘积其实就是

于是我们可以很容易的求出一个多项式有多少不同的根，只需要看

inline">\(x^q-x\)，这样复杂度就是被

放到商环上然后再求幂，否则指数爆炸了就。

lift()

Rabin

(x^{\frac{q-1}{2}}-1)(x^{\frac{q-1}{2}}+1)\)。

而

inline">\(x^{\frac{q-1}{2}}-1\)

inline">\(x^{\frac{q-1}{2}}-1\)

求一个

inline">\(\gcd\)，就有可能把多项式一分为二。

而我们可以将所有的根随机位移一个

inline">\(\delta\)，也就是求一个

inline">\((x+\delta)^{\frac{q-1}{2}}-1\)，某一个根是这个多项式的根的概率就约等于

inline">\(\frac{1}{2}\)。

于是，我们只需要随机若干次

inline">\(\delta\)，每次把这个多项式和原多项式

inline">\(x^{\frac{q-1}{2}}-1\)

的根其实就是所有有二次剩余的数，不过大概跟这个算法没啥关系。

f.base_ring().cardinality()assert
(q-1)
distinct_root_poly(f)print("Initial
gcd(f,x^q-x)
g.base_ring().random_element()print("delta
%s"
g.parent().quotient(g)print("Better
%s"
distinct_rational_roots(f,recurse=False):"""Returns
list
f.base_ring().cardinality()assert
(q-1)
g.base_ring().random_element()pig
gcd(g,
这个算法只能找到不同的根，不能找到重数。
如果要找重数，一种做法是直接把单项式除掉然后再看是不是根，但是这个很慢（重数为
inline">\(O(d^2)\)）。
没有平方因子，这称为无平方分解。
这个过程可以继续循环下去，每次可以将一个因子去掉，于是就可以依次求出
因为一开始我们就去掉了重复的因子，所以这个算法减少了很多的冗余计算。
class="math
squarefree_factorization(f):"""Yun's
algorithm
f.base_ring().characteristic()if
not
于是将两者结合一下，就得到了一个能够求出重数的求根算法。
squarefree_factorization(f)return
reduce(lambda
distinct_rational_roots(gs[i])]
for
id="cantor-zassenhaus-多项式分解算法">Cantor-Zassenhaus
多项式分解算法
求根只是求出了所有的一次因子，我们可不可以类似的求出整个的分解呢？
我们可以把上面的求根算法直接放到代数扩张的环上面再做，也就是在
inline">\(\mathbb{F}_{q^i}\)
里找一个随机元素
inline">\(\frac{\mathbb{F}_{q}[x]}{f}
\simeq
\frac{\mathbb{F}_{q}[x]}{f_n}\)（使用
CRT
\frac{\mathbb{F}_{q}[x]}{f}\)
inline">\(\frac{\mathbb{F}_{q}[x]}{f_i}\)
class="math
inline">\(\frac{\mathbb{F}_{q}[x]}{f_i}\simeq
\mathbb{F}_{q^d}\)），于是一定有
equal_degree_factorization(f,j):"""Completely
factors
f.parent()([Fq.random_element()
for
equal_degree_factorization(h,j)
equal_degree_factorization(f//h,j)#
this
equal_degree_factorization(h,j)
equal_degree_factorization(f//h,j)def
***
distinct_degree_factorization(gs[i],squarefree=True)for
[(g,i)
equal_degree_factorization(gis[j],j)]#
sort
的是这个优化用到了多项式复合，也就是这玩意还是的确有用的，不是只有在
conbinatorics
class="post-meta-container">