Struct libbgs::numbers::FpNum

pub struct FpNum<const P: u128>(_);

An integer modulo P.

Example

use libbgs::numbers::FpNum;
let x = FpNum::<7>::from(5);
let y = FpNum::<7>::from(6);
let z = x * y;
assert_eq!(z, FpNum::from(30 % 7));

For more informtion on the internal representation, see: Montgomery, Peter (April 1985). “Modular Multiplication Without Trial Division”. Mathematics of Computation. 44 (170): 519-521.

Implementations

impl<const P: u128> FpNum<P>

pub const ZERO: FpNum<P> = _

The constant 0.

pub const TWO_INV: FpNum<P> = _

The constant $2^{-1}$.

pub const fn legendre(&self) -> FpNum<P>

Returns the Legendre symbol of a modulo P, i.e., $$\left(\frac{a}{p}\right)_L = a^{\frac{p - 1}{2}} \mod p$$.

pub const fn int_sqrt(&self) -> Option<FpNum<P>>

Calculates this number’s square root, if it is a quadratic residue; otherwise, returns None.

pub const fn find_nonresidue() -> FpNum<P>

Returns a quadratic nonresidue modulo p.

pub const fn raw(&self) -> u128

Returns the Montgomery representation of this number.

Trait Implementations

impl<const P: u128> Add<&FpNum<P>> for &FpNum<P>

type Output = FpNum<P>

The resulting type after applying the + operator.

fn add(self, rhs: &FpNum<P>) -> FpNum<P>

Performs the + operation.

impl<const P: u128> Add<&FpNum<P>> for FpNum<P>

type Output = FpNum<P>

The resulting type after applying the + operator.

fn add(self, rhs: &FpNum<P>) -> FpNum<P>

Performs the + operation.

impl<const P: u128> Add<FpNum<P>> for &FpNum<P>

type Output = FpNum<P>

The resulting type after applying the + operator.

fn add(self, rhs: FpNum<P>) -> FpNum<P>

Performs the + operation.

impl<const P: u128> Add<FpNum<P>> for FpNum<P>

type Output = FpNum<P>

The resulting type after applying the + operator.

fn add(self, rhs: FpNum<P>) -> FpNum<P>

Performs the + operation.

impl<const P: u128> Clone for FpNum<P>

fn clone(&self) -> FpNum<P>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<const P: u128> Debug for FpNum<P>

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

Formats the value using the given formatter.

impl<const P: u128> From<FpNum<P>> for QuadNum<P>

fn from(value: FpNum<P>) -> QuadNum<P>

Converts to this type from the input type.

impl<const P: u128> From<FpNum<P>> for u128

fn from(src: FpNum<P>) -> u128

Converts to this type from the input type.

impl<const P: u128> From<u128> for FpNum<P>

fn from(src: u128) -> FpNum<P>

Converts to this type from the input type.

impl<S, const P: u128> FromChi<S, P> for FpNum<P>where FpNum<P>: Factor<S>,

fn from_chi<const L: usize>( chi: &SylowElem<S, L, FpNum<P>>, decomp: &SylowDecomp<S, L, FpNum<P>> ) -> FpNum<P>

Returns $\chi + \chi^{-1}$.

fn from_chi_conj<const L: usize>( chi: &SylowElem<S, L, FpNum<P>>, decomp: &SylowDecomp<S, L, FpNum<P>> ) -> FpNum<P>

Returns $\chi - \chi^{-1}$.

impl<const P: u128> GroupElem for FpNum<P>

const ONE: Self = _

The unique identity element of this group.

const SIZE: u128 = _

The size of the group this element belongs to.

fn multiply(&self, other: &FpNum<P>) -> FpNum<P>

Returns the product of two elements under the group binary operator. If you implement this trait, you must guarantee that the operation is associative; that is, a.multiply(b.multiply(c)) == a.multiply(b).multiply(c).

fn inverse(&self) -> FpNum<P>

Returns the multiplicative inverse of this element. If you implement this trait, you must guarantee x.inverse().multiply(x) and x.multiply(x.inverse()) both evaluate to ONE.

const ONE_256: [Self; 256] = _

👎Deprecated: To be replaced by inline const expressions once stabilized.

! 256 copies of Self::ONE in an array.

fn pow(&self, n: u128) -> Self

Raises this element to the power of n.

fn order<S>(&self) -> u128where Self: Factor<S>,

Returns the order of this element, that is, the smallest positive power p for which a.pow(p).is_one() returns True.

impl<const P: u128> Hash for FpNum<P>

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<const P: u128> Mul<&FpNum<P>> for &FpNum<P>

type Output = FpNum<P>

The resulting type after applying the * operator.

fn mul(self, rhs: &FpNum<P>) -> FpNum<P>

Performs the * operation.

impl<const P: u128> Mul<&FpNum<P>> for FpNum<P>

type Output = FpNum<P>

The resulting type after applying the * operator.

fn mul(self, rhs: &FpNum<P>) -> FpNum<P>

Performs the * operation.

impl<const P: u128> Mul<FpNum<P>> for &FpNum<P>

type Output = FpNum<P>

The resulting type after applying the * operator.

fn mul(self, rhs: FpNum<P>) -> FpNum<P>

Performs the * operation.

impl<const P: u128> Mul<FpNum<P>> for FpNum<P>

type Output = FpNum<P>

The resulting type after applying the * operator.

fn mul(self, rhs: FpNum<P>) -> FpNum<P>

Performs the * operation.

impl<const P: u128> Mul<FpNum<P>> for u128

type Output = FpNum<P>

The resulting type after applying the * operator.

fn mul(self, rhs: FpNum<P>) -> FpNum<P>

Performs the * operation.

impl<const P: u128> MulAssign<FpNum<P>> for FpNum<P>

fn mul_assign(&mut self, rhs: FpNum<P>)

Performs the *= operation.

impl<const P: u128> Neg for &FpNum<P>

type Output = FpNum<P>

The resulting type after applying the - operator.

fn neg(self) -> FpNum<P>

Performs the unary - operation.

impl<const P: u128> Neg for FpNum<P>

type Output = FpNum<P>

The resulting type after applying the - operator.

fn neg(self) -> FpNum<P>

Performs the unary - operation.

impl<const P: u128> PartialEq<FpNum<P>> for FpNum<P>

fn eq(&self, other: &FpNum<P>) -> 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<const P: u128> Sub<&FpNum<P>> for &FpNum<P>

type Output = FpNum<P>

The resulting type after applying the - operator.

fn sub(self, rhs: &FpNum<P>) -> FpNum<P>

Performs the - operation.

impl<const P: u128> Sub<&FpNum<P>> for FpNum<P>

type Output = FpNum<P>

The resulting type after applying the - operator.

fn sub(self, rhs: &FpNum<P>) -> FpNum<P>

Performs the - operation.

impl<const P: u128> Sub<FpNum<P>> for &FpNum<P>

type Output = FpNum<P>

The resulting type after applying the - operator.

fn sub(self, rhs: FpNum<P>) -> FpNum<P>

Performs the - operation.

impl<const P: u128> Sub<FpNum<P>> for FpNum<P>

type Output = FpNum<P>

The resulting type after applying the - operator.

fn sub(self, rhs: FpNum<P>) -> FpNum<P>

Performs the - operation.

impl<S, const P: u128> SylowDecomposable<S> for FpNum<P>where FpNum<P>: Factor<S>,

fn find_sylow_generator(i: usize) -> FpNum<P>

Finds a Sylow generator for the Sylow subgroup of prime power index i.

fn is_sylow_generator(candidate: &Self, d: (u128, usize)) -> Option<Self>

True if the given element is a generator of the Sylow subgroup of the prime power represented by d.

fn count_elements_of_order(ds: &[usize]) -> u128

Returns the number of elements of a particular order. The argument is the powers of the prime factors of the group’s order.

impl<const P: u128> Copy for FpNum<P>

impl<const P: u128> Eq for FpNum<P>

impl<const P: u128> StructuralEq for FpNum<P>

impl<const P: u128> StructuralPartialEq for FpNum<P>