feanor_math/reduce_lift/
poly_factor_gcd.rs

1use std::fmt::Debug;
2use std::fmt::Display;
3
4use crate::algorithms::linsolve::LinSolveRing;
5use crate::algorithms::miller_rabin::is_prime;
6use crate::computation::no_error;
7use crate::delegate::*;
8use crate::divisibility::*;
9use crate::homomorphism::*;
10use crate::integer::*;
11use crate::ordered::OrderedRing;
12use crate::ring::*;
13use crate::rings::zn::*;
14use crate::seq::*;
15use crate::specialization::FiniteRingSpecializable;
16use crate::algorithms::poly_factor::FactorPolyField;
17use crate::algorithms::poly_gcd::PolyTFracGCDRing;
18use crate::rings::field::{AsField, AsFieldBase};
19use crate::field::Field;
20use crate::rings::finite::FiniteRing;
21
22///
23/// Trait for rings that support lifting partial factorizations of polynomials modulo a prime
24/// to the ring. For infinite fields, this is the most important approach to computing gcd's,
25/// and also factorizations (with some caveats...).
26/// 
27/// Note that here (and in `feanor-math` generally), the term "local" is used to refer to algorithms
28/// that work modulo prime ideals (or their powers), which is different from the mathematical concept
29/// of localization.
30/// 
31/// The general philosophy is similar to [`crate::reduce_lift::poly_eval::EvalPolyLocallyRing`].
32/// However, when working with factorizations, it is usually better to compute modulo the factorization
33/// modulo an ideal `I`, and use Hensel lifting to derive the factorization modulo `I^e`.
34/// `EvalPolyLocallyRing` on the other hand is designed to allow computations modulo multiple different 
35/// maximal ideals.
36/// 
37/// I am currently not yet completely sure what the exact requirements of this trait would be,
38/// but conceptually, we want that for a random ideal `I` taken from some set of ideals (e.g. maximal
39/// ideals, prime ideals, ... depending on the context), the quotient `R / I` should be "nice",
40/// so that we can compute the desired factorization (or gcd etc.) over `R / I`.
41/// Furthermore there should be a power `e` such that we can derive the factorization (or gcd etc.)
42/// over `R` from the factorization over `R / I^e`. Note that we don't assume that this `e` can be
43/// computed, except possibly in special cases (like the integers). Also, we cannot always assume
44/// that `I` is a maximal ideal (unfortunately - it was a nasty surprise when I realized this after
45/// running my first implementation), however I believe we can choose it such that we know its decomposition
46/// into maximal ideals `a = m1 ∩ ... ∩ mr`.
47/// 
48/// Note also that I want this to work even when going to algebraic extensions or even the algebraic
49/// closure. This however seems to follow naturally in most cases.
50/// 
51/// # Mathematical examples
52/// 
53/// There are three main classes of rings that this trait is designed for
54///  - The integers `ZZ`. By Gauss' lemma, we know that any factor of an integral polynomial
55///    is again integral, and we can bound its size (using the absolute value `|.|` of the real
56///    numbers) in terms of size and degree of the original polynomial. 
57///    This motivates the main algorithm for factoring over `Z`: Reduce modulo a prime
58///    `p`, lift the factorization to `p^e` for a large enough `p`, and (more or less) read of
59///    the factors over `Z`.
60///  - Multivariate polynomial rings `R[X1, ..., Xm]` where `R` is a finite field (or another ring
61///    where we can efficiently compute polynomial factorizations, e.g. another [`PolyGCDLocallyDomain`]).
62///    For simplicity, let's focus on the finite field case, i.e. `R = k`. Then we can take a maximal
63///    ideal `m` of `k[X1, ..., Xm]`, and reduce a polynomial `f in k[X1, ..., Xm][Y]` modulo `m`, compute
64///    its factorization there (i.e. over `k`), lift it to `k[X1, ..., Xm]/m^e` and (more or less) read
65///    of the factors over `R[X1, ..., Xm]`. Note that if the base ring is not a field, the ideals will
66///    only be prime and not maximal. Also, the polynomial coefficients of the result might only live in
67///    the fraction field of `R`, similar to the algebraic number field case.
68///  - Orders in algebraic number fields. This case is much more complicated, since (in general) we
69///    don't have a UFD anymore. In particular, this is the case where we cannot generally choose `a = m` to be
70///    a maximal ideal, and also need rational reconstruction when lifting the factorization back to the number
71///    field. More concretely, the factors of a polynomial with coefficients in an order `R` don't necessarily 
72///    have coefficients in `R`. Example: `X^2 - sqrt(3) X - 1` over `Z[sqrt(3), sqrt(7)]`
73///    has the factor `X - (sqrt(3) + sqrt(7)) / 2`.
74///    However, it turns out that if the original polynomial is monic, then its factors have coefficients in
75///    the maximal order `O` of `R ⊗ QQ`. In particular, if we scale the factor by `[R : O] | disc(R)`, then
76///    we do end up with coefficients in `R`. Unfortunately, the discriminant can become really huge, which
77///    is why in the literature, rational reconstruction is used, to elements from `R / p^e` to "small" fractions
78///    in `Frac(R)`.
79/// 
80/// I cannot think of any other good examples (these were the ones I had in mind when writing this trait), but 
81/// who knows, maybe there are other rings that satisfy this and which we can thus do polynomial factorization in.
82/// 
83/// # Type-level recursion
84/// 
85/// This trait and related functionality use type-level recursion, as explained in [`crate::reduce_lift::poly_eval::EvalPolyLocallyRing`].
86/// 
87#[stability::unstable(feature = "enable")]
88pub trait PolyGCDLocallyDomain: Domain + DivisibilityRing + FiniteRingSpecializable {
89
90    ///
91    /// The type of the local ring once we quotiented out a power of a prime ideal.
92    /// 
93    type LocalRingBase<'ring>: ?Sized + LinSolveRing
94        where Self: 'ring;
95
96    type LocalRing<'ring>: RingStore<Type = Self::LocalRingBase<'ring>> + Clone
97        where Self: 'ring;
98    
99    ///
100    /// The type of the field we get by quotienting out a power of a prime ideal.
101    /// 
102    /// For the reason why there are so many quite specific trait bounds here:
103    /// See the doc of [`crate::reduce_lift::poly_eval::EvalPolyLocallyRing::LocalRingBase`].
104    /// 
105    type LocalFieldBase<'ring>: ?Sized + PolyTFracGCDRing + FactorPolyField + Field + SelfIso + FiniteRingSpecializable
106        where Self: 'ring;
107
108    type LocalField<'ring>: RingStore<Type = Self::LocalFieldBase<'ring>> + Clone
109        where Self: 'ring;
110
111    ///
112    /// An ideal of the ring for which we know a decomposition into maximal ideals, and
113    /// can use Hensel lifting to lift values to higher powers of this ideal.
114    /// 
115    type SuitableIdeal<'ring>
116        where Self: 'ring;
117
118    ///
119    /// Returns an exponent `e` such that we hope that the factors of a polynomial of given degree, 
120    /// involving the given coefficient can already be read of (via [`PolyGCDLocallyDomain::reconstruct_ring_el()`]) 
121    /// their reductions modulo `I^e`. Note that this is just a heuristic, and if it does not work,
122    /// the implementation will gradually try larger `e`. Thus, even if this function returns constant
123    /// 1, correctness will not be affected, but giving a good guess can improve performance
124    /// 
125    fn heuristic_exponent<'ring, 'a, I>(&self, _ideal: &Self::SuitableIdeal<'ring>, _poly_deg: usize, _coefficients: I) -> usize
126        where I: Iterator<Item = &'a Self::Element>,
127            Self: 'a,
128            Self: 'ring;
129
130    ///
131    /// Returns an ideal sampled at random from the interval of all supported ideals.
132    /// 
133    fn random_suitable_ideal<'ring, F>(&'ring self, rng: F) -> Self::SuitableIdeal<'ring>
134        where F: FnMut() -> u64;
135
136    ///
137    /// Returns the number of maximal ideals in the primary decomposition of `ideal`.
138    /// 
139    fn maximal_ideal_factor_count<'ring>(&self, ideal: &Self::SuitableIdeal<'ring>) -> usize
140        where Self: 'ring;
141
142    ///
143    /// Returns `R / mi`, where `mi` is the `i`-th maximal ideal over `I`.
144    /// 
145    /// This will always be a field, since `mi` is a maximal ideal.
146    /// 
147    fn local_field_at<'ring>(&self, ideal: &Self::SuitableIdeal<'ring>, max_ideal_idx: usize) -> Self::LocalField<'ring>
148        where Self: 'ring;
149    
150    ///
151    /// Returns `R / mi^e`, where `mi` is the `i`-th maximal ideal over `I`.
152    /// 
153    fn local_ring_at<'ring>(&self, ideal: &Self::SuitableIdeal<'ring>, e: usize, max_ideal_idx: usize) -> Self::LocalRing<'ring>
154        where Self: 'ring;
155
156    ///
157    /// Computes the reduction map
158    /// ```text
159    ///   R -> R / mi^e
160    /// ```
161    /// where `mi` is the `i`-th maximal ideal over `I`.
162    /// 
163    fn reduce_ring_el<'ring>(&self, ideal: &Self::SuitableIdeal<'ring>, to: (&Self::LocalRingBase<'ring>, usize), max_ideal_idx: usize, x: Self::Element) -> El<Self::LocalRing<'ring>>
164        where Self: 'ring;
165
166    ///
167    /// Computes the reduction map
168    /// ```text
169    ///   R / mi^e1 -> R / mi^e2
170    /// ```
171    /// where `e1 >= e2` and `mi` is the `i`-th maximal ideal over `I`.
172    /// 
173    fn reduce_partial<'ring>(&self, ideal: &Self::SuitableIdeal<'ring>, from: (&Self::LocalRingBase<'ring>, usize), to: (&Self::LocalRingBase<'ring>, usize), max_ideal_idx: usize, x: El<Self::LocalRing<'ring>>) -> El<Self::LocalRing<'ring>>
174        where Self: 'ring;
175
176    ///
177    /// Computes the isomorphism between the ring and field representations of `R / mi`
178    /// 
179    fn base_ring_to_field<'ring>(&self, ideal: &Self::SuitableIdeal<'ring>, from: &Self::LocalRingBase<'ring>, to: &Self::LocalFieldBase<'ring>, max_ideal_idx: usize, x: El<Self::LocalRing<'ring>>) -> El<Self::LocalField<'ring>>
180        where Self: 'ring;
181
182    ///
183    /// Computes the isomorphism between the ring and field representations of `R / mi`
184    /// 
185    fn field_to_base_ring<'ring>(&self, ideal: &Self::SuitableIdeal<'ring>, from: &Self::LocalFieldBase<'ring>, to: &Self::LocalRingBase<'ring>, max_ideal_idx: usize, x: El<Self::LocalField<'ring>>) -> El<Self::LocalRing<'ring>>
186        where Self: 'ring;
187
188    ///
189    /// Computes any element `y` in `R / mi^to_e` such that `y = x mod mi^from_e`.
190    /// In particular, `y` does not have to be "short" in any sense, but any lift
191    /// is a valid result.
192    /// 
193    fn lift_partial<'ring>(&self, ideal: &Self::SuitableIdeal<'ring>, from: (&Self::LocalRingBase<'ring>, usize), to: (&Self::LocalRingBase<'ring>, usize), max_ideal_idx: usize, x: El<Self::LocalRing<'ring>>) -> El<Self::LocalRing<'ring>>
194        where Self: 'ring;
195
196    ///
197    /// Computes a "small" element `x in R` such that `x mod mi^e` is equal to the given value,
198    /// for every maximal ideal `mi` over `I`.
199    /// In cases where the factors of polynomials in `R[X]` do not necessarily have coefficients
200    /// in `R`, this function might have to do rational reconstruction. 
201    /// 
202    fn reconstruct_ring_el<'local, 'element, 'ring, V1, V2>(&self, ideal: &Self::SuitableIdeal<'ring>, from: V1, e: usize, x: V2) -> Self::Element
203        where Self: 'ring, 
204            V1: VectorFn<&'local Self::LocalRing<'ring>>,
205            V2: VectorFn<&'element El<Self::LocalRing<'ring>>>,
206            Self::LocalRing<'ring>: 'local,
207            El<Self::LocalRing<'ring>>: 'element,
208            'ring: 'local + 'element;
209
210    fn dbg_ideal<'ring>(&self, ideal: &Self::SuitableIdeal<'ring>, out: &mut std::fmt::Formatter) -> std::fmt::Result
211        where Self: 'ring;
212}
213
214///
215/// Subtrait of [`PolyGCDLocallyDomain`] that restricts the local rings to be [`ZnRing`],
216/// which is necessary when implementing some base cases.
217/// 
218#[stability::unstable(feature = "enable")]
219pub trait IntegerPolyGCDRing: PolyGCDLocallyDomain {
220
221    ///
222    /// It would be much preferrable if we could restrict associated types from supertraits,
223    /// this is just a workaround (and an ugly one at that)
224    /// 
225    type LocalRingAsZnBase<'ring>: ?Sized + CanIsoFromTo<Self::LocalRingBase<'ring>> + ZnRing + SelfIso
226        where Self: 'ring;
227
228    type LocalRingAsZn<'ring>: RingStore<Type = Self::LocalRingAsZnBase<'ring>> + Clone
229        where Self: 'ring;
230
231    fn local_ring_as_zn<'a, 'ring>(&self, local_field: &'a Self::LocalRing<'ring>) -> &'a Self::LocalRingAsZn<'ring>;
232
233    fn local_ring_into_zn<'ring>(&self, local_field: Self::LocalRing<'ring>) -> Self::LocalRingAsZn<'ring>;
234
235    fn principal_ideal_generator<'ring>(&self, p: &Self::SuitableIdeal<'ring>) -> El<BigIntRing>
236        where Self: 'ring
237    {
238        assert_eq!(1, self.maximal_ideal_factor_count(p));
239        let Fp = self.local_ring_at(p, 1, 0);
240        let Fp = self.local_ring_as_zn(&Fp);
241        return int_cast(Fp.integer_ring().clone_el(Fp.modulus()), BigIntRing::RING, Fp.integer_ring());
242    }
243}
244
245#[stability::unstable(feature = "enable")]
246pub struct IdealDisplayWrapper<'a, 'ring, R: 'ring + ?Sized + PolyGCDLocallyDomain> {
247    ring: &'a R,
248    ideal: &'a R::SuitableIdeal<'ring>
249}
250
251impl<'a, 'ring, R: 'ring + ?Sized + PolyGCDLocallyDomain> IdealDisplayWrapper<'a, 'ring, R> {
252
253    #[stability::unstable(feature = "enable")]
254    pub fn new(ring: &'a R, ideal: &'a R::SuitableIdeal<'ring>) -> Self {
255        Self {
256            ring: ring, 
257            ideal: ideal
258        }
259    }
260}
261
262impl<'a, 'ring, R: 'ring + ?Sized + PolyGCDLocallyDomain> Display for IdealDisplayWrapper<'a, 'ring, R> {
263
264    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
265        self.ring.dbg_ideal(self.ideal, f)
266    }
267}
268
269///
270/// The map `R -> R/m^e`, where `m` is a maximal ideal factor of the ideal `I`,
271/// as specified by [`PolyGCDLocallyDomain`].
272/// 
273#[stability::unstable(feature = "enable")]
274pub struct PolyGCDLocallyReductionMap<'ring, 'data, 'local, R>
275    where R: 'ring + ?Sized + PolyGCDLocallyDomain, 'ring: 'data
276{
277    ring: RingRef<'data, R>,
278    ideal: &'data R::SuitableIdeal<'ring>,
279    to: (&'local R::LocalRing<'ring>, usize),
280    max_ideal_idx: usize
281}
282
283impl<'ring, 'data, 'local, R> PolyGCDLocallyReductionMap<'ring, 'data, 'local, R>
284    where R: 'ring +?Sized + PolyGCDLocallyDomain, 'ring: 'data
285{
286    #[stability::unstable(feature = "enable")]
287    pub fn new(ring: &'data R, ideal: &'data R::SuitableIdeal<'ring>, to: &'local R::LocalRing<'ring>, to_e: usize, max_ideal_idx: usize) -> Self {
288        assert!(to.get_ring() == ring.local_ring_at(ideal, to_e, max_ideal_idx).get_ring());
289        Self {
290            ring: RingRef::new(ring),
291            ideal: ideal,
292            to: (to, to_e),
293            max_ideal_idx: max_ideal_idx
294        }
295    }
296}
297
298impl<'ring, 'data, 'local, R> Homomorphism<R, R::LocalRingBase<'ring>> for PolyGCDLocallyReductionMap<'ring, 'data, 'local, R>
299    where R: 'ring +?Sized + PolyGCDLocallyDomain, 'ring: 'data
300{
301    type CodomainStore = &'local R::LocalRing<'ring>;
302    type DomainStore = RingRef<'data, R>;
303
304    fn codomain<'b>(&'b self) -> &'b Self::CodomainStore {
305        &self.to.0
306    }
307
308    fn domain<'b>(&'b self) -> &'b Self::DomainStore {
309        &self.ring
310    }
311
312    fn map(&self, x: <R as RingBase>::Element) -> <R::LocalRingBase<'ring> as RingBase>::Element {
313        self.ring.get_ring().reduce_ring_el(self.ideal, (self.to.0.get_ring(), self.to.1), self.max_ideal_idx, x)
314    }
315}
316
317///
318/// The map `R/m^r -> R/m^e`, where `r > e` and `m` is a maximal ideal factor of the 
319/// ideal `I`, as specified by [`PolyGCDLocallyDomain`].
320/// 
321#[stability::unstable(feature = "enable")]
322pub struct PolyGCDLocallyIntermediateReductionMap<'ring, 'data, 'local, R>
323    where R: 'ring + ?Sized + PolyGCDLocallyDomain, 'ring: 'data
324{
325    ring: RingRef<'data, R>,
326    ideal: &'data R::SuitableIdeal<'ring>,
327    from: (&'local R::LocalRing<'ring>, usize),
328    to: (&'local R::LocalRing<'ring>, usize),
329    max_ideal_idx: usize
330}
331
332impl<'ring, 'data, 'local, R> PolyGCDLocallyIntermediateReductionMap<'ring, 'data, 'local, R>
333    where R: 'ring + ?Sized + PolyGCDLocallyDomain, 'ring: 'data
334{
335    #[stability::unstable(feature = "enable")]
336    pub fn new(ring: &'data R, ideal: &'data R::SuitableIdeal<'ring>, from: &'local R::LocalRing<'ring>, from_e: usize, to: &'local R::LocalRing<'ring>, to_e: usize, max_ideal_idx: usize) -> Self {
337        assert!(ring.local_ring_at(ideal, from_e, max_ideal_idx).get_ring() == from.get_ring());
338        assert!(ring.local_ring_at(ideal, to_e, max_ideal_idx).get_ring() == to.get_ring());
339        Self {
340            ring: RingRef::new(ring),
341            ideal: ideal,
342            from: (from, from_e),
343            to: (to, to_e),
344            max_ideal_idx: max_ideal_idx
345        }
346    }
347
348    #[stability::unstable(feature = "enable")]
349    pub fn parent_ring<'a>(&'a self) -> RingRef<'a, R> {
350        RingRef::new(self.ring.get_ring())
351    }
352
353    #[stability::unstable(feature = "enable")]
354    pub fn from_e(&self) -> usize {
355        self.from.1
356    }
357
358    #[stability::unstable(feature = "enable")]
359    pub fn to_e(&self) -> usize {
360        self.to.1
361    }
362
363    #[stability::unstable(feature = "enable")]
364    pub fn ideal<'a>(&'a self) -> &'a R::SuitableIdeal<'ring> {
365        &self.ideal
366    }
367
368    #[stability::unstable(feature = "enable")]
369    pub fn max_ideal_idx(&self) -> usize {
370        self.max_ideal_idx
371    }
372}
373
374impl<'ring, 'data, 'local, R> Homomorphism<R::LocalRingBase<'ring>, R::LocalRingBase<'ring>> for PolyGCDLocallyIntermediateReductionMap<'ring, 'data, 'local, R>
375    where R: 'ring + ?Sized + PolyGCDLocallyDomain, 'ring: 'data
376{
377    type CodomainStore = &'local R::LocalRing<'ring>;
378    type DomainStore = &'local R::LocalRing<'ring>;
379
380    fn codomain<'b>(&'b self) -> &'b Self::CodomainStore {
381        &self.to.0
382    }
383
384    fn domain<'b>(&'b self) -> &'b Self::DomainStore {
385        &self.from.0
386    }
387
388    fn map(&self, x: <R::LocalRingBase<'ring> as RingBase>::Element) -> <R::LocalRingBase<'ring> as RingBase>::Element {
389        self.ring.get_ring().reduce_partial(self.ideal, (self.from.0.get_ring(), self.from.1), (self.to.0.get_ring(), self.to.1), self.max_ideal_idx, x)
390    }
391}
392
393///
394/// The isomorphism from the standard representation to the 
395/// field representation of `R / mi`, for a [`PolyGCDLocallyDomain`]
396/// `R` with maximal ideal `mi`.
397/// 
398#[stability::unstable(feature = "enable")]
399pub struct PolyGCDLocallyBaseRingToFieldIso<'ring, 'data, 'local, R>
400    where R: 'ring + ?Sized + PolyGCDLocallyDomain, 'ring: 'data
401{
402    ring: RingRef<'data, R>,
403    ideal: &'data R::SuitableIdeal<'ring>,
404    from: RingRef<'local, R::LocalRingBase<'ring>>,
405    to: RingRef<'local, R::LocalFieldBase<'ring>>,
406    max_ideal_idx: usize
407}
408
409impl<'ring, 'data, 'local, R> PolyGCDLocallyBaseRingToFieldIso<'ring, 'data, 'local, R>
410    where R: 'ring + ?Sized + PolyGCDLocallyDomain, 'ring: 'data
411{
412    #[stability::unstable(feature = "enable")]
413    pub fn new(ring: &'data R, ideal: &'data R::SuitableIdeal<'ring>, from: &'local R::LocalRingBase<'ring>, to: &'local R::LocalFieldBase<'ring>, max_ideal_idx: usize) -> Self {
414        assert!(ring.local_ring_at(ideal, 1, max_ideal_idx).get_ring() == from);
415        assert!(ring.local_field_at(ideal, max_ideal_idx).get_ring() == to);
416        Self {
417            ring: RingRef::new(ring),
418            ideal: ideal,
419            from: RingRef::new(from),
420            to: RingRef::new(to),
421            max_ideal_idx: max_ideal_idx
422        }
423    }
424
425    #[stability::unstable(feature = "enable")]
426    pub fn inv(&self) -> PolyGCDLocallyFieldToBaseRingIso<'ring, 'data, 'local, R> {
427        PolyGCDLocallyFieldToBaseRingIso {
428            ring: self.ring,
429            ideal: self.ideal,
430            from: self.to,
431            to: self.from,
432            max_ideal_idx: self.max_ideal_idx
433        }
434    }
435}
436
437impl<'ring, 'data, 'local, R> Homomorphism<R::LocalRingBase<'ring>, R::LocalFieldBase<'ring>> for PolyGCDLocallyBaseRingToFieldIso<'ring, 'data, 'local, R>
438    where R: 'ring + ?Sized + PolyGCDLocallyDomain, 'ring: 'data
439{
440    type DomainStore = RingRef<'local, R::LocalRingBase<'ring>>;
441    type CodomainStore = RingRef<'local, R::LocalFieldBase<'ring>>;
442
443    fn codomain<'b>(&'b self) -> &'b Self::CodomainStore {
444        &self.to
445    }
446
447    fn domain<'b>(&'b self) -> &'b Self::DomainStore {
448        &self.from
449    }
450
451    fn map(&self, x: <R::LocalRingBase<'ring> as RingBase>::Element) -> <R::LocalFieldBase<'ring> as RingBase>::Element {
452        self.ring.get_ring().base_ring_to_field(self.ideal, self.from.get_ring(), self.to.get_ring(), self.max_ideal_idx, x)
453    }
454}
455
456///
457/// The isomorphism from the field representation to the 
458/// standard representation of `R / mi`, for a [`PolyGCDLocallyDomain`]
459/// `R` with maximal ideal `mi`.
460/// 
461#[stability::unstable(feature = "enable")]
462pub struct PolyGCDLocallyFieldToBaseRingIso<'ring, 'data, 'local, R>
463    where R: 'ring + ?Sized + PolyGCDLocallyDomain, 'ring: 'data
464{
465    ring: RingRef<'data, R>,
466    ideal: &'data R::SuitableIdeal<'ring>,
467    to: RingRef<'local, R::LocalRingBase<'ring>>,
468    from: RingRef<'local, R::LocalFieldBase<'ring>>,
469    max_ideal_idx: usize
470}
471
472impl<'ring, 'data, 'local, R> PolyGCDLocallyFieldToBaseRingIso<'ring, 'data, 'local, R>
473    where R: 'ring + ?Sized + PolyGCDLocallyDomain, 'ring: 'data
474{
475    #[stability::unstable(feature = "enable")]
476    pub fn inv(&self) -> PolyGCDLocallyBaseRingToFieldIso<'ring, 'data, 'local, R> {
477        PolyGCDLocallyBaseRingToFieldIso {
478            ring: self.ring,
479            ideal: self.ideal,
480            from: self.to,
481            to: self.from,
482            max_ideal_idx: self.max_ideal_idx
483        }
484    }
485}
486
487impl<'ring, 'data, 'local, R> Homomorphism<R::LocalFieldBase<'ring>, R::LocalRingBase<'ring>> for PolyGCDLocallyFieldToBaseRingIso<'ring, 'data, 'local, R>
488    where R: 'ring + ?Sized + PolyGCDLocallyDomain, 'ring: 'data
489{
490    type DomainStore = RingRef<'local, R::LocalFieldBase<'ring>>;
491    type CodomainStore = RingRef<'local, R::LocalRingBase<'ring>>;
492
493    fn codomain<'b>(&'b self) -> &'b Self::CodomainStore {
494        &self.to
495    }
496
497    fn domain<'b>(&'b self) -> &'b Self::DomainStore {
498        &self.from
499    }
500
501    fn map(&self, x: <R::LocalFieldBase<'ring> as RingBase>::Element) -> <R::LocalRingBase<'ring> as RingBase>::Element {
502        self.ring.get_ring().field_to_base_ring(self.ideal, self.from.get_ring(), self.to.get_ring(), self.max_ideal_idx, x)
503    }
504}
505
506///
507/// The sequence of maps `R  ->  R/m1^e x ... x R/mr^e  ->  R/m1 x ... x R/mr`, where
508/// `m1, ..., mr` are the maximal ideals containing `I`, as specified by [`PolyGCDLocallyDomain`].
509/// 
510/// This sequence of maps is very relevant when using the compute-mod-p-and-lift approach
511/// for polynomial operations over infinite rings (e.g. `QQ`). This is also the primary use case
512/// for [`ReductionContext`].
513///
514#[stability::unstable(feature = "enable")]
515pub struct ReductionContext<'ring, 'data, R>
516    where R: 'ring + ?Sized + PolyGCDLocallyDomain, 'ring: 'data
517{
518    ring: RingRef<'data, R>,
519    ideal: &'data R::SuitableIdeal<'ring>,
520    from_e: usize,
521    from: Vec<R::LocalRing<'ring>>,
522    to: Vec<R::LocalRing<'ring>>,
523    to_fields: Vec<R::LocalField<'ring>>
524}
525
526impl<'ring, 'data, R> ReductionContext<'ring, 'data, R>
527    where R: 'ring + ?Sized + PolyGCDLocallyDomain, 'ring: 'data
528{
529    #[stability::unstable(feature = "enable")]
530    pub fn new(ring: &'data R, ideal: &'data R::SuitableIdeal<'ring>, e: usize) -> Self {
531        assert!(e >= 1);
532        let maximal_ideal_factor_count = ring.maximal_ideal_factor_count(ideal);
533        Self {
534            ring: RingRef::new(ring), 
535            ideal: ideal, 
536            from_e: e,
537            from: (0..maximal_ideal_factor_count).map(|idx| ring.local_ring_at(ideal, e, idx)).collect::<Vec<_>>(), 
538            to: (0..maximal_ideal_factor_count).map(|idx| ring.local_ring_at(ideal, 1, idx)).collect::<Vec<_>>(),
539            to_fields: (0..maximal_ideal_factor_count).map(|idx| ring.local_field_at(ideal, idx)).collect::<Vec<_>>(),
540        }
541    }
542    
543    #[stability::unstable(feature = "enable")]
544    pub fn ideal(&self) -> &'data R::SuitableIdeal<'ring> {
545        self.ideal
546    }
547
548    #[stability::unstable(feature = "enable")]
549    pub fn main_ring_to_field_reduction<'local>(&'local self, max_ideal_idx: usize) -> PolyGCDLocallyReductionMap<'ring, 'data, 'local, R> {
550        PolyGCDLocallyReductionMap {
551            ideal: self.ideal,
552            ring: self.ring,
553            to: (self.to.at(max_ideal_idx), 1),
554            max_ideal_idx: max_ideal_idx
555        }
556    }
557
558    #[stability::unstable(feature = "enable")]
559    pub fn main_ring_to_intermediate_ring_reduction<'local>(&'local self, max_ideal_idx: usize) -> PolyGCDLocallyReductionMap<'ring, 'data, 'local, R> {
560        PolyGCDLocallyReductionMap {
561            ideal: self.ideal,
562            ring: self.ring,
563            to: (self.from.at(max_ideal_idx), self.from_e),
564            max_ideal_idx: max_ideal_idx
565        }
566    }
567
568    #[stability::unstable(feature = "enable")]
569    pub fn intermediate_ring_to_field_reduction<'local>(&'local self, max_ideal_idx: usize) -> PolyGCDLocallyIntermediateReductionMap<'ring, 'data, 'local, R> {
570        PolyGCDLocallyIntermediateReductionMap {
571            from: (&self.from[max_ideal_idx], self.from_e),
572            to: (&self.to[max_ideal_idx], 1),
573            max_ideal_idx: max_ideal_idx,
574            ring: self.ring,
575            ideal: self.ideal
576        }
577    }
578
579    #[stability::unstable(feature = "enable")]
580    pub fn base_ring_to_field_iso<'local>(&'local self, max_ideal_idx: usize) -> PolyGCDLocallyBaseRingToFieldIso<'ring, 'data, 'local, R> {
581        PolyGCDLocallyBaseRingToFieldIso {
582            ring: self.ring,
583            ideal: self.ideal,
584            from: RingRef::new(self.to[max_ideal_idx].get_ring()),
585            to: RingRef::new(self.to_fields[max_ideal_idx].get_ring()),
586            max_ideal_idx: max_ideal_idx
587        }
588    }
589
590    #[stability::unstable(feature = "enable")]
591    pub fn len(&self) -> usize {
592        self.from.len()
593    }
594
595    #[stability::unstable(feature = "enable")]
596    pub fn reconstruct_ring_el<'local, V>(&self, els: V) -> R::Element
597        where V: VectorFn<&'local El<R::LocalRing<'ring>>>,
598            El<R::LocalRing<'ring>>: 'local,
599            'ring: 'local
600    {
601        fn do_reconstruction<'ring, 'local, R, V>(ring: &R, ideal: &R::SuitableIdeal<'ring>, local_rings: &[R::LocalRing<'ring>], e: usize, els: V) -> R::Element
602            where R: 'ring + ?Sized + PolyGCDLocallyDomain,
603                V: VectorFn<&'local El<R::LocalRing<'ring>>>,
604                El<R::LocalRing<'ring>>: 'local,
605                'ring: 'local
606        {
607            ring.reconstruct_ring_el(ideal, local_rings.as_fn(), e, els)
608        }
609        do_reconstruction(self.ring.get_ring(), self.ideal, &self.from[..], self.from_e, els)
610    }
611}
612
613#[stability::unstable(feature = "enable")]
614pub const INTRING_HEURISTIC_FACTOR_SIZE_OVER_POLY_SIZE_FACTOR: f64 = 0.25;
615
616///
617/// Implements [`PolyGCDLocallyDomain`] and [`IntegerPolyGCDRing`] for an integer ring.
618/// 
619/// This uses a default implementation, where the maximal ideals are random 24-bit prime numbers,
620/// and the corresponding residue field is implemented using [`crate::rings::zn::zn_64::Zn`]. This
621/// should be suitable in almost all scenarios.
622/// 
623/// The syntax is the same as for other impl-macros, see e.g. [`crate::impl_interpolation_base_ring_char_zero!`].
624/// 
625#[macro_export]
626macro_rules! impl_poly_gcd_locally_for_ZZ {
627    (IntegerPolyGCDRing for $int_ring_type:ty) => {
628        impl_poly_gcd_locally_for_ZZ!{ <{}> IntegerPolyGCDRing for $int_ring_type where }
629    };
630    (<{$($gen_args:tt)*}> IntegerPolyGCDRing for $int_ring_type:ty where $($constraints:tt)*) => {
631
632        impl<$($gen_args)*> $crate::reduce_lift::poly_factor_gcd::PolyGCDLocallyDomain for $int_ring_type
633            where $($constraints)*
634        {
635            type LocalRing<'ring> = $crate::rings::zn::zn_big::Zn<BigIntRing>
636                where Self: 'ring;
637            type LocalRingBase<'ring> = $crate::rings::zn::zn_big::ZnBase<BigIntRing>
638                where Self: 'ring;
639            type LocalFieldBase<'ring> = $crate::rings::field::AsFieldBase<$crate::rings::zn::zn_64::Zn>
640                where Self: 'ring;
641            type LocalField<'ring> = $crate::rings::field::AsField<$crate::rings::zn::zn_64::Zn>
642                where Self: 'ring;
643            type SuitableIdeal<'ring> = i64
644                where Self: 'ring;
645        
646            fn reconstruct_ring_el<'local, 'element, 'ring, V1, V2>(&self, _p: &Self::SuitableIdeal<'ring>, from: V1, _e: usize, x: V2) -> Self::Element
647                where Self: 'ring,
648                    V1: $crate::seq::VectorFn<&'local Self::LocalRing<'ring>>,
649                    V2: $crate::seq::VectorFn<&'element El<Self::LocalRing<'ring>>>
650            {
651                use $crate::rings::zn::*;
652                #[allow(unused)]
653                use $crate::seq::*;
654                assert_eq!(1, from.len());
655                assert_eq!(1, x.len());
656                int_cast(from.at(0).smallest_lift(from.at(0).clone_el(x.at(0))), RingRef::new(self), BigIntRing::RING)
657            }
658
659            fn maximal_ideal_factor_count<'ring>(&self, _p: &Self::SuitableIdeal<'ring>) -> usize
660                where Self: 'ring
661            {
662                1
663            }
664        
665            fn lift_partial<'ring>(&self, _p: &Self::SuitableIdeal<'ring>, from: (&Self::LocalRingBase<'ring>, usize), to: (&Self::LocalRingBase<'ring>, usize), max_ideal_idx: usize, x: El<Self::LocalRing<'ring>>) -> El<Self::LocalRing<'ring>>
666                where Self: 'ring
667            {
668                use $crate::rings::zn::*;
669                use $crate::homomorphism::*;
670
671                assert_eq!(0, max_ideal_idx);
672                assert!(from.1 <= to.1);
673                let hom = RingRef::new(to.0).into_can_hom(to.0.integer_ring()).ok().unwrap();
674                return hom.map(from.0.any_lift(x));
675            }
676        
677            fn local_field_at<'ring>(&self, p: &Self::SuitableIdeal<'ring>, max_ideal_idx: usize) -> Self::LocalField<'ring>
678                where Self: 'ring
679            {
680                use $crate::rings::zn::*;
681
682                assert_eq!(0, max_ideal_idx);
683                $crate::rings::zn::zn_64::Zn::new(*p as u64).as_field().ok().unwrap()
684            }
685        
686            fn local_ring_at<'ring>(&self, p: &Self::SuitableIdeal<'ring>, e: usize, max_ideal_idx: usize) -> Self::LocalRing<'ring>
687                where Self: 'ring
688            {
689                assert_eq!(0, max_ideal_idx);
690                $crate::rings::zn::zn_big::Zn::new(BigIntRing::RING, BigIntRing::RING.pow(int_cast(*p, BigIntRing::RING, StaticRing::<i64>::RING), e))
691            }
692        
693            fn random_suitable_ideal<'ring, F>(&'ring self, rng: F) -> Self::SuitableIdeal<'ring>
694                where F: FnMut() -> u64
695            {
696                let lower_bound = StaticRing::<i64>::RING.get_ring().get_uniformly_random_bits(24, rng);
697                return $crate::algorithms::miller_rabin::next_prime(StaticRing::<i64>::RING, lower_bound);
698            }
699        
700            fn base_ring_to_field<'ring>(&self, _ideal: &Self::SuitableIdeal<'ring>, from: &Self::LocalRingBase<'ring>, to: &Self::LocalFieldBase<'ring>, max_ideal_idx: usize, x: El<Self::LocalRing<'ring>>) -> El<Self::LocalField<'ring>>
701                where Self: 'ring
702            {
703                assert_eq!(0, max_ideal_idx);
704                assert_eq!(from.characteristic(StaticRing::<i64>::RING).unwrap(), to.characteristic(StaticRing::<i64>::RING).unwrap());
705                <_ as $crate::rings::zn::ZnRing>::from_int_promise_reduced(to, $crate::integer::int_cast(
706                    <_ as $crate::rings::zn::ZnRing>::smallest_positive_lift(from, x), 
707                    <_ as $crate::rings::zn::ZnRing>::integer_ring(to),
708                    <_ as $crate::rings::zn::ZnRing>::integer_ring(from),
709                ))
710            }
711
712            fn field_to_base_ring<'ring>(&self, _ideal: &Self::SuitableIdeal<'ring>, from: &Self::LocalFieldBase<'ring>, to: &Self::LocalRingBase<'ring>, max_ideal_idx: usize, x: El<Self::LocalField<'ring>>) -> El<Self::LocalRing<'ring>>
713                where Self: 'ring
714            {
715
716                assert_eq!(0, max_ideal_idx);
717                assert_eq!(from.characteristic(StaticRing::<i64>::RING).unwrap(), to.characteristic(StaticRing::<i64>::RING).unwrap());
718                <_ as $crate::rings::zn::ZnRing>::from_int_promise_reduced(to, $crate::integer::int_cast(
719                    <_ as $crate::rings::zn::ZnRing>::smallest_positive_lift(from, x), 
720                    <_ as $crate::rings::zn::ZnRing>::integer_ring(to),
721                    <_ as $crate::rings::zn::ZnRing>::integer_ring(from),
722                ))
723            }
724
725            fn reduce_ring_el<'ring>(&self, _p: &Self::SuitableIdeal<'ring>, to: (&Self::LocalRingBase<'ring>, usize), max_ideal_idx: usize, x: Self::Element) -> El<Self::LocalRing<'ring>>
726                where Self: 'ring
727            {
728                use $crate::homomorphism::*;
729
730                assert_eq!(0, max_ideal_idx);
731                let self_ref = RingRef::new(self);
732                let hom = RingRef::new(to.0).into_can_hom(&self_ref).ok().unwrap();
733                return hom.map(x);
734            }
735        
736            fn reduce_partial<'ring>(&self, _p: &Self::SuitableIdeal<'ring>, from: (&Self::LocalRingBase<'ring>, usize), to: (&Self::LocalRingBase<'ring>, usize), max_ideal_idx: usize, x: El<Self::LocalRing<'ring>>) -> El<Self::LocalRing<'ring>>
737                where Self: 'ring
738            {
739                use $crate::rings::zn::*;
740                use $crate::homomorphism::*;
741
742                assert_eq!(0, max_ideal_idx);
743                assert!(from.1 >= to.1);
744                let hom = RingRef::new(to.0).into_can_hom(to.0.integer_ring()).ok().unwrap();
745                return hom.map(from.0.smallest_lift(x));
746            }
747        
748            fn heuristic_exponent<'ring, 'a, I>(&self, p: &i64, poly_deg: usize, coefficients: I) -> usize
749                where I: Iterator<Item = &'a Self::Element>,
750                    Self: 'a,
751                    Self: 'ring
752            {
753                let log2_max_coeff = coefficients.map(|c| RingRef::new(self).abs_log2_ceil(c).unwrap_or(0)).max().unwrap_or(0);
754                // this is in no way a rigorous bound, but equals the worst-case bound at least asymptotically (up to constants)
755                return ((log2_max_coeff as f64 + poly_deg as f64) / (*p as f64).log2() * $crate::reduce_lift::poly_factor_gcd::INTRING_HEURISTIC_FACTOR_SIZE_OVER_POLY_SIZE_FACTOR).ceil() as usize + 1;
756            }
757            
758            fn dbg_ideal<'ring>(&self, p: &Self::SuitableIdeal<'ring>, out: &mut std::fmt::Formatter) -> std::fmt::Result
759                where Self: 'ring
760            {
761                write!(out, "({})", p)
762            }
763        }
764
765        impl<$($gen_args)*> $crate::reduce_lift::poly_factor_gcd::IntegerPolyGCDRing for $int_ring_type
766            where $($constraints)*
767        {
768            type LocalRingAsZnBase<'ring> = Self::LocalRingBase<'ring>
769                where Self: 'ring;
770
771            type LocalRingAsZn<'ring> = Self::LocalRing<'ring>
772                where Self: 'ring;
773
774            fn local_ring_as_zn<'a, 'ring>(&self, local_field: &'a Self::LocalRing<'ring>) -> &'a Self::LocalRingAsZn<'ring>
775                where Self: 'ring
776            {
777                local_field
778            }
779            
780            fn local_ring_into_zn<'ring>(&self, local_field: Self::LocalRing<'ring>) -> Self::LocalRingAsZn<'ring>
781                where Self: 'ring
782            {
783                local_field
784            }
785        }
786    };
787}
788
789///
790/// We cannot provide a blanket impl of [`crate::algorithms::poly_gcd::PolyTFracGCDRing`] for finite fields, since it would
791/// conflict with the one for all rings that impl [`PolyGCDLocallyDomain`]. Thus, we implement
792/// [`PolyGCDLocallyDomain`] for all finite fields, and reuse the blanket impl.
793/// 
794/// Note that while technically, finite fields are always [`PolyGCDLocallyDomain`] - where the
795/// local rings are all equal to itself - we still panic in the implementations. In particular,
796/// giving a working implementation would be "correct", but this implementation should never be
797/// called anyway, since we specialize on finite fields previously anyway.
798/// 
799#[allow(unused)]
800impl<R> PolyGCDLocallyDomain for R
801    where R: ?Sized + FiniteRing + FactorPolyField + Field + SelfIso
802{
803    type LocalRingBase<'ring> = Self
804        where Self: 'ring;
805    type LocalRing<'ring> = RingRef<'ring, Self>
806        where Self: 'ring;
807                
808    type LocalFieldBase<'ring> = Self
809        where Self: 'ring;
810    type LocalField<'ring> = RingRef<'ring, Self>
811        where Self: 'ring;
812    type SuitableIdeal<'ring> = RingRef<'ring, Self>
813        where Self: 'ring;
814        
815    fn heuristic_exponent<'ring, 'element, IteratorType>(&self, _maximal_ideal: &Self::SuitableIdeal<'ring>, _poly_deg: usize, _coefficients: IteratorType) -> usize
816        where IteratorType: Iterator<Item = &'element Self::Element>,
817            Self: 'element,
818            Self: 'ring
819    {
820        unreachable!("this should never be called for finite fields, since specialized functions are available in this case")
821    }
822
823    fn maximal_ideal_factor_count<'ring>(&self,ideal: &Self::SuitableIdeal<'ring>) -> usize where Self:'ring {
824        unreachable!("this should never be called for finite fields, since specialized functions are available in this case")
825    }
826
827    fn random_suitable_ideal<'ring, RandomNumberFunction>(&'ring self, rng: RandomNumberFunction) -> Self::SuitableIdeal<'ring>
828        where RandomNumberFunction: FnMut() -> u64
829    {
830        unreachable!("this should never be called for finite fields, since specialized functions are available in this case")
831    }
832
833    fn local_field_at<'ring>(&self, p: &Self::SuitableIdeal<'ring>, max_ideal_idx: usize) -> Self::LocalField<'ring>
834        where Self: 'ring
835    {
836        unreachable!("this should never be called for finite fields, since specialized functions are available in this case")
837    }
838                
839    fn local_ring_at<'ring>(&self, p: &Self::SuitableIdeal<'ring>, e: usize, max_ideal_idx: usize) -> Self::LocalRing<'ring>
840        where Self: 'ring
841    {
842        unreachable!("this should never be called for finite fields, since specialized functions are available in this case")
843    }
844
845    fn reduce_ring_el<'ring>(&self, p: &Self::SuitableIdeal<'ring>, to: (&Self::LocalRingBase<'ring>, usize), max_ideal_idx: usize, x: Self::Element) -> El<Self::LocalRing<'ring>>
846        where Self: 'ring
847    {
848        unreachable!("this should never be called for finite fields, since specialized functions are available in this case")
849    }
850
851    fn base_ring_to_field<'ring>(&self, _ideal: &Self::SuitableIdeal<'ring>, from: &Self::LocalRingBase<'ring>, to: &Self::LocalFieldBase<'ring>, max_ideal_idx: usize, x: El<Self::LocalRing<'ring>>) -> El<Self::LocalField<'ring>>
852        where Self: 'ring
853    {
854        unreachable!("this should never be called for finite fields, since specialized functions are available in this case")
855    }
856
857    fn field_to_base_ring<'ring>(&self, _ideal: &Self::SuitableIdeal<'ring>, from: &Self::LocalFieldBase<'ring>, to: &Self::LocalRingBase<'ring>, max_ideal_idx: usize, x: El<Self::LocalField<'ring>>) -> El<Self::LocalRing<'ring>>
858        where Self: 'ring
859    {
860        unreachable!("this should never be called for finite fields, since specialized functions are available in this case")
861    }
862
863    fn reduce_partial<'ring>(&self, p: &Self::SuitableIdeal<'ring>, from: (&Self::LocalRingBase<'ring>, usize), to: (&Self::LocalRingBase<'ring>, usize), max_ideal_idx: usize, x: El<Self::LocalRing<'ring>>) -> El<Self::LocalRing<'ring>>
864        where Self: 'ring
865    {
866        unreachable!("this should never be called for finite fields, since specialized functions are available in this case")
867    }
868
869    fn lift_partial<'ring>(&self, p: &Self::SuitableIdeal<'ring>, from: (&Self::LocalRingBase<'ring>, usize), to: (&Self::LocalRingBase<'ring>, usize), max_ideal_idx: usize, x: El<Self::LocalRing<'ring>>) -> El<Self::LocalRing<'ring>>
870        where Self: 'ring
871    {
872        unreachable!("this should never be called for finite fields, since specialized functions are available in this case")
873    }
874
875    fn reconstruct_ring_el<'local, 'element, 'ring, V1, V2>(&self, p: &Self::SuitableIdeal<'ring>, from: V1, e: usize, x: V2) -> Self::Element
876        where Self: 'ring, 
877            V1: VectorFn<&'local Self::LocalRing<'ring>>,
878            V2: VectorFn<&'element El<Self::LocalRing<'ring>>>,
879            'ring: 'local + 'element,
880            Self::LocalRing<'ring>: 'local,
881            El<Self::LocalRing<'ring>>: 'element
882    {
883        unreachable!("this should never be called for finite fields, since specialized functions are available in this case")
884    }
885    
886    fn dbg_ideal<'ring>(&self, p: &Self::SuitableIdeal<'ring>, out: &mut std::fmt::Formatter) -> std::fmt::Result
887        where Self: 'ring
888    {
889        unreachable!("this should never be called for finite fields, since specialized functions are available in this case")
890    }
891}
892
893#[stability::unstable(feature = "enable")]
894pub struct IntegersWithLocalZnQuotient<'a, R>
895    where R: Sized + SelfIso + ZnRing + FromModulusCreateableZnRing + LinSolveRing + Clone
896{
897    integers: &'a R::IntegerRing,
898    prime: El<R::IntegerRing>
899}
900
901impl<'a, R> IntegersWithLocalZnQuotient<'a, R>
902    where R: Sized + SelfIso + ZnRing + FromModulusCreateableZnRing + LinSolveRing + Clone
903{
904    #[stability::unstable(feature = "enable")]
905    pub fn new(integers: &'a R::IntegerRing, prime: El<R::IntegerRing>) -> Self {
906        assert!(is_prime(integers, &prime, 10));
907        return Self { integers, prime };
908    }
909
910    #[stability::unstable(feature = "enable")]
911    pub fn reduction_context<'b>(&'b self, from_e: usize) -> ReductionContext<'b, 'b, Self> {
912        ReductionContext {
913            ring: RingRef::new(self),
914            ideal: &self.prime,
915            from_e: from_e,
916            from: vec![self.local_ring_at(&self.prime, from_e, 0)], 
917            to: vec![self.local_ring_at(&self.prime, 1, 0)], 
918            to_fields: vec![self.local_field_at(&self.prime, 0)], 
919        }
920    }
921}
922
923impl<'a, R> Debug for IntegersWithLocalZnQuotient<'a, R>
924    where R: ?Sized + SelfIso + ZnRing + FromModulusCreateableZnRing + LinSolveRing + Clone,
925        R::IntegerRingBase: Debug
926{
927    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
928        f.debug_struct("IntegersWithLocalZnQuotient")
929            .field("integers", &self.integers.get_ring())
930            .finish()
931    }
932}
933
934impl<'a, R> PartialEq for IntegersWithLocalZnQuotient<'a, R>
935    where R: ?Sized + SelfIso + ZnRing + FromModulusCreateableZnRing + LinSolveRing + Clone
936{
937    fn eq(&self, other: &Self) -> bool {
938        self.integers.get_ring() == other.integers.get_ring()
939    }
940}
941
942impl<'a, R> DelegateRing for IntegersWithLocalZnQuotient<'a, R>
943    where R: Sized + SelfIso + ZnRing + FromModulusCreateableZnRing + LinSolveRing + Clone
944{
945    type Base = <R as ZnRing>::IntegerRingBase;
946    type Element = El<<R as ZnRing>::IntegerRing>;
947
948    fn get_delegate(&self) -> &Self::Base {
949        self.integers.get_ring()
950    }
951
952    fn delegate(&self, el: Self::Element) -> <Self::Base as RingBase>::Element { el }
953    fn delegate_mut<'b>(&self, el: &'b mut Self::Element) -> &'b mut <Self::Base as RingBase>::Element { el }
954    fn delegate_ref<'b>(&self, el: &'b Self::Element) -> &'b <Self::Base as RingBase>::Element { el }
955    fn rev_delegate(&self, el: <Self::Base as RingBase>::Element) -> Self::Element { el }
956}
957
958impl<'a, R> OrderedRing for IntegersWithLocalZnQuotient<'a, R>
959    where R: Sized + SelfIso + ZnRing + FromModulusCreateableZnRing + Clone
960{
961    fn cmp(&self, lhs: &Self::Element, rhs: &Self::Element) -> std::cmp::Ordering { self.get_delegate().cmp(self.delegate_ref(lhs), self.delegate_ref(rhs)) }
962    fn abs_cmp(&self, lhs: &Self::Element, rhs: &Self::Element) -> std::cmp::Ordering { self.get_delegate().abs_cmp(self.delegate_ref(lhs), self.delegate_ref(rhs)) }
963}
964
965impl<'a, R> Domain for IntegersWithLocalZnQuotient<'a, R>
966    where R: Sized + SelfIso + ZnRing + FromModulusCreateableZnRing + Clone
967{}
968
969impl<'a, R> DelegateRingImplFiniteRing for IntegersWithLocalZnQuotient<'a, R>
970    where R: Sized + SelfIso + ZnRing + FromModulusCreateableZnRing + Clone
971{}
972
973impl<'a, R> DelegateRingImplEuclideanRing for IntegersWithLocalZnQuotient<'a, R>
974    where R: Sized + SelfIso + ZnRing + FromModulusCreateableZnRing + Clone
975{}
976
977impl<'a, R> crate::reduce_lift::poly_eval::EvalPolyLocallyRing for IntegersWithLocalZnQuotient<'a, R>
978    where R: Sized + SelfIso + ZnRing + FromModulusCreateableZnRing + Clone
979{
980    type LocalRingBase<'ring> = <<Self as DelegateRing>::Base as crate::reduce_lift::poly_eval::EvalPolyLocallyRing>::LocalRingBase<'ring>
981        where Self: 'ring;
982    type LocalRing<'ring> = <<Self as DelegateRing>::Base as crate::reduce_lift::poly_eval::EvalPolyLocallyRing>::LocalRing<'ring>
983        where Self: 'ring;
984    type LocalComputationData<'ring> = <<Self as DelegateRing>::Base as crate::reduce_lift::poly_eval::EvalPolyLocallyRing>::LocalComputationData<'ring>
985        where Self:'ring;
986    
987    fn ln_pseudo_norm(&self, el: &Self::Element) -> f64 {
988        self.get_delegate().ln_pseudo_norm(self.delegate_ref(el))
989    }
990    
991    fn reduce<'ring>(&self, computation: &Self::LocalComputationData<'ring>, el: &Self::Element) -> Vec<<Self::LocalRingBase<'ring> as RingBase>::Element>
992        where Self: 'ring
993    {
994        self.get_delegate().reduce(computation, self.delegate_ref(el))
995    }
996
997    fn local_ring_count<'ring>(&self, computation: &Self::LocalComputationData<'ring>) -> usize
998        where Self: 'ring
999    {
1000        self.get_delegate().local_ring_count(computation)
1001    }
1002
1003    fn local_ring_at<'ring>(&self, computation: &Self::LocalComputationData<'ring>, i: usize) -> Self::LocalRing<'ring>
1004        where Self: 'ring
1005    {
1006        crate::reduce_lift::poly_eval::EvalPolyLocallyRing::local_ring_at(self.get_delegate(), computation, i)
1007    }
1008
1009    fn local_computation<'ring>(&'ring self, ln_pseudo_norm_bound: f64) -> Self::LocalComputationData<'ring> {
1010        self.get_delegate().local_computation(ln_pseudo_norm_bound)
1011    }
1012
1013    fn lift_combine<'ring>(&self, computation: &Self::LocalComputationData<'ring>, el: &[<Self::LocalRingBase<'ring> as RingBase>::Element]) -> Self::Element
1014        where Self: 'ring
1015    {
1016        self.rev_delegate(self.get_delegate().lift_combine(computation, el))
1017    }
1018}
1019
1020impl<'a, R> IntegerRing for IntegersWithLocalZnQuotient<'a, R>
1021    where R: Sized + SelfIso + ZnRing + FromModulusCreateableZnRing + Clone
1022{
1023    fn to_float_approx(&self, value: &Self::Element) -> f64 { self.get_delegate().to_float_approx(self.delegate_ref(self.rev_element_cast_ref(value))) }
1024    fn from_float_approx(&self, value: f64) -> Option<Self::Element> { self.get_delegate().from_float_approx(value).map(|x| self.element_cast(self.rev_delegate(x))) }
1025    fn abs_is_bit_set(&self, value: &Self::Element, i: usize) -> bool { self.get_delegate().abs_is_bit_set(self.delegate_ref(self.rev_element_cast_ref(value)), i) }
1026    fn abs_highest_set_bit(&self, value: &Self::Element) -> Option<usize> { self.get_delegate().abs_highest_set_bit(self.delegate_ref(self.rev_element_cast_ref(value))) }
1027    fn abs_lowest_set_bit(&self, value: &Self::Element) -> Option<usize> { self.get_delegate().abs_lowest_set_bit(self.delegate_ref(self.rev_element_cast_ref(value))) }
1028    fn get_uniformly_random_bits<G: FnMut() -> u64>(&self, log2_bound_exclusive: usize, rng: G) -> Self::Element { self.element_cast(self.rev_delegate(self.get_delegate().get_uniformly_random_bits(log2_bound_exclusive, rng))) }
1029    fn rounded_div(&self, lhs: Self::Element, rhs: &Self::Element) -> Self::Element { self.element_cast(self.rev_delegate(self.get_delegate().rounded_div(self.delegate(self.rev_element_cast(lhs)), self.delegate_ref(self.rev_element_cast_ref(rhs))))) }
1030    fn ceil_div(&self, lhs: Self::Element, rhs: &Self::Element) -> Self::Element { self.element_cast(self.rev_delegate(self.get_delegate().ceil_div(self.delegate(self.rev_element_cast(lhs)), self.delegate_ref(self.rev_element_cast_ref(rhs))))) } 
1031    fn floor_div(&self, lhs: Self::Element, rhs: &Self::Element) -> Self::Element { self.element_cast(self.rev_delegate(self.get_delegate().floor_div(self.delegate(self.rev_element_cast(lhs)), self.delegate_ref(self.rev_element_cast_ref(rhs))))) }
1032    fn power_of_two(&self, power: usize) -> Self::Element { self.element_cast(self.rev_delegate(self.get_delegate().power_of_two(power))) }
1033    fn representable_bits(&self) -> Option<usize> { self.get_delegate().representable_bits() }
1034    fn parse(&self, string: &str, base: u32) -> Result<Self::Element, ()> { self.get_delegate().parse(string, base).map(|x| self.element_cast(self.rev_delegate(x))) }
1035
1036    fn euclidean_div_pow_2(&self, value: &mut Self::Element, power: usize) {
1037        self.get_delegate().euclidean_div_pow_2(self.delegate_mut(self.rev_element_cast_mut(value)), power);
1038        self.postprocess_delegate_mut(self.rev_element_cast_mut(value));
1039    }
1040
1041    fn mul_pow_2(&self, value: &mut Self::Element, power: usize) {
1042        self.get_delegate().mul_pow_2(self.delegate_mut(self.rev_element_cast_mut(value)), power);
1043        self.postprocess_delegate_mut(self.rev_element_cast_mut(value));
1044    }
1045}
1046
1047impl<'a, R> PolyGCDLocallyDomain for IntegersWithLocalZnQuotient<'a, R>
1048    where R: Sized + SelfIso + ZnRing + FromModulusCreateableZnRing + LinSolveRing + Clone
1049{
1050    type LocalRingBase<'ring> = R
1051        where Self: 'ring;
1052
1053    type LocalRing<'ring> = RingValue<R>
1054        where Self: 'ring;
1055    
1056    type LocalFieldBase<'ring> = AsFieldBase<RingValue<R>>
1057        where Self: 'ring;
1058
1059    type LocalField<'ring> = AsField<RingValue<R>>
1060        where Self: 'ring;
1061
1062    type SuitableIdeal<'ring> = Self::Element
1063        where Self: 'ring;
1064
1065    fn heuristic_exponent<'ring, 'el, I>(&self, ideal: &Self::SuitableIdeal<'ring>, poly_deg: usize, coefficients: I) -> usize
1066        where I: Iterator<Item = &'el Self::Element>,
1067            Self: 'el + 'ring
1068    {
1069        let log2_max_coeff = coefficients.map(|c| self.integers.abs_log2_ceil(c).unwrap_or(0)).max().unwrap_or(0);
1070        // this is in no way a rigorous bound, but equals the worst-case bound at least asymptotically (up to constants)
1071        return ((log2_max_coeff as f64 + poly_deg as f64) / self.integers.abs_log2_floor(ideal).unwrap_or(1) as f64 * crate::reduce_lift::poly_factor_gcd::INTRING_HEURISTIC_FACTOR_SIZE_OVER_POLY_SIZE_FACTOR).ceil() as usize + 1;
1072    }
1073
1074    fn random_suitable_ideal<'ring, F>(&'ring self, _rng: F) -> Self::SuitableIdeal<'ring>
1075        where F: FnMut() -> u64
1076    {
1077        self.integers.clone_el(&self.prime)
1078    }
1079
1080    fn maximal_ideal_factor_count<'ring>(&self, ideal: &Self::SuitableIdeal<'ring>) -> usize
1081        where Self: 'ring
1082    {
1083        debug_assert!(self.integers.eq_el(ideal, &self.prime));
1084        1
1085    }
1086
1087    fn local_field_at<'ring>(&self, ideal: &Self::SuitableIdeal<'ring>, max_ideal_idx: usize) -> Self::LocalField<'ring>
1088        where Self: 'ring
1089    {
1090        assert_eq!(0, max_ideal_idx);
1091        self.local_ring_at(ideal, 1, 0).as_field().ok().unwrap()
1092    }
1093    
1094    fn local_ring_at<'ring>(&self, ideal: &Self::SuitableIdeal<'ring>, e: usize, max_ideal_idx: usize) -> Self::LocalRing<'ring>
1095        where Self: 'ring
1096    {
1097        assert_eq!(0, max_ideal_idx);
1098        assert!(self.integers.eq_el(ideal, &self.prime));
1099        RingValue::from(R::from_modulus(|ZZ| Ok(RingRef::new(ZZ).pow(int_cast(self.integers.clone_el(&self.prime), RingRef::new(ZZ), &self.integers), e))).unwrap_or_else(no_error))
1100    }
1101
1102    fn reduce_ring_el<'ring>(&self, ideal: &Self::SuitableIdeal<'ring>, to: (&Self::LocalRingBase<'ring>, usize), max_ideal_idx: usize, x: Self::Element) -> El<Self::LocalRing<'ring>>
1103        where Self: 'ring
1104    {
1105        debug_assert_eq!(0, max_ideal_idx);
1106        debug_assert!(self.integers.eq_el(ideal, &self.prime));
1107        debug_assert!(self.integers.eq_el(&self.integers.pow(self.integers.clone_el(&self.prime), to.1), to.0.modulus()));
1108        RingRef::new(to.0).coerce(&self.integers, x)
1109    }
1110
1111    fn reduce_partial<'ring>(&self, ideal: &Self::SuitableIdeal<'ring>, from: (&Self::LocalRingBase<'ring>, usize), to: (&Self::LocalRingBase<'ring>, usize), max_ideal_idx: usize, x: El<Self::LocalRing<'ring>>) -> El<Self::LocalRing<'ring>>
1112        where Self: 'ring
1113    {
1114        debug_assert_eq!(0, max_ideal_idx);
1115        debug_assert!(self.integers.eq_el(ideal, &self.prime));
1116        debug_assert!(self.integers.eq_el(&self.integers.pow(self.integers.clone_el(&self.prime), to.1), to.0.modulus()));
1117        debug_assert!(self.integers.eq_el(&self.integers.pow(self.integers.clone_el(&self.prime), from.1), from.0.modulus()));
1118        RingRef::new(to.0).coerce(&self.integers, from.0.smallest_positive_lift(x))
1119    }
1120
1121    fn lift_partial<'ring>(&self, ideal: &Self::SuitableIdeal<'ring>, from: (&Self::LocalRingBase<'ring>, usize), to: (&Self::LocalRingBase<'ring>, usize), max_ideal_idx: usize, x: El<Self::LocalRing<'ring>>) -> El<Self::LocalRing<'ring>>
1122        where Self: 'ring
1123    {
1124        debug_assert_eq!(0, max_ideal_idx);
1125        debug_assert!(self.integers.eq_el(ideal, &self.prime));
1126        debug_assert!(self.integers.eq_el(&self.integers.pow(self.integers.clone_el(&self.prime), to.1), to.0.modulus()));
1127        debug_assert!(self.integers.eq_el(&self.integers.pow(self.integers.clone_el(&self.prime), from.1), from.0.modulus()));
1128        RingRef::new(to.0).coerce(&self.integers, from.0.smallest_positive_lift(x))
1129    }
1130
1131    fn base_ring_to_field<'ring>(&self, _ideal: &Self::SuitableIdeal<'ring>, from: &Self::LocalRingBase<'ring>, to: &Self::LocalFieldBase<'ring>, max_ideal_idx: usize, x: El<Self::LocalRing<'ring>>) -> El<Self::LocalField<'ring>>
1132        where Self: 'ring
1133    {
1134        debug_assert_eq!(0, max_ideal_idx);
1135        assert!(from == to.get_delegate());
1136        to.element_cast(to.rev_delegate(x))
1137    }
1138
1139    fn field_to_base_ring<'ring>(&self, _ideal: &Self::SuitableIdeal<'ring>, from: &Self::LocalFieldBase<'ring>, to: &Self::LocalRingBase<'ring>, max_ideal_idx: usize, x: El<Self::LocalField<'ring>>) -> El<Self::LocalRing<'ring>>
1140        where Self: 'ring
1141    {
1142        debug_assert_eq!(0, max_ideal_idx);
1143        assert!(to == from.get_delegate());
1144        from.delegate(from.rev_element_cast(x))
1145    }
1146
1147    fn reconstruct_ring_el<'local, 'element, 'ring, V1, V2>(&self, ideal: &Self::SuitableIdeal<'ring>, from: V1, e: usize, x: V2) -> Self::Element
1148        where Self: 'ring, 
1149            V1: VectorFn<&'local Self::LocalRing<'ring>>,
1150            V2: VectorFn<&'element El<Self::LocalRing<'ring>>>,
1151            Self::LocalRing<'ring>: 'local,
1152            El<Self::LocalRing<'ring>>: 'element,
1153            'ring: 'local + 'element
1154    {
1155        assert_eq!(1, x.len());
1156        assert_eq!(1, from.len());
1157        debug_assert!(self.integers.eq_el(ideal, &self.prime));
1158        debug_assert!(self.integers.eq_el(&self.integers.pow(self.integers.clone_el(&self.prime), e), from.at(0).modulus()));
1159        from.at(0).smallest_lift(from.at(0).clone_el(x.at(0)))
1160    }
1161
1162    fn dbg_ideal<'ring>(&self, ideal: &Self::SuitableIdeal<'ring>, out: &mut std::fmt::Formatter) -> std::fmt::Result
1163        where Self: 'ring
1164    {
1165        self.dbg(ideal, out)
1166    }
1167}
1168
1169impl<'a, R> IntegerPolyGCDRing for IntegersWithLocalZnQuotient<'a, R>
1170    where R: Sized + SelfIso + ZnRing + FromModulusCreateableZnRing + LinSolveRing + Clone
1171{
1172    type LocalRingAsZn<'ring> = Self::LocalRing<'ring>
1173        where Self:'ring;
1174    type LocalRingAsZnBase<'ring> = Self::LocalRingBase<'ring>
1175        where Self:'ring;
1176
1177    fn local_ring_as_zn<'b, 'ring>(&self, local_field: &'b Self::LocalRing<'ring>) -> &'b Self::LocalRingAsZn<'ring>
1178        where Self: 'ring
1179    {
1180        local_field
1181    }
1182
1183    fn local_ring_into_zn<'ring>(&self, local_field: Self::LocalRing<'ring>) -> Self::LocalRingAsZn<'ring>
1184        where Self: 'ring
1185    {
1186        local_field
1187    }
1188}
feanor_math/reduce_lift/poly_factor_gcd.rs

feanor_math/reduce_lift/
poly_factor_gcd.rs
