Struct nekolib::math::Polynomial

pub struct Polynomial<M: NttFriendly>(/* private fields */);

多項式。

Notations

$\gdef\deg{\operatorname{deg}}$ $\gdef\dd{\mathrm{d}}$ $\gdef\dx{{\textstyle{\frac{\dd}{\dd x}}}}$ $\gdef\dy{{\textstyle{\frac{\dd}{\dd y}}}}$ $\gdef\qed{\square}$

$(f(x), g(x))\bmod x^n$ を $(f(x)\bmod x^n, g(x)\bmod x^n)$ の略記として用いる。

$f(x) = \sum_{i=0}^{n} a_i x^i$ ($a_{n}\neq 0$) に対して $\deg(f) = n$ とする。 ただし、$f(x) = 0$ に対しては $\deg(f) = -\infty$ とする。

Implementations

impl<M: NttFriendly> Polynomial<M>

pub fn new() -> Self

$f(x) = 0$ を返す。

Examples

use nekolib::math::{Mod998244353, Polynomial};
let f = Polynomial::<Mod998244353>::new();
assert!(f.is_zero());

use nekolib::math::{Mod998244353, Polynomial};
type Poly = Polynomial<Mod998244353>;
let f = Poly::new();
assert!(f.is_zero());

pub fn recip(&self, len: usize) -> Self

$f(x)\cdot g(x) \equiv 1\pmod{x^n}$ なる $g(x) \bmod x^n$ を返す。

Examples

let f: Poly = [1, -1].into();
let g: Poly = [1; 10].into();
assert_eq!(f.recip(10), g);

pub fn truncated(self, len: usize) -> Self

$f(x)\bmod x^n$ を返す。

Examples

let f: Poly = [1, 2, 3, 4, 5].into();
let g: Poly = [1, 2, 3].into();
assert_eq!(f.truncated(3), g);

pub fn ref_truncated(&self, len: usize) -> Self

$f(x)\bmod x^n$ を返す。

Examples

let f: Poly = [1, 2, 3, 4, 5].into();
let g: Poly = [1, 2, 3].into();
assert_eq!(f.ref_truncated(3), g);
assert_eq!(f.ref_truncated(3), g);

pub fn truncate(&mut self, len: usize)

$f(x) \gets f(x) \bmod x^n$ で更新する。

Examples

let mut f: Poly = [1, 2, 3, 4, 5].into();
let g: Poly = [1, 2, 3].into();
f.truncate(3);
assert_eq!(f, g);

pub fn reversed(self) -> Self

$f(x)^{\mathrm{R}} \triangleq x^{\deg(f)}\cdot f(1/x)$ を返す。ただし $f(x) = 0$ の場合は $0$ を返す。

Examples

let f: Poly = [0, 1, 2].into();
let g: Poly = [2, 1].into();
assert_eq!(f.reversed(), g);

pub fn reverse(&mut self)

$f(x) \gets f(x)^{\mathrm{R}}$ で更新する。

Examples

let mut f: Poly = [0, 1, 2].into();
let g: Poly = [2, 1].into();
f.reverse();
assert_eq!(f, g);

pub fn differential(self) -> Self

$f'(x)$ を返す。

$n = \deg(f) + 1$ とし、 $f(x) = \sum_{i=0}^{n-1} a_i x^i$ のとき、 $$\begin{aligned} f'(x) &= \sum_{i=1}^{n-1} i\cdot a_i x^{i-1} \\ &= \sum_{i=0}^{n-2} (i+1)\cdot a_{i+1} x^i \end{aligned}$$ となる。ただし、$f(x) = 0$ のとき $f'(x) = 0$ である。

Examples

let f: Poly = [1, 1, 1, 1].into();
let g: Poly = [1, 2, 3].into();
assert_eq!(f.differential(), g);

pub fn differentiate(&mut self)

$f(x) \gets f'(x)$ で更新する。

Examples

let mut f: Poly = [1, 1, 1, 1].into();
let g: Poly = [1, 2, 3].into();
f.differentiate();
assert_eq!(f, g);

pub fn integral(self) -> Self

$\int_0^x f(t)\, \dd{t}$ を返す。

$n = \deg(f) + 1$ とし、 $f(x) = \sum_{i=0}^{n-1} a_i x^i$ のとき、 $$\begin{aligned} \int_0^x f(t)\, \dd{t} &= \sum_{i=0}^{n-1} (i+1)^{-1}\cdot a_i x^{i+1} \\ &= \sum_{i=1}^{n} i\cdot a_i x^{i+1} \end{aligned}$$ となる。ただし、$f(x) = 0$ のとき $\int_0^t f(t)\, \dd{t} = 0$ である。

Examples

let f: Poly = [1, 2, 3].into();
let g: Poly = [0, 1, 1, 1].into();
assert_eq!(f.integral(), g);

let f = Poly::from([1, -1]).recip(4).integral();
let g = Poly::from([0, 1, 499122177, 332748118, 748683265]);
// \Integrate (1/(1-x)) dx = x + 1/2 x^2 + 1/3 x^3 + 1/4 x^4 + ...
assert_eq!(f, g);

pub fn integrate(&mut self)

$f(x) \gets \int_0^x f(t)\, \dd{t}$ で更新する。

Examples

let mut f: Poly = [1, 2, 3].into();
let g: Poly = [0, 1, 1, 1].into();
f.integrate();
assert_eq!(f, g);

pub fn log(&self, len: usize) -> Self

$[x^0] f(x) = 1$ なる $f$ に対し、$\log(f(x)) \bmod x^n$ を返す。

$\log(1-f(x)) = -\sum_{n=1}^{\infty} \frac{f(x)^n}{n}$ などで定義される。 $\dx\log(f(x)) = f'(t)\cdot f(t)^{-1}$ や $\log(f(x)g(x)) = \log(f(x))+\log(g(x))$ などが成り立つ。

また、$[x^0]\log(f(x)) = 0$ となる。

Examples

let f: Poly = [1, 1].into();
let g: Poly = [0, 1, 499122176, 332748118, 249561088].into();
// log(1+x) = x - 1/2 x^2 + 1/3 x^3 - 1/4 x^4 + ...
assert_eq!(f.log(5), g);
assert_eq!(f.log(5).differential(), [1, -1, 1, -1].into());

pub fn exp(&self, len: usize) -> Self

$[x^0] f(x) = 0$ なる $f$ に対し、$\exp(f(x)) \bmod x^n$ を返す。

$\exp(f(x)) = \sum_{n=0}^{\infty} \frac{f(x)^n}{n!}$ によって定義される。 $\dx \exp(f(x)) = \exp(f(x))\cdot \dx f(x)$ や $\exp(f(x)+g(x)) = \exp(f(x))\exp(g(x))$ などが成り立つ。

また、$\prod_i f_i(x) = \exp(\sum_i \log(f_i(x)))$ や $[x^0] \exp(f(x)) = 1$ も成り立つ。

Examples

let f: Poly = [0, 1].into();
let g: Poly = [1, 1, 499122177, 166374059, 291154603].into();
// exp(x) = 1 + x + 1/2 x^2 + 1/6 x^3 + 1/24 x^4 + ...
assert_eq!(f.exp(5), g);

pub fn pow<I: Into<StaticModInt<M>>>(&self, k: I, len: usize) -> Self

$f(x)^k \bmod x^n$ を返す。

Ideas

自明なケースとして、 $k = 0$ のときは $1$ である。 $f(x) = 0$ のときは $0$ である。$0^0 = 1$ としている。

それ以外のとき、$f(x) = a_l x^l \cdot (1+g(x))$ と書ける。 $$\begin{aligned} f(x)^k &= (a_l x^l \cdot (1+g(x)))^k \\ &= a_l^k x^{lk} \cdot \exp(k\log(1+g(x))) \end{aligned}$$

によって計算できる。$\log$ の引数の定数項が $1$ であることと、$\exp$ の引数の定数項が $0$ になっていることに注意せよ。

Examples

let f: Poly = [1, 1].into();
let g: Poly = [1, 4, 6, 4, 1].into();
// (1+x)^4 = 1 + 4x + 6x^2 + 4x^3 + x^4
assert_eq!(f.pow(4, 10), g);

let f: Poly = [0, 0, 2, 6].into();
let g = Poly::from([64, 1152, 8640, 34560]) << 12;
// (2x^2+6x^3)^6
// = (2x^2 (1 + 3x))^6
// = 64x^12 (1 + 18x + 135x^2 + 540x^3 + ...)
// = 64x^12 + 1152x^13 + 8640x^14 + 34560x^15 + ...
assert_eq!(f.pow(6, 16), g);

pub fn circular(&self, im: &Self, len: usize) -> (Self, Self)

$[x^0] f(x) = 0$ かつ $[x^0] g(x) = 0$ なる $h(x) = f(x)+ig(x)$ に対して $(\cos(h(x)), \sin(h(x))) \bmod x^n$ を返す。

$\exp(f(x) + ig(x)) = \exp(f(x))\cdot(\cos(g(x)) + i\sin(g(x)))$ から定義される。

Examples

let zero = Poly::new();
let f: Poly = [0, 1].into();
let g_re: Poly = [1, 0, -499122177, 0, 291154603, 0].into();
let g_im: Poly = [0, 1, 0, -166374059, 0, 856826403].into();
// cos(x) = 1 - 1/2 x^2 + 1/24 x^4 - ...
// sin(x) = x - 1/6 x^3 + 1/120 x^5 - ...
assert_eq!(zero.circular(&f, 6), (g_re, g_im));

pub fn cos(&self, len: usize) -> Self

$\cos(f(x)) \bmod x^n$ を返す。

Examples

let zero = Poly::new();
let f: Poly = [0, 1].into();
let g: Poly = [1, 0, -499122177, 0, 291154603, 0].into();
// cos(x) = 1 - 1/2 x^2 + 1/24 x^4 - ...
assert_eq!(f.cos(6), g);

pub fn sin(&self, len: usize) -> Self

$\sin(f(x)) \bmod x^n$ を返す。

Examples

let zero = Poly::new();
let f: Poly = [0, 1].into();
let g: Poly = [0, 1, 0, -166374059, 0, 856826403].into();
// sin(x) = x - 1/6 x^3 + 1/120 x^5 - ...
assert_eq!(f.sin(6), g);

pub fn tan(&self, len: usize) -> Self

$\tan(f(x)) \bmod x^n$ を返す。

Examples

let zero = Poly::new();
let f: Poly = [0, 1].into();
let g: Poly = [0, 1, 0, 332748118, 0, 732045859].into();
// tan(x) = x + 1/3 x^3 + 2/15 x^5 ...
assert_eq!(f.tan(6), g);

pub fn polyeqn(self, n: usize, f_dfr: impl Fn(&Self, usize) -> Self) -> Self

self を初期解とし、$f(y) = 0$ を満たす $y$ を求める。

f_dfr は $(y, n)$ に対して $f(y)\cdot f'(y)^{-1} \bmod x^n$ を返すとする。

Newton 法による $$y_{k+1} = (y_k - f(y_k)\cdot f'(y_k)^{-1}) \bmod x^{2^k}$$ に基づき、 $$y\xleftarrow{-} (f(y)\cdot f'(y)^{-1}) \bmod x^{2^k}$$ で更新する。

Ideas

多項式 $\varphi(y)$ の $g$ のまわりでの Taylor 展開は、 $$\varphi(y) = \sum_{i=0}^{\deg(\varphi)} \varphi_i\cdot (y-g)^i$$ として定義される。各係数 $\varphi_i$ は一意に定まり、Taylor 係数と呼ばれる。

微分して $y=g$ を代入することなどで、ある多項式 $\psi$ を用いて以下のように書ける。 $$\varphi(y) = \varphi(g) + \left(\dy\varphi(g)\right)\cdot (y-g) + \psi(y)\cdot (y-g)^2.$$

さて、$f(y_k)\equiv 0 \pmod{x^{2^k}}$ なる $y_k$ が得られており、かつ $\dy f(y_k)$ が逆元を持つとき、 $$y_{k+1} \triangleq y_k - f(y_k)\cdot \dy f(y_k)^{-1} \bmod {x^{2^{k+1}}}$$ で得られる $y_{k+1}$ によって $f(y_{k+1}) \equiv 0\pmod{x^{2^{k+1}}}$ が成り立つことを示す。

Proof

まず、$f(y_k) \equiv \pmod{x^{2^k}}$ であることと、$x^{2^k}$ が $x^{2^{k+1}}$ を割り切ることから $y_{k+1} = y_k \pmod{x^{2^k}}$ は成り立つ。 これより、$(y_{k+1} - y_k)^2 \pmod {x^{2^{k+1}}}$ も従う。 さて、多項式 $f$ の $y_k$ のまわりでの Taylor 展開から、ある $\psi$ に対して $$f(y) = f(y_k) + \left(\dy f(y_k)\right)\cdot (y-y_k) + \psi(y)\cdot (y-y_k)^2$$ が成り立つので、 $$f(y) \equiv f(y_k) + \left(\dy f(y_k)\right)\cdot (y-y_k) \equiv 0 \pmod {x^{2^{k+1}}}$$ となる。$y$ について整理して $$y \equiv y_k -f(y_k)\cdot \dy f(y_k)^{-1} \pmod{x^{2^{k+1}}}$$ を得る。$\qed$

なお、一般に、環 $R$ において、$x\in R$ が $y\in R$ を法とする逆元を持つことは、 $y^i$ ($i\in\N_{\ge 1}$) を法とする逆元を持つことと同値である。

よって、上記の手続きを繰り返すことにより、$y$ を任意の次数で求めることができる。 $x^{2^k}\to x^{2^{k+1}}$ としていた箇所は、一般に $x^l\to x^{2l}$ と置き換えることも可能。 実際には、定数項のみを与え、$x^{2^0}=x$ を法として始めることが多いであろう。

References

• Von Zur Gathen, Joachim, and Jürgen Gerhard. Modern computer algebra. Cambridge university press, 2013.

Examples

let one = Poly::from([1]);
let two = Poly::from([2]);
let three = Poly::from([3]);
let catalan = |y: &Poly, n| {
    // c(x) = 1 + x c(x)^2
    // f(y) = x y^2 - y + 1
    // f(y) / f'(y) = (x y^2 - y + 1) / (2xy - 1)
    let f = ((y * y) << 1) - y + &one;
    let df = ((y * &two) << 1) - &one;
    (f.truncated(n) * df.recip(n)).truncated(n)
};
let f = Poly::from([1]).polyeqn(6, catalan);
let g = Poly::from([1, 1, 2, 5, 14, 42]);
assert_eq!(f, g);

pub fn fode(self, n: usize, f_df: impl Fn(&Self, usize) -> (Self, Self)) -> Self

self を初期解とし、$y' = f(y, x)$ を満たす $y(x)$ を求める。

f_df は $(y, n)$ に対して $(f(y, x), f'(y, x)) \bmod x^n$ を返すとする。

Ideas

基本的な方針は Newton 法と同じである。Taylor 展開を用いて二次収束する更新式を得る。

$y\equiv y_k \pmod{x^{2^k}}$ を満たす $y_k = \sum_{i=0}^{2^k-1} a_i x^i$ が得られているとする。 このとき、ある $\psi(y)$ が存在して、$f(y, x)$ の $y_k$ のまわりでの Taylor 展開が $$f(y, x) = f(y_k, x) + \left(\dy f(y_k, x)\right)\cdot (y-y_k) + \psi(y)\cdot (y-y_k)^2$$ と書ける。仮定より $y-y_k\equiv 0\pmod{x^{2^k}}$ なので、 $$f(y, x) \equiv f(y_k, x) + \left(\dy f(y_k, x)\right)\cdot (y-y_k) \pmod{x^{2^{k+1}}}$$ となる。また、$y' = y_k' + (y' - y_k')$ と書けるので、$y' = f(y, x)$ より $$y_k' + (y' - y_k') \equiv f(y_k, x) + \left(\dy f(y_k, x)\right)\cdot (y-y_k) \pmod{x^{2^{k+1}}}$$ が成り立つ。

ここで $e_k = y-y_k$ とおくと、 $$y_k' + e_k' \equiv f(y_k, x) + \left(\dy f(y_k, x)\right)\cdot e_k \pmod{x^{2^{k+1}}}$$ が成り立つ。$e_k$ について整理して $$e_k' + \underbrace{\left(-\dy f(y_k, x)\right)}_{g(x)}\cdot e_k \equiv \underbrace{f(y_k, x) - y_k'\vphantom{\left(\dy\right)}}_{h(x)} \pmod{x^{2^{k+1}}}$$ を得る。$e_k' + g(x)\cdot e_k \equiv h(x)$ の形式の微分方程式が得られたので、これについて考える。

$\mu(x) = \exp(\int_0^x g(t)\, \dd{t})$ を両辺に掛けて¹、 $$\begin{aligned} e_k'\cdot\mu(x) + g(x)\cdot e_k\cdot\mu(x) &\equiv h(x) \mu(x) \\ \dx \left(e_k\cdot\mu(x)\right) &\equiv h(x) \mu(x) \\ \end{aligned}$$ より、 $$e_k \equiv \frac{1}{\mu(x)}\left(\int_0^x h(t)\mu(t)\, \dd{t} + C\right) \pmod{x^{2^{k+1}}}$$ を得る。$\exp$ の性質から $\mu(x) \equiv 1 \pmod{x}$ であり、$C\mu(x)^{-1} \equiv C\pmod{x}$ となる。 ところで、$e_k = y-y_k\equiv 0 \pmod{x^{2^k}}$ であったため、$C = 0$ となる必要がある。

さて、$y = y_k + e_k \pmod{x^{2^{k+1}}}$ なので、$y_{k+1} \triangleq y_k + e_k$ とすると、$y \equiv y_{k+1} \pmod{x^{2^{k+1}}}$ を得られる。 すなわち、以下で更新することになる。

$$\begin{aligned} g_k &= -\dy f(y_k, x) \bmod x^{2^{k+1}} \\ \mu_k &= \exp\left(\int_0^x g(t)\, \dd{t}\right) \bmod x^{2^{k+1}}\\ e_k &= \frac{1}{\mu_k}\int_0^x \big(f(y_k, x)-y_k')\cdot \mu_k\big)\, \dd{x} \bmod x^{2^{k+1}} \\ y_{k+1} &= y_k + e_k \end{aligned}$$

実際には $y$ を immutable で管理して $y\xleftarrow{+}e_k$ の更新をしている。

References

• Fateman, Richard J. “Series solutions of algebraic and differential equations: a comparison of linear and quadratic algebraic convergence.” In Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, pp. 11–16. 1989.
• Von Zur Gathen, Joachim, and Jürgen Gerhard. Modern computer algebra. Cambridge university press, 2013.

Examples

let x: Poly = [0, 1].into();
let one: Poly = [1].into();
let three: Poly = [3].into();
let f_df = |y: &Poly, n| {
    let d = y - &x;
    // (f(y), f'(y)) = ((y-x)^3+1, 3(y-x)^2)
    let dd = (&d * &d).truncated(n);
    ((&dd * &d + &one).truncated(n), &dd * &three)
};

let n = 4;
let y = Poly::from([2]).fode(n + 1, f_df);

// y = x + 2/sqrt(1-8x) = 2 + 9x + 48x^2 + 320x^3 + 2240x^4 + ...
assert_eq!(y, [2, 9, 48, 320, 2240].into());
assert_eq!(f_df(&y, n).0, y.differential());

---

1. $\exp$ の引数の定数項は $0$ となる必要がある。 ↩

pub fn get(&self, i: usize) -> StaticModInt<M>

$[x^i] f(x)$ を返す。

Examples

let f: Poly = [5, 0, 7].into();
assert_eq!(f.get(0).get(), 5);
assert_eq!(f.get(1).get(), 0);
assert_eq!(f.get(2).get(), 7);
assert_eq!(f.get(3).get(), 0);
assert_eq!(f.get(4).get(), 0);

pub fn eval(&self, t: impl Into<StaticModInt<M>>) -> StaticModInt<M>

pub fn into_inner(self) -> Vec<StaticModInt<M>>

$([x^i] f(x))_{i=0}^{\deg(f)}$ を返す。

pub fn fft_butterfly(&mut self, len: usize)

$F_{\omega}[f]$ を返す。

$F$ とか $\omega$ とかの定義をちゃんと書く。butterfly をどう書くか悩ましい。

pub fn fft_inv_butterfly(&mut self, len: usize)

$F_{\omega}^{-1}[f]$ を返す。

pub fn fft_butterfly_double(&mut self, to_len: usize)

$F_{\omega^2}[f]$ を $F_{\omega}[f]$ で更新する。

pub fn is_zero(&self) -> bool

$f(x) = 0$ を返す。

pub fn len(&self) -> usize

$\deg(f)-1$ を返す。ただし $f(x) = 0$ のときは $0$ を返す。

pub fn div_mod(&self, other: &Polynomial<M>) -> (Self, Self)

$(f(x) / g(x), f(x) \bmod g(x))$ を返す。

$f(x) / g(x)$ は $f(x)\cdot g(x)^{-1}$ ではなく多項式としての除算である。

pub fn div_nth(&self, other: &Polynomial<M>, n: usize) -> StaticModInt<M>

$[x^n] f(x) \cdot g(x)^{-1}$ を返す。

Trait Implementations

impl<'a, M: NttFriendly> Add<&'a Polynomial<M>> for &'a Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the + operator.

fn add(self, other: &'a Polynomial<M>) -> Polynomial<M>

Performs the + operation.

impl<'a, M: NttFriendly> Add<&'a Polynomial<M>> for Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the + operator.

fn add(self, other: &'a Polynomial<M>) -> Polynomial<M>

Performs the + operation.

impl<'a, M: NttFriendly> Add<&'a StaticModInt<M>> for &'a Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the + operator.

fn add(self, other: &'a StaticModInt<M>) -> Polynomial<M>

Performs the + operation.

impl<'a, M: NttFriendly> Add<&'a StaticModInt<M>> for Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the + operator.

fn add(self, other: &'a StaticModInt<M>) -> Polynomial<M>

Performs the + operation.

impl<'a, M: NttFriendly> Add<Polynomial<M>> for &'a Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the + operator.

fn add(self, other: Polynomial<M>) -> Polynomial<M>

Performs the + operation.

impl<M: NttFriendly> Add<Polynomial<M>> for Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the + operator.

fn add(self, other: Polynomial<M>) -> Polynomial<M>

Performs the + operation.

impl<'a, M: NttFriendly> Add<StaticModInt<M>> for &'a Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the + operator.

fn add(self, other: StaticModInt<M>) -> Polynomial<M>

Performs the + operation.

impl<M: NttFriendly> Add<StaticModInt<M>> for Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the + operator.

fn add(self, other: StaticModInt<M>) -> Polynomial<M>

Performs the + operation.

impl<'a, M: NttFriendly> AddAssign<&'a Polynomial<M>> for Polynomial<M>

fn add_assign(&mut self, other: &'a Polynomial<M>)

Performs the += operation.

impl<'a, M: NttFriendly> AddAssign<&'a StaticModInt<M>> for Polynomial<M>

fn add_assign(&mut self, other: &'a StaticModInt<M>)

Performs the += operation.

impl<M: NttFriendly> AddAssign<Polynomial<M>> for Polynomial<M>

fn add_assign(&mut self, other: Polynomial<M>)

Performs the += operation.

impl<M: NttFriendly> AddAssign<StaticModInt<M>> for Polynomial<M>

fn add_assign(&mut self, other: StaticModInt<M>)

Performs the += operation.

impl<'a, M: NttFriendly> BitAnd<&'a Polynomial<M>> for &'a Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the & operator.

fn bitand(self, other: &'a Polynomial<M>) -> Polynomial<M>

Performs the & operation.

impl<'a, M: NttFriendly> BitAnd<&'a Polynomial<M>> for Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the & operator.

fn bitand(self, other: &'a Polynomial<M>) -> Polynomial<M>

Performs the & operation.

impl<'a, M: NttFriendly> BitAnd<&'a StaticModInt<M>> for &'a Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the & operator.

fn bitand(self, other: &'a StaticModInt<M>) -> Polynomial<M>

Performs the & operation.

impl<'a, M: NttFriendly> BitAnd<&'a StaticModInt<M>> for Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the & operator.

fn bitand(self, other: &'a StaticModInt<M>) -> Polynomial<M>

Performs the & operation.

impl<'a, M: NttFriendly> BitAnd<Polynomial<M>> for &'a Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the & operator.

fn bitand(self, other: Polynomial<M>) -> Polynomial<M>

Performs the & operation.

impl<M: NttFriendly> BitAnd<Polynomial<M>> for Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the & operator.

fn bitand(self, other: Polynomial<M>) -> Polynomial<M>

Performs the & operation.

impl<'a, M: NttFriendly> BitAnd<StaticModInt<M>> for &'a Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the & operator.

fn bitand(self, other: StaticModInt<M>) -> Polynomial<M>

Performs the & operation.

impl<M: NttFriendly> BitAnd<StaticModInt<M>> for Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the & operator.

fn bitand(self, other: StaticModInt<M>) -> Polynomial<M>

Performs the & operation.

impl<'a, M: NttFriendly> BitAndAssign<&'a Polynomial<M>> for Polynomial<M>

fn bitand_assign(&mut self, other: &'a Polynomial<M>)

Performs the &= operation.

impl<'a, M: NttFriendly> BitAndAssign<&'a StaticModInt<M>> for Polynomial<M>

fn bitand_assign(&mut self, other: &'a StaticModInt<M>)

Performs the &= operation.

impl<M: NttFriendly> BitAndAssign<Polynomial<M>> for Polynomial<M>

fn bitand_assign(&mut self, other: Polynomial<M>)

Performs the &= operation.

impl<M: NttFriendly> BitAndAssign<StaticModInt<M>> for Polynomial<M>

fn bitand_assign(&mut self, other: StaticModInt<M>)

Performs the &= operation.

impl<M: Clone + NttFriendly> Clone for Polynomial<M>

fn clone(&self) -> Polynomial<M>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<M: NttFriendly> Debug for Polynomial<M>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<M: NttFriendly> Display for Polynomial<M>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'a, M: NttFriendly> Div<&'a Polynomial<M>> for &'a Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the / operator.

fn div(self, other: &'a Polynomial<M>) -> Polynomial<M>

Performs the / operation.

impl<'a, M: NttFriendly> Div<&'a Polynomial<M>> for Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the / operator.

fn div(self, other: &'a Polynomial<M>) -> Polynomial<M>

Performs the / operation.

impl<'a, M: NttFriendly> Div<&'a StaticModInt<M>> for &'a Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the / operator.

fn div(self, other: &'a StaticModInt<M>) -> Polynomial<M>

Performs the / operation.

impl<'a, M: NttFriendly> Div<&'a StaticModInt<M>> for Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the / operator.

fn div(self, other: &'a StaticModInt<M>) -> Polynomial<M>

Performs the / operation.

impl<'a, M: NttFriendly> Div<Polynomial<M>> for &'a Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the / operator.

fn div(self, other: Polynomial<M>) -> Polynomial<M>

Performs the / operation.

impl<M: NttFriendly> Div<Polynomial<M>> for Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the / operator.

fn div(self, other: Polynomial<M>) -> Polynomial<M>

Performs the / operation.

impl<'a, M: NttFriendly> Div<StaticModInt<M>> for &'a Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the / operator.

fn div(self, other: StaticModInt<M>) -> Polynomial<M>

Performs the / operation.

impl<M: NttFriendly> Div<StaticModInt<M>> for Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the / operator.

fn div(self, other: StaticModInt<M>) -> Polynomial<M>

Performs the / operation.

impl<'a, M: NttFriendly> DivAssign<&'a Polynomial<M>> for Polynomial<M>

fn div_assign(&mut self, other: &'a Polynomial<M>)

Performs the /= operation.

impl<'a, M: NttFriendly> DivAssign<&'a StaticModInt<M>> for Polynomial<M>

fn div_assign(&mut self, other: &'a StaticModInt<M>)

Performs the /= operation.

impl<M: NttFriendly> DivAssign<Polynomial<M>> for Polynomial<M>

fn div_assign(&mut self, other: Polynomial<M>)

Performs the /= operation.

impl<M: NttFriendly> DivAssign<StaticModInt<M>> for Polynomial<M>

fn div_assign(&mut self, other: StaticModInt<M>)

Performs the /= operation.

impl<'a, M: NttFriendly> From<&'a [StaticModInt<M>]> for Polynomial<M>

fn from(buf: &'a [StaticModInt<M>]) -> Self

Converts to this type from the input type.

impl<'a, M: NttFriendly> From<&'a [i128]> for Polynomial<M>

fn from(buf: &'a [i128]) -> Self

Converts to this type from the input type.

impl<'a, M: NttFriendly> From<&'a [i16]> for Polynomial<M>

fn from(buf: &'a [i16]) -> Self

Converts to this type from the input type.

impl<'a, M: NttFriendly> From<&'a [i32]> for Polynomial<M>

fn from(buf: &'a [i32]) -> Self

Converts to this type from the input type.

impl<'a, M: NttFriendly> From<&'a [i64]> for Polynomial<M>

fn from(buf: &'a [i64]) -> Self

Converts to this type from the input type.

impl<'a, M: NttFriendly> From<&'a [i8]> for Polynomial<M>

fn from(buf: &'a [i8]) -> Self

Converts to this type from the input type.

impl<'a, M: NttFriendly> From<&'a [isize]> for Polynomial<M>

fn from(buf: &'a [isize]) -> Self

Converts to this type from the input type.

impl<'a, M: NttFriendly> From<&'a [u128]> for Polynomial<M>

fn from(buf: &'a [u128]) -> Self

Converts to this type from the input type.

impl<'a, M: NttFriendly> From<&'a [u16]> for Polynomial<M>

fn from(buf: &'a [u16]) -> Self

Converts to this type from the input type.

impl<'a, M: NttFriendly> From<&'a [u32]> for Polynomial<M>

fn from(buf: &'a [u32]) -> Self

Converts to this type from the input type.

impl<'a, M: NttFriendly> From<&'a [u64]> for Polynomial<M>

fn from(buf: &'a [u64]) -> Self

Converts to this type from the input type.

impl<'a, M: NttFriendly> From<&'a [u8]> for Polynomial<M>

fn from(buf: &'a [u8]) -> Self

Converts to this type from the input type.

impl<'a, M: NttFriendly> From<&'a [usize]> for Polynomial<M>

fn from(buf: &'a [usize]) -> Self

Converts to this type from the input type.

impl<M: NttFriendly, const N: usize> From<[StaticModInt<M>; N]> for Polynomial<M>

fn from(buf: [StaticModInt<M>; N]) -> Self

Converts to this type from the input type.

impl<M: NttFriendly, const N: usize> From<[i128; N]> for Polynomial<M>

fn from(buf: [i128; N]) -> Self

Converts to this type from the input type.

impl<M: NttFriendly, const N: usize> From<[i16; N]> for Polynomial<M>

fn from(buf: [i16; N]) -> Self

Converts to this type from the input type.

impl<M: NttFriendly, const N: usize> From<[i32; N]> for Polynomial<M>

fn from(buf: [i32; N]) -> Self

Converts to this type from the input type.

impl<M: NttFriendly, const N: usize> From<[i64; N]> for Polynomial<M>

fn from(buf: [i64; N]) -> Self

Converts to this type from the input type.

impl<M: NttFriendly, const N: usize> From<[i8; N]> for Polynomial<M>

fn from(buf: [i8; N]) -> Self

Converts to this type from the input type.

impl<M: NttFriendly, const N: usize> From<[isize; N]> for Polynomial<M>

fn from(buf: [isize; N]) -> Self

Converts to this type from the input type.

impl<M: NttFriendly, const N: usize> From<[u128; N]> for Polynomial<M>

fn from(buf: [u128; N]) -> Self

Converts to this type from the input type.

impl<M: NttFriendly, const N: usize> From<[u16; N]> for Polynomial<M>

fn from(buf: [u16; N]) -> Self

Converts to this type from the input type.

impl<M: NttFriendly, const N: usize> From<[u32; N]> for Polynomial<M>

fn from(buf: [u32; N]) -> Self

Converts to this type from the input type.

impl<M: NttFriendly, const N: usize> From<[u64; N]> for Polynomial<M>

fn from(buf: [u64; N]) -> Self

Converts to this type from the input type.

impl<M: NttFriendly, const N: usize> From<[u8; N]> for Polynomial<M>

fn from(buf: [u8; N]) -> Self

Converts to this type from the input type.

impl<M: NttFriendly, const N: usize> From<[usize; N]> for Polynomial<M>

fn from(buf: [usize; N]) -> Self

Converts to this type from the input type.

impl<M: NttFriendly> From<Vec<StaticModInt<M>, Global>> for Polynomial<M>

fn from(buf: Vec<StaticModInt<M>>) -> Self

Converts to this type from the input type.

impl<M: NttFriendly> From<Vec<i128, Global>> for Polynomial<M>

fn from(buf: Vec<i128>) -> Self

Converts to this type from the input type.

impl<M: NttFriendly> From<Vec<i16, Global>> for Polynomial<M>

fn from(buf: Vec<i16>) -> Self

Converts to this type from the input type.

impl<M: NttFriendly> From<Vec<i32, Global>> for Polynomial<M>

fn from(buf: Vec<i32>) -> Self

Converts to this type from the input type.

impl<M: NttFriendly> From<Vec<i64, Global>> for Polynomial<M>

fn from(buf: Vec<i64>) -> Self

Converts to this type from the input type.

impl<M: NttFriendly> From<Vec<i8, Global>> for Polynomial<M>

fn from(buf: Vec<i8>) -> Self

Converts to this type from the input type.

impl<M: NttFriendly> From<Vec<isize, Global>> for Polynomial<M>

fn from(buf: Vec<isize>) -> Self

Converts to this type from the input type.

impl<M: NttFriendly> From<Vec<u128, Global>> for Polynomial<M>

fn from(buf: Vec<u128>) -> Self

Converts to this type from the input type.

impl<M: NttFriendly> From<Vec<u16, Global>> for Polynomial<M>

fn from(buf: Vec<u16>) -> Self

Converts to this type from the input type.

impl<M: NttFriendly> From<Vec<u32, Global>> for Polynomial<M>

fn from(buf: Vec<u32>) -> Self

Converts to this type from the input type.

impl<M: NttFriendly> From<Vec<u64, Global>> for Polynomial<M>

fn from(buf: Vec<u64>) -> Self

Converts to this type from the input type.

impl<M: NttFriendly> From<Vec<u8, Global>> for Polynomial<M>

fn from(buf: Vec<u8>) -> Self

Converts to this type from the input type.

impl<M: NttFriendly> From<Vec<usize, Global>> for Polynomial<M>

fn from(buf: Vec<usize>) -> Self

Converts to this type from the input type.

impl<'a, M: NttFriendly> Mul<&'a Polynomial<M>> for &'a Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the * operator.

fn mul(self, other: &'a Polynomial<M>) -> Polynomial<M>

Performs the * operation.

impl<'a, M: NttFriendly> Mul<&'a Polynomial<M>> for Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the * operator.

fn mul(self, other: &'a Polynomial<M>) -> Polynomial<M>

Performs the * operation.

impl<'a, M: NttFriendly> Mul<&'a StaticModInt<M>> for &'a Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the * operator.

fn mul(self, other: &'a StaticModInt<M>) -> Polynomial<M>

Performs the * operation.

impl<'a, M: NttFriendly> Mul<&'a StaticModInt<M>> for Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the * operator.

fn mul(self, other: &'a StaticModInt<M>) -> Polynomial<M>

Performs the * operation.

impl<'a, M: NttFriendly> Mul<Polynomial<M>> for &'a Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the * operator.

fn mul(self, other: Polynomial<M>) -> Polynomial<M>

Performs the * operation.

impl<M: NttFriendly> Mul<Polynomial<M>> for Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the * operator.

fn mul(self, other: Polynomial<M>) -> Polynomial<M>

Performs the * operation.

impl<'a, M: NttFriendly> Mul<StaticModInt<M>> for &'a Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the * operator.

fn mul(self, other: StaticModInt<M>) -> Polynomial<M>

Performs the * operation.

impl<M: NttFriendly> Mul<StaticModInt<M>> for Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the * operator.

fn mul(self, other: StaticModInt<M>) -> Polynomial<M>

Performs the * operation.

impl<'a, M: NttFriendly> MulAssign<&'a Polynomial<M>> for Polynomial<M>

fn mul_assign(&mut self, other: &'a Polynomial<M>)

Performs the *= operation.

impl<'a, M: NttFriendly> MulAssign<&'a StaticModInt<M>> for Polynomial<M>

fn mul_assign(&mut self, other: &'a StaticModInt<M>)

Performs the *= operation.

impl<M: NttFriendly> MulAssign<Polynomial<M>> for Polynomial<M>

fn mul_assign(&mut self, other: Polynomial<M>)

Performs the *= operation.

impl<M: NttFriendly> MulAssign<StaticModInt<M>> for Polynomial<M>

fn mul_assign(&mut self, other: StaticModInt<M>)

Performs the *= operation.

impl<'a, M: NttFriendly> Neg for &'a Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the - operator.

fn neg(self) -> Polynomial<M>

Performs the unary - operation.

impl<M: NttFriendly> Neg for Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the - operator.

fn neg(self) -> Polynomial<M>

Performs the unary - operation.

impl<M: PartialEq + NttFriendly> PartialEq<Polynomial<M>> for Polynomial<M>

fn eq(&self, other: &Polynomial<M>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<'a, M: NttFriendly> Rem<&'a Polynomial<M>> for &'a Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the % operator.

fn rem(self, other: &'a Polynomial<M>) -> Polynomial<M>

Performs the % operation.

impl<'a, M: NttFriendly> Rem<&'a Polynomial<M>> for Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the % operator.

fn rem(self, other: &'a Polynomial<M>) -> Polynomial<M>

Performs the % operation.

impl<'a, M: NttFriendly> Rem<&'a StaticModInt<M>> for &'a Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the % operator.

fn rem(self, other: &'a StaticModInt<M>) -> Polynomial<M>

Performs the % operation.

impl<'a, M: NttFriendly> Rem<&'a StaticModInt<M>> for Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the % operator.

fn rem(self, other: &'a StaticModInt<M>) -> Polynomial<M>

Performs the % operation.

impl<'a, M: NttFriendly> Rem<Polynomial<M>> for &'a Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the % operator.

fn rem(self, other: Polynomial<M>) -> Polynomial<M>

Performs the % operation.

impl<M: NttFriendly> Rem<Polynomial<M>> for Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the % operator.

fn rem(self, other: Polynomial<M>) -> Polynomial<M>

Performs the % operation.

impl<'a, M: NttFriendly> Rem<StaticModInt<M>> for &'a Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the % operator.

fn rem(self, other: StaticModInt<M>) -> Polynomial<M>

Performs the % operation.

impl<M: NttFriendly> Rem<StaticModInt<M>> for Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the % operator.

fn rem(self, other: StaticModInt<M>) -> Polynomial<M>

Performs the % operation.

impl<'a, M: NttFriendly> RemAssign<&'a Polynomial<M>> for Polynomial<M>

fn rem_assign(&mut self, other: &'a Polynomial<M>)

Performs the %= operation.

impl<'a, M: NttFriendly> RemAssign<&'a StaticModInt<M>> for Polynomial<M>

fn rem_assign(&mut self, other: &'a StaticModInt<M>)

Performs the %= operation.

impl<M: NttFriendly> RemAssign<Polynomial<M>> for Polynomial<M>

fn rem_assign(&mut self, other: Polynomial<M>)

Performs the %= operation.

impl<M: NttFriendly> RemAssign<StaticModInt<M>> for Polynomial<M>

fn rem_assign(&mut self, other: StaticModInt<M>)

Performs the %= operation.

impl<'a, M: NttFriendly> Shl<usize> for &'a Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the << operator.

fn shl(self, sh: usize) -> Self::Output

Performs the << operation.

impl<M: NttFriendly> Shl<usize> for Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the << operator.

fn shl(self, sh: usize) -> Self::Output

Performs the << operation.

impl<M: NttFriendly> ShlAssign<usize> for Polynomial<M>

fn shl_assign(&mut self, sh: usize)

Performs the <<= operation.

impl<'a, M: NttFriendly> Shr<usize> for &'a Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the >> operator.

fn shr(self, sh: usize) -> Self::Output

Performs the >> operation.

impl<M: NttFriendly> Shr<usize> for Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the >> operator.

fn shr(self, sh: usize) -> Self::Output

Performs the >> operation.

impl<M: NttFriendly> ShrAssign<usize> for Polynomial<M>

fn shr_assign(&mut self, sh: usize)

Performs the >>= operation.

impl<'a, M: NttFriendly> Sub<&'a Polynomial<M>> for &'a Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the - operator.

fn sub(self, other: &'a Polynomial<M>) -> Polynomial<M>

Performs the - operation.

impl<'a, M: NttFriendly> Sub<&'a Polynomial<M>> for Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the - operator.

fn sub(self, other: &'a Polynomial<M>) -> Polynomial<M>

Performs the - operation.

impl<'a, M: NttFriendly> Sub<&'a StaticModInt<M>> for &'a Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the - operator.

fn sub(self, other: &'a StaticModInt<M>) -> Polynomial<M>

Performs the - operation.

impl<'a, M: NttFriendly> Sub<&'a StaticModInt<M>> for Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the - operator.

fn sub(self, other: &'a StaticModInt<M>) -> Polynomial<M>

Performs the - operation.

impl<'a, M: NttFriendly> Sub<Polynomial<M>> for &'a Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the - operator.

fn sub(self, other: Polynomial<M>) -> Polynomial<M>

Performs the - operation.

impl<M: NttFriendly> Sub<Polynomial<M>> for Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the - operator.

fn sub(self, other: Polynomial<M>) -> Polynomial<M>

Performs the - operation.

impl<'a, M: NttFriendly> Sub<StaticModInt<M>> for &'a Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the - operator.

fn sub(self, other: StaticModInt<M>) -> Polynomial<M>

Performs the - operation.

impl<M: NttFriendly> Sub<StaticModInt<M>> for Polynomial<M>

type Output = Polynomial<M>

The resulting type after applying the - operator.

fn sub(self, other: StaticModInt<M>) -> Polynomial<M>

Performs the - operation.

impl<'a, M: NttFriendly> SubAssign<&'a Polynomial<M>> for Polynomial<M>

fn sub_assign(&mut self, other: &'a Polynomial<M>)

Performs the -= operation.

impl<'a, M: NttFriendly> SubAssign<&'a StaticModInt<M>> for Polynomial<M>

fn sub_assign(&mut self, other: &'a StaticModInt<M>)

Performs the -= operation.

impl<M: NttFriendly> SubAssign<Polynomial<M>> for Polynomial<M>

fn sub_assign(&mut self, other: Polynomial<M>)

Performs the -= operation.

impl<M: NttFriendly> SubAssign<StaticModInt<M>> for Polynomial<M>

fn sub_assign(&mut self, other: StaticModInt<M>)

Performs the -= operation.

impl<M: Eq + NttFriendly> Eq for Polynomial<M>

impl<M: NttFriendly> StructuralEq for Polynomial<M>

impl<M: NttFriendly> StructuralPartialEq for Polynomial<M>