Struct ModPoly 

pub struct ModPoly { /* private fields */ }

A polynomial with modular integer coefficients.

That is, a member of Z/nZ[X].

Examples

See constructors:

• new
• interpolate_from_mul_subgroup

Implementations

impl ModPoly

pub fn new(modulus: Integer) -> Self

A new polynomial, equal to zero.

pub fn from_int(modulus: Integer, constant: Integer) -> Self

A new polynomial, equal to constant.

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 evaluate_over_mul_subgroup(&self, w: &Integer, n: usize) -> Vec<Integer>

Evaluate this polynomial over the multiplicative subgroup generated by w, of size n.

Returns list of evaluations, over {1, w, w^2, ... w^(2^n-1)}.

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 mut p = ModPoly::new(m);
p.set_coefficient_ui(0, 1);
p.set_coefficient_ui(1, 1);
let vs = p.evaluate_over_mul_subgroup(&Integer::from(2), 4);
let vs: Vec<usize> = vs.into_iter().map(|i| i.to_usize().unwrap()).collect();
debug_assert_eq!(vs, vec![2, 3, 0, 4]);

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 evaluate(&self, i: &Integer) -> Integer

Evaluate the polynomial at the given input.

Example

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

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

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

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

From (a, b), returns (g, s, t) such that g | a, g | b and g = a*s + b*t.

pub fn derivative(&self) -> Self

Give the formal derivative of 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<Integer> for ModPoly

type Output = ModPoly

The resulting type after applying the + operator.

fn add(self, rhs: Integer) -> 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 Integer

type Output = ModPoly

The resulting type after applying the + operator.

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

Performs the + operation.

impl Add 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<Integer> for ModPoly

fn add_assign(&mut self, rhs: Integer)

Performs the += operation.

impl AddAssign for ModPoly

fn add_assign(&mut self, rhs: ModPoly)

Performs the += operation.

impl Clone for ModPoly

fn clone(&self) -> Self

Returns a duplicate 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<'de> Deserialize<'de> for ModPoly

fn deserialize<D>(deserializer: D) -> Result<ModPoly, D::Error>

where D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

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<Integer> for ModPoly

type Output = ModPoly

The resulting type after applying the / operator.

fn div(self, rhs: Integer) -> 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 Integer

type Output = ModPoly

The resulting type after applying the / operator.

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

Performs the / operation.

impl Div 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<Integer> for ModPoly

fn div_assign(&mut self, rhs: Integer)

Performs the /= operation.

impl DivAssign 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 From<&ModPoly> for ModPolySer

fn from(other: &ModPoly) -> ModPolySer

Converts to this type from the input type.

impl From<ModPolySer> for ModPoly

fn from(other: ModPolySer) -> ModPoly

Converts to this type from the input type.

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<Integer> for ModPoly

type Output = ModPoly

The resulting type after applying the * operator.

fn mul(self, rhs: Integer) -> 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 Integer

type Output = ModPoly

The resulting type after applying the * operator.

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

Performs the * operation.

impl Mul 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<Integer> for ModPoly

fn mul_assign(&mut self, rhs: Integer)

Performs the *= operation.

impl MulAssign for ModPoly

fn mul_assign(&mut self, rhs: ModPoly)

Performs the *= operation.

impl PartialEq for ModPoly

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

Tests for self and other values to be equal, and is used by ==.

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

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

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<Integer> for ModPoly

type Output = ModPoly

The resulting type after applying the % operator.

fn rem(self, rhs: Integer) -> 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 Integer

type Output = ModPoly

The resulting type after applying the % operator.

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

Performs the % operation.

impl Rem 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<Integer> for ModPoly

fn rem_assign(&mut self, rhs: Integer)

Performs the %= operation.

impl RemAssign for ModPoly

fn rem_assign(&mut self, rhs: ModPoly)

Performs the %= operation.

impl Serialize for ModPoly

fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>

where S: Serializer,

Serialize this value into the given Serde serializer.

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<Integer> for ModPoly

type Output = ModPoly

The resulting type after applying the - operator.

fn sub(self, rhs: Integer) -> 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 Integer

type Output = ModPoly

The resulting type after applying the - operator.

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

Performs the - operation.

impl Sub 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<Integer> for ModPoly

fn sub_assign(&mut self, rhs: Integer)

Performs the -= operation.

impl SubAssign for ModPoly

fn sub_assign(&mut self, rhs: ModPoly)

Performs the -= operation.

impl Eq for ModPoly