37、多项式算术及其应用

多项式算术及其应用

在数学和计算机科学领域，多项式算术有着广泛的应用。本文将深入探讨多项式矩阵乘法、有理函数重构及其应用，以及更快的多项式算术算法。

1. 多项式矩阵乘法

当需要对两个元素为 (F[X]) 的矩阵进行乘法运算时，可以利用多项式的中国剩余定理来加速计算。若域 (F) 足够大，就能直接使用多项式求值和插值，无需担心构造不可约多项式。

假设有两个矩阵 (A, B \in F[X]^{\ell\times\ell})，且 (A) 和 (B) 的所有元素都是次数至多为 (M) 的多项式，同时 (|F| \geq 2M + 1)。通过多项式求值和插值，可在 (F) 中以 (O(\ell^2M^2 + \ell^3M)) 次运算计算乘积矩阵 (C = A \cdot B)，而直接计算的复杂度为 (O(\ell^3M^2))。

2. 有理函数重构及其应用

2.1 有理函数重构定理

设 (r^, t^) 为非负整数，(n, y \in F[X]) 为多项式，满足 (r^+ t^\leq \text{deg}(n)) 且 (\text{deg}(y) < \text{deg}(n))。对输入 (a := n) 和 (b := y) 运行扩展欧几里得算法，会有以下结论：
- 存在唯一的索引 (i = 1, \ldots, \ell + 1)，使得 (\text{deg}(r_i) < r^\leq \text{deg}(r_{i - 1}))，且对于该 (i)，有 (t_i \neq 0)。令 (r’ := r_i)，(s’ := s