Struct PolynomialOperator

pub struct PolynomialOperator<'a, const P: u32, const PR: u32> { /* private fields */ }

多項式の演算を扱う。

Implementations

impl<'a, const P: u32, const PR: u32> PolynomialOperator<'a, P, PR>

pub fn new(ntt: &'a NTT<P, PR>) -> Self

NTT<P>を基にPolynomialOperator<P>を生成する。

pub fn mul_assign(&self, a: &mut Polynomial<P>, b: Polynomial<P>)

多項式aに多項式bを掛ける。

pub fn mul(&self, a: Polynomial<P>, b: Polynomial<P>) -> Polynomial<P>

多項式aと多項式bの積を返す。

pub fn sq(&self, a: Polynomial<P>) -> Polynomial<P>

多項式aの2乗を返す。

pub fn inv(&self, a: Polynomial<P>, n: usize) -> Polynomial<P>

pub fn div(&self, a: Polynomial<P>, b: Polynomial<P>) -> Polynomial<P>

多項式aの多項式bによる商を返す。

pub fn rem(&self, a: Polynomial<P>, b: Polynomial<P>) -> Polynomial<P>

多項式aの多項式bによる剰余を返す。

pub fn divrem( &self, a: Polynomial<P>, b: Polynomial<P>, ) -> (Polynomial<P>, Polynomial<P>)

多項式aの多項式bによる商と剰余を返す。

Trait Implementations

impl<const P: u32, const PR: u32> FpsExp for PolynomialOperator<'_, P, PR>

type Poly = Polynomial<P>

多項式の型

fn fps_exp(&self, f: Self::Poly) -> Result<Self::Poly, &'static str>

$f(x) = \sum_0^{n-1} a_ix^i$について、$\exp (f(x))$の先頭$n$項を求める。

impl<const P: u32, const PR: u32> FpsInv for PolynomialOperator<'_, P, PR>

type Poly = Polynomial<P>

多項式の型

fn fps_inv(&self, f: Self::Poly) -> Result<Self::Poly, &'static str>

$f(x) = \sum_0^{n-1} a_ix^i$について、$\frac{1}{f(x)}$の先頭$n$項を求める。

impl<const P: u32, const PR: u32> FpsLog for PolynomialOperator<'_, P, PR>

type Poly = Polynomial<P>

多項式の型

fn fps_log(&self, f: Self::Poly) -> Result<Self::Poly, &'static str>

$f(x) = \sum_0^{n-1} a_ix^i$について、$\log (f(x))$の先頭$n$項を求める。

impl<const P: u32, const PR: u32> FpsPow for PolynomialOperator<'_, P, PR>

type Poly = Polynomial<P>

多項式の型

fn fps_pow(&self, f: Self::Poly, m: u64) -> Result<Self::Poly, &'static str>

$f(x) = \sum_0^{n-1} a_ix^i$について、$(f(x))^m$の先頭$n$項を求める。

impl<const P: u32, const PR: u32> FpsSqrt for PolynomialOperator<'_, P, PR>

type Poly = Polynomial<P>

多項式の型

fn fps_sqrt(&self, f: Self::Poly) -> Result<Self::Poly, &'static str>

$f(x) = \sum_0^{n-1} a_ix^i$について、$\sqrt{f(x)}$の先頭$n$項を求める。

impl<const P: u32, const PR: u32> MultipointEval for PolynomialOperator<'_, P, PR>

type Poly = Polynomial<P>

多項式の型

type Value = ConstModInt<P>

多項式の係数の型

fn multipoint_eval( &self, a: Self::Poly, p: Vec<Self::Value>, ) -> Vec<Self::Value>

多項式の多点評価

impl<const P: u32, const PR: u32> TaylorShift for PolynomialOperator<'_, P, PR>

type Poly = Polynomial<P>

多項式の型

type Value = ConstModInt<P>

多項式の係数の型

fn taylor_shift(&self, p: Self::Poly, c: Self::Value) -> Self::Poly

多項式 p = $f(x) = a_0 + a_1x + \cdots + a_nx^n$に対して、
多項式 $f(x + c) = a_0 + a_1(x + c) + \cdots + a_n(x + c)^n = b_0 + b_0x + \cdots + b_nx^n$ を満たす、数列{$b_i$}を求める。