Struct dashu_int::modular::Reduced

pub struct Reduced<'a>(/* private fields */);

Modular arithmetic.

Examples

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

Implementations

impl<'a> Reduced<'a>

pub fn dbl(self) -> Self

Calculate 2*target mod m in reduced form

Examples

let p = UBig::from(0x1234u16);
let ring = ConstDivisor::new(p.clone());
let a = ring.reduce(4000);
assert_eq!(a.dbl(), ring.reduce(4000 + 4000));

impl Reduced<'_>

pub fn residue(&self) -> UBig

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

Examples

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

pub fn modulus(&self) -> UBig

Get the modulus of the ring that this element belongs to.

impl<'a> Reduced<'a>

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

Multiplicative inverse.

Examples

// A Mersenne prime.
let p = UBig::from(2u8).pow(127) - UBig::ONE;
let ring = ConstDivisor::new(p.clone());
// Fermat's little theorem: a^(p-2) = a^-1 (mod p)
let a = ring.reduce(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> Reduced<'a>

pub fn sqr(&self) -> Self

Calculate target^2 mod m in reduced form

Examples

let p = UBig::from(0x1234u16);
let ring = ConstDivisor::new(p.clone());
let a = ring.reduce(4000);
assert_eq!(a.sqr(), ring.reduce(4000 * 4000));

impl<'a> Reduced<'a>

pub fn pow(&self, exp: &UBig) -> Reduced<'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 = ConstDivisor::new(p.clone());
// Fermat's little theorem: a^(p-1) = 1 (mod p)
let a = ring.reduce(123);
assert_eq!(a.pow(&(p - UBig::ONE)), ring.reduce(1));

Trait Implementations

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

type Output = Reduced<'a>

The resulting type after applying the + operator.

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

Performs the + operation.

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

type Output = Reduced<'a>

The resulting type after applying the + operator.

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

Performs the + operation.

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

type Output = Reduced<'a>

The resulting type after applying the + operator.

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

Performs the + operation.

impl<'a> Add<Reduced<'a>> for Reduced<'a>

type Output = Reduced<'a>

The resulting type after applying the + operator.

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

Performs the + operation.

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

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

Performs the += operation.

impl<'a> AddAssign<Reduced<'a>> for Reduced<'a>

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

Performs the += operation.

impl Binary for Reduced<'_>

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

Formats the value using the given formatter.

impl Clone for Reduced<'_>

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

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

Formats the value using the given formatter.

impl Display for Reduced<'_>

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

Formats the value using the given formatter.

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

type Output = Reduced<'a>

The resulting type after applying the / operator.

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

Performs the / operation.

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

type Output = Reduced<'a>

The resulting type after applying the / operator.

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

Performs the / operation.

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

type Output = Reduced<'a>

The resulting type after applying the / operator.

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

Performs the / operation.

impl<'a> Div<Reduced<'a>> for Reduced<'a>

type Output = Reduced<'a>

The resulting type after applying the / operator.

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

Performs the / operation.

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

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

Performs the /= operation.

impl<'a> DivAssign<Reduced<'a>> for Reduced<'a>

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

Performs the /= operation.

impl LowerHex for Reduced<'_>

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

Formats the value using the given formatter.

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

type Output = Reduced<'a>

The resulting type after applying the * operator.

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

Performs the * operation.

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

type Output = Reduced<'a>

The resulting type after applying the * operator.

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

Performs the * operation.

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

type Output = Reduced<'a>

The resulting type after applying the * operator.

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

Performs the * operation.

impl<'a> Mul<Reduced<'a>> for Reduced<'a>

type Output = Reduced<'a>

The resulting type after applying the * operator.

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

Performs the * operation.

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

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

Performs the *= operation.

impl<'a> MulAssign<Reduced<'a>> for Reduced<'a>

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

Performs the *= operation.

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

type Output = Reduced<'a>

The resulting type after applying the - operator.

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

Performs the unary - operation.

impl<'a> Neg for Reduced<'a>

type Output = Reduced<'a>

The resulting type after applying the - operator.

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

Performs the unary - operation.

impl Octal for Reduced<'_>

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

Formats the value using the given formatter.

impl PartialEq<Reduced<'_>> for Reduced<'_>

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<&Reduced<'a>> for &Reduced<'a>

type Output = Reduced<'a>

The resulting type after applying the - operator.

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

Performs the - operation.

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

type Output = Reduced<'a>

The resulting type after applying the - operator.

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

Performs the - operation.

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

type Output = Reduced<'a>

The resulting type after applying the - operator.

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

Performs the - operation.

impl<'a> Sub<Reduced<'a>> for Reduced<'a>

type Output = Reduced<'a>

The resulting type after applying the - operator.

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

Performs the - operation.

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

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

Performs the -= operation.

impl<'a> SubAssign<Reduced<'a>> for Reduced<'a>

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

Performs the -= operation.

impl UpperHex for Reduced<'_>

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

Formats the value using the given formatter.

impl Eq for Reduced<'_>