Struct rug_polynomial::ModPoly

pub struct ModPoly { /* fields omitted */ }

Implementations

impl ModPoly

pub fn new(modulus: Integer) -> Self

A new polynomial, equal to zero.

pub fn with_capacity(modulus: Integer, n: usize) -> Self

A new polynomial, equal to zero, with room for n coefficients.

pub fn interpolate_from_mul_subgroup(
    ys: Vec<Integer>,
    m: Integer,
    w: &Integer
) -> Self

Interpolate a polynomial which agrees with the given values over a multiplicative subgroup of the prime field with modulus m.

Let n be a power of two and the order of the multiplicative subgroup generated by w modulo m. Let ys be a vector of values at 1, w, w^2, ...

Returns a polynomial f, such that for i in 0..n, f(w^i) = ys[i] mod m.

Panics

If n is not a power of two, or if w does not generate a subgroup of order n.

Examples

use rug_polynomial::*;
use rug::Integer;

let m = Integer::from(5);
let w = Integer::from(2);
let ys: Vec<Integer> = vec![2, 3, 0, 4].into_iter().map(Integer::from).collect();
let p = ModPoly::interpolate_from_mul_subgroup(ys, m, &w);
debug_assert_eq!(p.len(), 2);
debug_assert_eq!(p.get_coefficient(0), Integer::from(1));
debug_assert_eq!(p.get_coefficient(1), Integer::from(1));

pub fn with_roots(xs: impl IntoIterator<Item = Integer>, m: &Integer) -> Self

Returns the minimal-degree monic polynomial with the given roots.

Example

use rug_polynomial::*;
use rug::Integer;

let p = ModPoly::with_roots(vec![0, 1].into_iter().map(Integer::from), &Integer::from(5));
debug_assert_eq!(p.len(), 3);
debug_assert_eq!(p.get_coefficient(0), Integer::from(0));
debug_assert_eq!(p.get_coefficient(1), Integer::from(4));
debug_assert_eq!(p.get_coefficient(2), Integer::from(1));

pub fn reserve(&mut self, n: usize)

Reallocates the polynomial to have room for n coefficients. Truncates the polynomial if it has more than n coefficients.

pub fn modulus(&self) -> &Integer

Get the modulus of this polynomial.

pub fn get_coefficient(&self, i: usize) -> Integer

Get the ith coefficient

pub fn set_coefficient(&mut self, i: usize, c: &Integer)

Set the ith coefficient to be c

pub fn set_coefficient_ui(&mut self, i: usize, c: usize)

Set the ith coefficient to be c

pub fn len(&self) -> usize

The number of coefficients in the polynomial. One more than the degree.

pub fn neg(&mut self)

self = -self

pub fn add(&mut self, other: &Self)

self = self + other

pub fn sub(&mut self, other: &Self)

self = self - other

pub fn sub_from(&mut self, other: &Self)

self = other - self

pub fn mul(&mut self, other: &Self)

self = self * other

pub fn divrem(&self, other: &Self) -> (ModPoly, ModPoly)

Find q and r such that self = other * q + r and r has degree less than other.

Returns

(q, r)

pub fn div(&mut self, other: &Self)

self = self / other

pub fn div_from(&mut self, other: &Self)

self = other / self

pub fn rem(&mut self, other: &Self)

self = self % other

pub fn rem_from(&mut self, other: &Self)

self = other % self

pub fn sqr(&mut self)

self = self * self

Trait Implementations

impl<'_> Add<&'_ ModPoly> for ModPoly

type Output = ModPoly

The resulting type after applying the + operator.

fn add(self, rhs: &ModPoly) -> ModPoly

Performs the + operation.

impl Add<ModPoly> for ModPoly

type Output = ModPoly

The resulting type after applying the + operator.

fn add(self, rhs: ModPoly) -> ModPoly

Performs the + operation.

impl<'_> Add<ModPoly> for &'_ ModPoly

type Output = ModPoly

The resulting type after applying the + operator.

fn add(self, rhs: ModPoly) -> ModPoly

Performs the + operation.

impl<'_> AddAssign<&'_ ModPoly> for ModPoly

fn add_assign(&mut self, rhs: &ModPoly)

Performs the += operation.

impl AddAssign<ModPoly> for ModPoly

fn add_assign(&mut self, rhs: ModPoly)

Performs the += operation.

impl Clone for ModPoly

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for ModPoly

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

Formats the value using the given formatter.

impl Display for ModPoly

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

Formats the value using the given formatter.

impl<'_> Div<&'_ ModPoly> for ModPoly

type Output = ModPoly

The resulting type after applying the / operator.

fn div(self, rhs: &ModPoly) -> ModPoly

Performs the / operation.

impl Div<ModPoly> for ModPoly

type Output = ModPoly

The resulting type after applying the / operator.

fn div(self, rhs: ModPoly) -> ModPoly

Performs the / operation.

impl<'_> Div<ModPoly> for &'_ ModPoly

type Output = ModPoly

The resulting type after applying the / operator.

fn div(self, rhs: ModPoly) -> ModPoly

Performs the / operation.

impl<'_> DivAssign<&'_ ModPoly> for ModPoly

fn div_assign(&mut self, rhs: &ModPoly)

Performs the /= operation.

impl DivAssign<ModPoly> for ModPoly

fn div_assign(&mut self, rhs: ModPoly)

Performs the /= operation.

impl Drop for ModPoly

fn drop(&mut self)

Executes the destructor for this type.

impl Eq for ModPoly

impl<'_> Mul<&'_ ModPoly> for ModPoly

type Output = ModPoly

The resulting type after applying the * operator.

fn mul(self, rhs: &ModPoly) -> ModPoly

Performs the * operation.

impl Mul<ModPoly> for ModPoly

type Output = ModPoly

The resulting type after applying the * operator.

fn mul(self, rhs: ModPoly) -> ModPoly

Performs the * operation.

impl<'_> Mul<ModPoly> for &'_ ModPoly

type Output = ModPoly

The resulting type after applying the * operator.

fn mul(self, rhs: ModPoly) -> ModPoly

Performs the * operation.

impl<'_> MulAssign<&'_ ModPoly> for ModPoly

fn mul_assign(&mut self, rhs: &ModPoly)

Performs the *= operation.

impl MulAssign<ModPoly> for ModPoly

fn mul_assign(&mut self, rhs: ModPoly)

Performs the *= operation.

impl PartialEq<ModPoly> for ModPoly

fn eq(&self, other: &ModPoly) -> bool

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

#[must_use]fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl<'_> Rem<&'_ ModPoly> for ModPoly

type Output = ModPoly

The resulting type after applying the % operator.

fn rem(self, rhs: &ModPoly) -> ModPoly

Performs the % operation.

impl Rem<ModPoly> for ModPoly

type Output = ModPoly

The resulting type after applying the % operator.

fn rem(self, rhs: ModPoly) -> ModPoly

Performs the % operation.

impl<'_> Rem<ModPoly> for &'_ ModPoly

type Output = ModPoly

The resulting type after applying the % operator.

fn rem(self, rhs: ModPoly) -> ModPoly

Performs the % operation.

impl<'_> RemAssign<&'_ ModPoly> for ModPoly

fn rem_assign(&mut self, rhs: &ModPoly)

Performs the %= operation.

impl RemAssign<ModPoly> for ModPoly

fn rem_assign(&mut self, rhs: ModPoly)

Performs the %= operation.

impl<'_> Sub<&'_ ModPoly> for ModPoly

type Output = ModPoly

The resulting type after applying the - operator.

fn sub(self, rhs: &ModPoly) -> ModPoly

Performs the - operation.

impl Sub<ModPoly> for ModPoly

type Output = ModPoly

The resulting type after applying the - operator.

fn sub(self, rhs: ModPoly) -> ModPoly

Performs the - operation.

impl<'_> Sub<ModPoly> for &'_ ModPoly

type Output = ModPoly

The resulting type after applying the - operator.

fn sub(self, rhs: ModPoly) -> ModPoly

Performs the - operation.

impl<'_> SubAssign<&'_ ModPoly> for ModPoly

fn sub_assign(&mut self, rhs: &ModPoly)

Performs the -= operation.

impl SubAssign<ModPoly> for ModPoly

fn sub_assign(&mut self, rhs: ModPoly)

Performs the -= operation.