Struct dashu_int::modular::Modulo

pub struct Modulo<'a>(_);

Modular arithmetic.

Examples

let ring = ModuloRing::new(UBig::from(10000u32));
let x = ring.convert(12345);
let y = ring.convert(55443);
assert_eq!((x - y).residue(), UBig::from(6902u32));

Implementations

impl Modulo<'_>

pub fn residue(&self) -> UBig

Get the residue in range 0..n in an n-element ring.

Examples

let ring = ModuloRing::new(UBig::from(100u8));
let x = ring.convert(-1234);
assert_eq!(x.residue(), UBig::from(66u8));

impl<'a> Modulo<'a>

pub fn inv(&self) -> Option<Modulo<'a>>

Multiplicative inverse.

Examples

// A Mersenne prime.
let p = UBig::from(2u8).pow(127) - UBig::ONE;
let ring = ModuloRing::new(p.clone());
// Fermat's little theorem: a^(p-2) = a^-1 (mod p)
let a = ring.convert(123);
let ainv = a.clone().inv().unwrap();
assert_eq!(ainv, a.pow(&(p - UBig::from(2u8))));
assert_eq!((a * ainv).residue(), UBig::ONE);

impl<'a> Modulo<'a>

pub fn pow(&self, exp: &UBig) -> Modulo<'a>

Exponentiation.

If you want use a negative exponent, you can first use inv() to convert the base to its inverse, and then call this method.

Examples

// A Mersenne prime.
let p = UBig::from(2u8).pow(607) - UBig::ONE;
let ring = ModuloRing::new(p.clone());
// Fermat's little theorem: a^(p-1) = 1 (mod p)
let a = ring.convert(123);
assert_eq!(a.pow(&(p - UBig::ONE)), ring.convert(1));

Trait Implementations

impl<'a> Add<&Modulo<'a>> for &Modulo<'a>

type Output = Modulo<'a>

The resulting type after applying the + operator.

fn add(self, rhs: &Modulo<'a>) -> Modulo<'a>

Performs the + operation.

impl<'a> Add<&Modulo<'a>> for Modulo<'a>

type Output = Modulo<'a>

The resulting type after applying the + operator.

fn add(self, rhs: &Modulo<'a>) -> Modulo<'a>

Performs the + operation.

impl<'a> Add<Modulo<'a>> for &Modulo<'a>

type Output = Modulo<'a>

The resulting type after applying the + operator.

fn add(self, rhs: Modulo<'a>) -> Modulo<'a>

Performs the + operation.

impl<'a> Add<Modulo<'a>> for Modulo<'a>

type Output = Modulo<'a>

The resulting type after applying the + operator.

fn add(self, rhs: Modulo<'a>) -> Modulo<'a>

Performs the + operation.

impl<'a> AddAssign<&Modulo<'a>> for Modulo<'a>

fn add_assign(&mut self, rhs: &Modulo<'a>)

Performs the += operation.

impl<'a> AddAssign<Modulo<'a>> for Modulo<'a>

fn add_assign(&mut self, rhs: Modulo<'a>)

Performs the += operation.

impl Binary for Modulo<'_>

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

Formats the value using the given formatter.

impl Clone for Modulo<'_>

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 Modulo<'_>

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

Formats the value using the given formatter.

impl Display for Modulo<'_>

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

Formats the value using the given formatter.

impl<'a> Div<&Modulo<'a>> for &Modulo<'a>

type Output = Modulo<'a>

The resulting type after applying the / operator.

fn div(self, rhs: &Modulo<'a>) -> Modulo<'a>

Performs the / operation.

impl<'a> Div<&Modulo<'a>> for Modulo<'a>

type Output = Modulo<'a>

The resulting type after applying the / operator.

fn div(self, rhs: &Modulo<'a>) -> Modulo<'a>

Performs the / operation.

impl<'a> Div<Modulo<'a>> for &Modulo<'a>

type Output = Modulo<'a>

The resulting type after applying the / operator.

fn div(self, rhs: Modulo<'a>) -> Modulo<'a>

Performs the / operation.

impl<'a> Div<Modulo<'a>> for Modulo<'a>

type Output = Modulo<'a>

The resulting type after applying the / operator.

fn div(self, rhs: Modulo<'a>) -> Modulo<'a>

Performs the / operation.

impl<'a> DivAssign<&Modulo<'a>> for Modulo<'a>

fn div_assign(&mut self, rhs: &Modulo<'a>)

Performs the /= operation.

impl<'a> DivAssign<Modulo<'a>> for Modulo<'a>

fn div_assign(&mut self, rhs: Modulo<'a>)

Performs the /= operation.

impl LowerHex for Modulo<'_>

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

Formats the value using the given formatter.

impl<'a> Mul<&Modulo<'a>> for &Modulo<'a>

type Output = Modulo<'a>

The resulting type after applying the * operator.

fn mul(self, rhs: &Modulo<'a>) -> Modulo<'a>

Performs the * operation.

impl<'a> Mul<&Modulo<'a>> for Modulo<'a>

type Output = Modulo<'a>

The resulting type after applying the * operator.

fn mul(self, rhs: &Modulo<'a>) -> Modulo<'a>

Performs the * operation.

impl<'a> Mul<Modulo<'a>> for &Modulo<'a>

type Output = Modulo<'a>

The resulting type after applying the * operator.

fn mul(self, rhs: Modulo<'a>) -> Modulo<'a>

Performs the * operation.

impl<'a> Mul<Modulo<'a>> for Modulo<'a>

type Output = Modulo<'a>

The resulting type after applying the * operator.

fn mul(self, rhs: Modulo<'a>) -> Modulo<'a>

Performs the * operation.

impl<'a> MulAssign<&Modulo<'a>> for Modulo<'a>

fn mul_assign(&mut self, rhs: &Modulo<'a>)

Performs the *= operation.

impl<'a> MulAssign<Modulo<'a>> for Modulo<'a>

fn mul_assign(&mut self, rhs: Modulo<'a>)

Performs the *= operation.

impl<'a> Neg for &Modulo<'a>

type Output = Modulo<'a>

The resulting type after applying the - operator.

fn neg(self) -> Modulo<'a>

Performs the unary - operation.

impl<'a> Neg for Modulo<'a>

type Output = Modulo<'a>

The resulting type after applying the - operator.

fn neg(self) -> Modulo<'a>

Performs the unary - operation.

impl Octal for Modulo<'_>

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

Formats the value using the given formatter.

impl PartialEq<Modulo<'_>> for Modulo<'_>

Equality within a ring.

Panics

Panics if the two values are from different rings.

fn eq(&self, other: &Self) -> 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> Sub<&Modulo<'a>> for &Modulo<'a>

type Output = Modulo<'a>

The resulting type after applying the - operator.

fn sub(self, rhs: &Modulo<'a>) -> Modulo<'a>

Performs the - operation.

impl<'a> Sub<&Modulo<'a>> for Modulo<'a>

type Output = Modulo<'a>

The resulting type after applying the - operator.

fn sub(self, rhs: &Modulo<'a>) -> Modulo<'a>

Performs the - operation.

impl<'a> Sub<Modulo<'a>> for &Modulo<'a>

type Output = Modulo<'a>

The resulting type after applying the - operator.

fn sub(self, rhs: Modulo<'a>) -> Modulo<'a>

Performs the - operation.

impl<'a> Sub<Modulo<'a>> for Modulo<'a>

type Output = Modulo<'a>

The resulting type after applying the - operator.

fn sub(self, rhs: Modulo<'a>) -> Modulo<'a>

Performs the - operation.

impl<'a> SubAssign<&Modulo<'a>> for Modulo<'a>

fn sub_assign(&mut self, rhs: &Modulo<'a>)

Performs the -= operation.

impl<'a> SubAssign<Modulo<'a>> for Modulo<'a>

fn sub_assign(&mut self, rhs: Modulo<'a>)

Performs the -= operation.

impl UpperHex for Modulo<'_>

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

Formats the value using the given formatter.

impl Eq for Modulo<'_>