Struct RustBigintRingBase

pub struct RustBigintRingBase<A: Allocator + Clone = Global> { /* private fields */ }

Arbitrary-precision integer implementation.

This is a not-too-well optimized implementation, written in pure Rust. If you need very high performance, consider using crate::rings::mpir::MPZ (requires an installation of mpir and activating the feature “mpir”).

Implementations

impl<A: Allocator + Clone> RustBigintRingBase<A>

pub fn map_i128(&self, val: &RustBigint<A>) -> Option<i128>

pub fn parse(&self, string: &str, base: u32) -> Result<RustBigint<A>, ()>

pub fn abs_base_u64_repr<'a>( &self, el: &'a RustBigint, ) -> impl 'a + Iterator<Item = u64>

pub fn from_base_u64_repr<I>(&self, data: I) -> RustBigint

where I: Iterator<Item = u64>,

Trait Implementations

impl<A: Clone + Allocator + Clone> Clone for RustBigintRingBase<A>

fn clone(&self) -> RustBigintRingBase<A>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<A: Debug + Allocator + Clone> Debug for RustBigintRingBase<A>

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

Formats the value using the given formatter.

impl<A: Allocator + Clone + Default> Default for RustBigintRingBase<A>

fn default() -> Self

Returns the “default value” for a type.

impl<A: Allocator + Clone> DivisibilityRing for RustBigintRingBase<A>

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<A: Allocator + Clone> EuclideanRing for RustBigintRingBase<A>

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

Computes euclidean division with remainder.

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

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

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

Computes euclidean division without remainder.

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

Computes only the remainder of euclidean division.

impl<A> FiniteRingSpecializable for RustBigintRingBase<A>

where A: Allocator + Clone,

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

fn is_finite_ring() -> bool

impl<A: Allocator + Clone> HashableElRing for RustBigintRingBase<A>

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

Hashes the given ring element.

impl IntCast<MPZBase> for RustBigintRingBase

Available on crate feature mpir only.

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

Maps the given integer into this ring.

impl<A: Allocator + Clone> IntCast<RustBigintRingBase<A>> for StaticRingBase<i128>

fn cast(&self, from: &RustBigintRingBase<A>, value: RustBigint<A>) -> i128

Maps the given integer into this ring.

impl<A: Allocator + Clone> IntCast<RustBigintRingBase<A>> for StaticRingBase<i16>

fn cast(&self, from: &RustBigintRingBase<A>, value: RustBigint<A>) -> i16

Maps the given integer into this ring.

impl<A: Allocator + Clone> IntCast<RustBigintRingBase<A>> for StaticRingBase<i32>

fn cast(&self, from: &RustBigintRingBase<A>, value: RustBigint<A>) -> i32

Maps the given integer into this ring.

impl<A: Allocator + Clone> IntCast<RustBigintRingBase<A>> for StaticRingBase<i64>

fn cast(&self, from: &RustBigintRingBase<A>, value: RustBigint<A>) -> i64

Maps the given integer into this ring.

impl<A: Allocator + Clone> IntCast<RustBigintRingBase<A>> for StaticRingBase<i8>

fn cast(&self, from: &RustBigintRingBase<A>, value: RustBigint<A>) -> i8

Maps the given integer into this ring.

impl<A1: Allocator + Clone, A2: Allocator + Clone> IntCast<RustBigintRingBase<A2>> for RustBigintRingBase<A1>

fn cast( &self, _: &RustBigintRingBase<A2>, value: RustBigint<A2>, ) -> Self::Element

Maps the given integer into this ring.

impl IntCast<RustBigintRingBase> for MPZBase

Available on crate feature mpir only.

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

Maps the given integer into this ring.

impl<A: Allocator + Clone> IntCast<StaticRingBase<i128>> for RustBigintRingBase<A>

fn cast(&self, _: &StaticRingBase<i128>, value: i128) -> RustBigint<A>

Maps the given integer into this ring.

impl<A: Allocator + Clone> IntCast<StaticRingBase<i16>> for RustBigintRingBase<A>

fn cast(&self, _: &StaticRingBase<i16>, value: i16) -> RustBigint<A>

Maps the given integer into this ring.

impl<A: Allocator + Clone> IntCast<StaticRingBase<i32>> for RustBigintRingBase<A>

fn cast(&self, _: &StaticRingBase<i32>, value: i32) -> RustBigint<A>

Maps the given integer into this ring.

impl<A: Allocator + Clone> IntCast<StaticRingBase<i64>> for RustBigintRingBase<A>

fn cast(&self, _: &StaticRingBase<i64>, value: i64) -> RustBigint<A>

Maps the given integer into this ring.

impl<A: Allocator + Clone> IntCast<StaticRingBase<i8>> for RustBigintRingBase<A>

fn cast(&self, _: &StaticRingBase<i8>, value: i8) -> RustBigint<A>

Maps the given integer into this ring.

impl<A> IntegerPolyGCDRing for RustBigintRingBase<A>

where A: Allocator + Clone,

type LocalRingAsZnBase<'ring> = <RustBigintRingBase<A> 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> = <RustBigintRingBase<A> 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<A: Allocator + Clone> IntegerRing for RustBigintRingBase<A>

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

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

fn from_float_approx(&self, value: 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 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 abs_is_bit_set(&self, value: &Self::Element, i: 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 euclidean_div_pow_2(&self, value: &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 mul_pow_2(&self, value: &mut Self::Element, power: usize)

Multiplies the element by a power of two.

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 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 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<A> InterpolationBaseRing for RustBigintRingBase<A>

where A: Allocator + Clone,

type ExtendedRing<'a> = RingRef<'a, RustBigintRingBase<A>> where Self: 'a

type ExtendedRingBase<'a> = RustBigintRingBase<A> where Self: 'a

Restricting this here to be DivisibilityRing + PrincipalIdealRing + Domain is necessary, because of a compiler bug, see also crate::compute_locally::EvaluatePolyLocallyRing::LocalRingBase

fn in_base<'a, S>(&self, _ext_ring: S, el: El<S>) -> Option<Self::Element>

where Self: 'a, S: RingStore<Type = Self::ExtendedRingBase<'a>>,

fn in_extension<'a, S>(&self, _ext_ring: S, el: Self::Element) -> El<S>

where Self: 'a, S: RingStore<Type = Self::ExtendedRingBase<'a>>,

fn interpolation_points<'a>( &'a self, count: usize, ) -> (Self::ExtendedRing<'a>, Vec<El<Self::ExtendedRing<'a>>>)

Returns count points such that the difference between any two of them is a non-zero-divisor.

impl<A: Allocator + Clone> OrderedRing for RustBigintRingBase<A>

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

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

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_neg(&self, value: &Self::Element) -> bool

Returns whether value < 0.

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<A: Allocator + Clone> PartialEq for RustBigintRingBase<A>

fn eq(&self, _other: &Self) -> 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<A> PolyGCDLocallyDomain for RustBigintRingBase<A>

where A: Allocator + Clone,

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<A: Allocator + Clone> PrincipalIdealRing for RustBigintRingBase<A>

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 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 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<A: Allocator + Clone> RingBase for RustBigintRingBase<A>

type Element = RustBigint<A>

Type of elements of the ring

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

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

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

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

fn negate_inplace(&self, lhs: &mut 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 zero(&self) -> 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, value: &Self::Element) -> bool

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

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

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_noetherian(&self) -> bool

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

fn dbg_within<'a>( &self, value: &Self::Element, out: &mut Formatter<'a>, _: 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 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 one(&self) -> 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_assign_int(&self, lhs: &mut Self::Element, rhs: i32)

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 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 sub(&self, lhs: Self::Element, rhs: Self::Element) -> Self::Element

fn mul_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<A: Allocator + Clone> SerializableElementRing for RustBigintRingBase<A>

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<A: Copy + Allocator + Clone> Copy for RustBigintRingBase<A>

impl<A: Allocator + Clone> Domain for RustBigintRingBase<A>