Struct MPZBase

pub struct MPZBase;

Available on crate feature mpir only.

Arbitrary-precision integer ring, implemented by binding to the well-known and heavily optimized library mpir (fork of gmp).

Implementations

impl MPZBase

pub fn from_base_u64_repr(&self, dst: &mut MPZEl, input: &[u64])

pub fn abs_base_u64_repr_len(&self, src: &MPZEl) -> usize

pub fn abs_base_u64_repr(&self, src: &MPZEl, out: &mut [u64])

Trait Implementations

impl Clone for MPZBase

fn clone(&self) -> MPZBase

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for MPZBase

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

Formats the value using the given formatter.

impl Default for MPZBase

fn default() -> Self

Returns the “default value” for a type.

impl DivisibilityRing for MPZBase

fn checked_left_div( &self, lhs: &Self::Element, rhs: &Self::Element, ) -> Option<Self::Element>

Checks whether there is an element x such that rhs * x = lhs, and returns it if it exists.

fn balance_factor<'a, I>(&self, elements: I) -> Option<Self::Element>

where I: Iterator<Item = &'a Self::Element>, Self: 'a,

Function that computes a “balancing” factor of a sequence of ring elements. The only use of the balancing factor is to increase performance, in particular, dividing all elements in the sequence by this factor should make them “smaller” resp. cheaper to process.

type PreparedDivisorData = ()

Additional data associated to a fixed ring element that can be used to speed up division by this ring element.

fn divides_left(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool

Returns whether there is an element x such that rhs * x = lhs. If you need such an element, consider using DivisibilityRing::checked_left_div().

fn divides(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool

Same as DivisibilityRing::divides_left(), but requires a commutative ring.

fn checked_div( &self, lhs: &Self::Element, rhs: &Self::Element, ) -> Option<Self::Element>

Same as DivisibilityRing::checked_left_div(), but requires a commutative ring.

fn is_unit(&self, x: &Self::Element) -> bool

Returns whether the given element is a unit, i.e. has an inverse.

fn prepare_divisor(&self, x: Self::Element) -> PreparedDivisor<Self>

“Prepares” an element of this ring for division.

fn checked_left_div_prepared( &self, lhs: &Self::Element, rhs: &PreparedDivisor<Self>, ) -> Option<Self::Element>

Same as DivisibilityRing::checked_left_div() but for a prepared divisor.

fn divides_left_prepared( &self, lhs: &Self::Element, rhs: &PreparedDivisor<Self>, ) -> bool

Same as DivisibilityRing::divides_left() but for a prepared divisor.

fn is_unit_prepared(&self, x: &PreparedDivisor<Self>) -> bool

Same as DivisibilityRing::is_unit() but for a prepared divisor.

fn invert(&self, el: &Self::Element) -> Option<Self::Element>

If the given element is a unit, returns its inverse, otherwise None.

impl EuclideanRing for MPZBase

fn euclidean_div_rem( &self, lhs: Self::Element, rhs: &Self::Element, ) -> (Self::Element, Self::Element)

Computes euclidean division with remainder.

fn euclidean_rem( &self, lhs: Self::Element, rhs: &Self::Element, ) -> Self::Element

Computes only the remainder of euclidean division.

fn euclidean_div( &self, lhs: Self::Element, rhs: &Self::Element, ) -> Self::Element

Computes euclidean division without remainder.

fn euclidean_deg(&self, val: &Self::Element) -> Option<usize>

Defines how “small” an element is. For details, see EuclideanRing.

impl FiniteRingSpecializable for MPZBase

fn specialize<O: FiniteRingOperation<Self>>(_op: O) -> Result<O::Output, ()>

fn is_finite_ring() -> bool

impl HashableElRing for MPZBase

fn hash<H: Hasher>(&self, el: &Self::Element, h: &mut H)

Hashes the given ring element.

impl IntCast<MPZBase> for MPZBase

fn cast(&self, _from: &MPZBase, el: MPZEl) -> MPZEl

Maps the given integer into this ring.

impl IntCast<MPZBase> for RustBigintRingBase

fn cast(&self, from: &MPZBase, el: MPZEl) -> RustBigint

Maps the given integer into this ring.

impl IntCast<MPZBase> for StaticRingBase<i128>

fn cast(&self, from: &MPZBase, el: MPZEl) -> i128

Maps the given integer into this ring.

impl IntCast<MPZBase> for StaticRingBase<i16>

fn cast(&self, _: &MPZBase, el: MPZEl) -> i16

Maps the given integer into this ring.

impl IntCast<MPZBase> for StaticRingBase<i32>

fn cast(&self, _: &MPZBase, el: MPZEl) -> i32

Maps the given integer into this ring.

impl IntCast<MPZBase> for StaticRingBase<i64>

fn cast(&self, from: &MPZBase, el: MPZEl) -> i64

Maps the given integer into this ring.

impl IntCast<MPZBase> for StaticRingBase<i8>

fn cast(&self, _: &MPZBase, el: MPZEl) -> i8

Maps the given integer into this ring.

impl IntCast<RustBigintRingBase> for MPZBase

fn cast(&self, _: &RustBigintRingBase, el: RustBigint) -> Self::Element

Maps the given integer into this ring.

impl IntCast<StaticRingBase<i128>> for MPZBase

fn cast(&self, _: &StaticRingBase<i128>, el: i128) -> MPZEl

Maps the given integer into this ring.

impl IntCast<StaticRingBase<i16>> for MPZBase

fn cast(&self, _: &StaticRingBase<i16>, el: i16) -> MPZEl

Maps the given integer into this ring.

impl IntCast<StaticRingBase<i32>> for MPZBase

fn cast(&self, _: &StaticRingBase<i32>, el: i32) -> MPZEl

Maps the given integer into this ring.

impl IntCast<StaticRingBase<i64>> for MPZBase

fn cast(&self, _: &StaticRingBase<i64>, el: i64) -> Self::Element

Maps the given integer into this ring.

impl IntCast<StaticRingBase<i8>> for MPZBase

fn cast(&self, _: &StaticRingBase<i8>, el: i8) -> MPZEl

Maps the given integer into this ring.

impl IntegerPolyGCDRing for MPZBase

type LocalRingAsZnBase<'ring> = <MPZBase as PolyGCDLocallyDomain>::LocalRingBase<'ring> where Self: 'ring

It would be much preferrable if we could restrict associated types from supertraits, this is just a workaround (and an ugly one at that)

type LocalRingAsZn<'ring> = <MPZBase as PolyGCDLocallyDomain>::LocalRing<'ring> where Self: 'ring

fn local_ring_as_zn<'a, 'ring>( &self, local_field: &'a Self::LocalRing<'ring>, ) -> &'a Self::LocalRingAsZn<'ring>

where Self: 'ring,

fn principal_ideal_generator<'ring>( &self, p: &Self::SuitableIdeal<'ring>, ) -> i64

where Self: 'ring,

impl IntegerRing for MPZBase

fn to_float_approx(&self, el: &Self::Element) -> f64

Computes a float value that is “close” to the given integer.

fn from_float_approx(&self, el: f64) -> Option<Self::Element>

Computes a value that is “close” to the given float. However, no guarantees are made on the definition of close, in particular, this does not have to be the closest integer to the given float, and cannot be used to compute rounding. It is also implementation-defined when to return None, although this is usually the case on infinity and NaN.

fn mul_pow_2(&self, el: &mut Self::Element, power: usize)

Multiplies the element by a power of two.

fn euclidean_div_pow_2(&self, el: &mut Self::Element, power: usize)

Computes the euclidean division by a power of two, always rounding to zero (note that euclidean division requires that |remainder| < |divisor|, and thus would otherwise leave multiple possible results).

fn abs_is_bit_set(&self, el: &Self::Element, bit: usize) -> bool

Return whether the i-th bit in the two-complements representation of abs(value) is 1.

fn abs_highest_set_bit(&self, value: &Self::Element) -> Option<usize>

Returns the index of the highest set bit in the two-complements representation of abs(value), or None if the value is zero.

fn abs_lowest_set_bit(&self, value: &Self::Element) -> Option<usize>

Returns the index of the lowest set bit in the two-complements representation of abs(value), or None if the value is zero.

fn rounded_div(&self, lhs: Self::Element, rhs: &Self::Element) -> Self::Element

Computes the rounded division, i.e. rounding to the closest integer. In the case of a tie (i.e. round(0.5)), we round towards +/- infinity.

fn get_uniformly_random_bits<G: FnMut() -> u64>( &self, log2_bound_exclusive: usize, rng: G, ) -> Self::Element

Computes a uniformly random integer in [0, 2^log_bound_exclusive - 1], assuming that rng provides uniformly random values in the whole range of u64.

fn representable_bits(&self) -> Option<usize>

Returns n such that this ring can represent at least [-2^n, ..., 2^n - 1]. Returning None means that the size of representable integers is unbounded.

fn ceil_div(&self, lhs: Self::Element, rhs: &Self::Element) -> Self::Element

Computes the division lhs / rhs, rounding towards + infinity.

fn floor_div(&self, lhs: Self::Element, rhs: &Self::Element) -> Self::Element

Computes the division lhs / rhs, rounding towards - infinity.

fn power_of_two(&self, power: usize) -> Self::Element

Returns the value 2^power in this integer ring.

impl OrderedRing for MPZBase

fn cmp(&self, lhs: &Self::Element, rhs: &Self::Element) -> Ordering

Returns whether lhs is Ordering::Less, Ordering::Equal or Ordering::Greater than rhs.

fn is_neg(&self, value: &Self::Element) -> bool

Returns whether value < 0.

fn abs_cmp(&self, lhs: &Self::Element, rhs: &Self::Element) -> Ordering

Returns whether abs(lhs) is Ordering::Less, Ordering::Equal or Ordering::Greater than abs(rhs).

fn is_leq(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool

Returns whether lhs <= rhs.

fn is_geq(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool

Returns whether lhs >= rhs.

fn is_lt(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool

Returns whether lhs < rhs.

fn is_gt(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool

Returns whether lhs > rhs.

fn is_pos(&self, value: &Self::Element) -> bool

Returns whether value > 0.

fn abs(&self, value: Self::Element) -> Self::Element

Returns the absolute value of value, i.e. value if value >= 0 and -value otherwise.

fn max<'a>( &self, fst: &'a Self::Element, snd: &'a Self::Element, ) -> &'a Self::Element

Returns the larger one of fst and snd.

impl PartialEq for MPZBase

fn eq(&self, other: &MPZBase) -> 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 PolyGCDLocallyDomain for MPZBase

type LocalRing<'ring> = RingValue<ZnBase<RingValue<MPZBase>>> where Self: 'ring

type LocalRingBase<'ring> = ZnBase<RingValue<MPZBase>> where Self: 'ring

The proper way would be to define this with two lifetime parameters 'ring and 'data, see also crate::compute_locally::EvaluatePolyLocallyRing::LocalRingBase

type LocalFieldBase<'ring> = AsFieldBase<RingValue<ZnBase>> where Self: 'ring

type LocalField<'ring> = RingValue<AsFieldBase<RingValue<ZnBase>>> where Self: 'ring

type SuitableIdeal<'ring> = i64 where Self: 'ring

fn reconstruct_ring_el<'local, 'element, 'ring, V1, V2>( &self, _p: &Self::SuitableIdeal<'ring>, from: V1, _e: usize, x: V2, ) -> Self::Element

where Self: 'ring, V1: VectorFn<&'local Self::LocalRing<'ring>>, V2: VectorFn<&'element El<Self::LocalRing<'ring>>>,

Computes a “small” element x in R such that x mod mi^e is equal to the given value, for every maximal ideal mi over I. In cases where the factors of polynomials in R[X] do not necessarily have coefficients in R, this function might have to do rational reconstruction.

fn maximal_ideal_factor_count<'ring>( &self, _p: &Self::SuitableIdeal<'ring>, ) -> usize

where Self: 'ring,

fn lift_partial<'ring>( &self, _p: &Self::SuitableIdeal<'ring>, from: (&Self::LocalRing<'ring>, usize), to: (&Self::LocalRing<'ring>, usize), max_ideal_idx: usize, x: El<Self::LocalRing<'ring>>, ) -> El<Self::LocalRing<'ring>>

where Self: 'ring,

Computes any element y in R / mi^to_e such that y = x mod mi^from_e. In particular, y does not have to be “short” in any sense, but any lift is a valid result.

fn local_field_at<'ring>( &self, p: &Self::SuitableIdeal<'ring>, max_ideal_idx: usize, ) -> Self::LocalField<'ring>

where Self: 'ring,

Returns R / mi, where mi is the i-th maximal ideal over I.

fn local_ring_at<'ring>( &self, p: &Self::SuitableIdeal<'ring>, e: usize, max_ideal_idx: usize, ) -> Self::LocalRing<'ring>

where Self: 'ring,

Returns R / mi^e, where mi is the i-th maximal ideal over I.

fn random_suitable_ideal<'ring, F>( &'ring self, rng: F, ) -> Self::SuitableIdeal<'ring>

where F: FnMut() -> u64,

Returns an ideal sampled at random from the interval of all supported ideals.

fn reduce_ring_el<'ring>( &self, _p: &Self::SuitableIdeal<'ring>, to: (&Self::LocalRing<'ring>, usize), max_ideal_idx: usize, x: Self::Element, ) -> El<Self::LocalRing<'ring>>

where Self: 'ring,

Computes the reduction map

fn reduce_partial<'ring>( &self, _p: &Self::SuitableIdeal<'ring>, from: (&Self::LocalRing<'ring>, usize), to: (&Self::LocalRing<'ring>, usize), max_ideal_idx: usize, x: El<Self::LocalRing<'ring>>, ) -> El<Self::LocalRing<'ring>>

where Self: 'ring,

Computes the reduction map

fn heuristic_exponent<'ring, 'a, I>( &self, p: &i64, poly_deg: usize, coefficients: I, ) -> usize

where I: Iterator<Item = &'a Self::Element>, Self: 'a + 'ring,

Returns an exponent e such that we hope that the factors of a polynomial of given degree, involving the given coefficient can already be read of (via PolyGCDLocallyDomain::reconstruct_ring_el()) their reductions modulo I^e. Note that this is just a heuristic, and if it does not work, the implementation will gradually try larger e. Thus, even if this function returns constant 1, correctness will not be affected, but giving a good guess can improve performance

fn dbg_ideal<'ring>( &self, p: &Self::SuitableIdeal<'ring>, out: &mut Formatter<'_>, ) -> Result

where Self: 'ring,

impl PrincipalIdealRing for MPZBase

fn extended_ideal_gen( &self, lhs: &Self::Element, rhs: &Self::Element, ) -> (Self::Element, Self::Element, Self::Element)

Computes a Bezout identity for the generator g of the ideal (lhs, rhs) as g = s * lhs + t * rhs.

fn checked_div_min( &self, lhs: &Self::Element, rhs: &Self::Element, ) -> Option<Self::Element>

Similar to DivisibilityRing::checked_left_div() this computes a “quotient” q of lhs and rhs, if it exists. However, we impose the additional constraint that this quotient be minimal, i.e. there is no q' with q' | q properly and q' * rhs = lhs.

fn annihilator(&self, val: &Self::Element) -> Self::Element

Returns the (w.r.t. divisibility) smallest element x such that x * val = 0.

fn create_elimination_matrix( &self, a: &Self::Element, b: &Self::Element, ) -> ([Self::Element; 4], Self::Element)

Creates a matrix A of unit determinant such that A * (a, b)^T = (d, 0). Returns (A, d).

fn ideal_gen(&self, lhs: &Self::Element, rhs: &Self::Element) -> Self::Element

Computes a generator g of the ideal (lhs, rhs) = (g), also known as greatest common divisor.

fn lcm(&self, lhs: &Self::Element, rhs: &Self::Element) -> Self::Element

Computes a generator of the ideal (lhs) ∩ (rhs), also known as least common multiple.

impl RingBase for MPZBase

type Element = MPZEl

Type of elements of the ring

fn clone_el(&self, val: &Self::Element) -> Self::Element

fn mul_ref(&self, lhs: &Self::Element, rhs: &Self::Element) -> Self::Element

fn negate_inplace(&self, lhs: &mut Self::Element)

fn zero(&self) -> Self::Element

fn one(&self) -> Self::Element

fn sub_ref_fst(&self, lhs: &Self::Element, rhs: Self::Element) -> Self::Element

fn sub_ref_snd(&self, lhs: Self::Element, rhs: &Self::Element) -> Self::Element

fn add_assign(&self, lhs: &mut Self::Element, rhs: Self::Element)

fn add_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element)

fn mul_assign(&self, lhs: &mut Self::Element, rhs: Self::Element)

fn mul_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element)

fn mul_assign_int(&self, lhs: &mut Self::Element, rhs: i32)

fn sub(&self, lhs: Self::Element, rhs: Self::Element) -> Self::Element

fn from_int(&self, value: i32) -> Self::Element

fn eq_el(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool

fn is_zero(&self, val: &Self::Element) -> bool

fn is_one(&self, val: &Self::Element) -> bool

fn is_neg_one(&self, val: &Self::Element) -> bool

fn is_noetherian(&self) -> bool

Returns whether the ring is noetherian, i.e. every ideal is finitely generated.

fn is_commutative(&self) -> bool

Returns whether the ring is commutative, i.e. a * b = b * a for all elements a, b. Note that addition is assumed to be always commutative.

fn is_approximate(&self) -> bool

Returns whether this ring computes with approximations to elements. This would usually be the case for rings that are based on f32 or f64, to represent real or complex numbers.

fn dbg_within<'a>( &self, value: &Self::Element, out: &mut Formatter<'a>, _env: EnvBindingStrength, ) -> Result

Writes a human-readable representation of value to out, taking into account the possible context to place parenthesis as needed.

fn characteristic<I: IntegerRingStore + Copy>( &self, other_ZZ: I, ) -> Option<El<I>>

where I::Type: IntegerRing,

Returns the characteristic of this ring as an element of the given implementation of ZZ.

fn sub_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element)

fn neg_one(&self) -> Self::Element

fn dbg<'a>(&self, value: &Self::Element, out: &mut Formatter<'a>) -> Result

Writes a human-readable representation of value to out.

fn square(&self, value: &mut Self::Element)

fn negate(&self, value: Self::Element) -> Self::Element

fn sub_assign(&self, lhs: &mut Self::Element, rhs: Self::Element)

fn mul_int(&self, lhs: Self::Element, rhs: i32) -> Self::Element

fn mul_int_ref(&self, lhs: &Self::Element, rhs: i32) -> Self::Element

fn sub_self_assign(&self, lhs: &mut Self::Element, rhs: Self::Element)

Computes lhs := rhs - lhs.

fn sub_self_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element)

Computes lhs := rhs - lhs.

fn add_ref(&self, lhs: &Self::Element, rhs: &Self::Element) -> Self::Element

fn add_ref_fst(&self, lhs: &Self::Element, rhs: Self::Element) -> Self::Element

fn add_ref_snd(&self, lhs: Self::Element, rhs: &Self::Element) -> Self::Element

fn add(&self, lhs: Self::Element, rhs: Self::Element) -> Self::Element

fn sub_ref(&self, lhs: &Self::Element, rhs: &Self::Element) -> Self::Element

fn mul_ref_fst(&self, lhs: &Self::Element, rhs: Self::Element) -> Self::Element

fn mul_ref_snd(&self, lhs: Self::Element, rhs: &Self::Element) -> Self::Element

fn mul(&self, lhs: Self::Element, rhs: Self::Element) -> Self::Element

fn pow_gen<R: RingStore>( &self, x: Self::Element, power: &El<R>, integers: R, ) -> Self::Element

where R::Type: IntegerRing,

Raises x to the power of an arbitrary, nonnegative integer given by a custom integer ring implementation.

fn sum<I>(&self, els: I) -> Self::Element

where I: IntoIterator<Item = Self::Element>,

Sums the elements given by the iterator.

fn prod<I>(&self, els: I) -> Self::Element

where I: IntoIterator<Item = Self::Element>,

Computes the product of the elements given by the iterator.

impl SerializableElementRing for MPZBase

fn deserialize<'de, D>( &self, deserializer: D, ) -> Result<Self::Element, D::Error>

where D: Deserializer<'de>,

Deserializes an element of this ring from the given deserializer.

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

where S: Serializer,

Serializes an element of this ring to the given serializer.

impl Copy for MPZBase

impl Domain for MPZBase

impl Eq for MPZBase

impl StructuralPartialEq for MPZBase