feanor_math/reduce_lift/
poly_factor_gcd.rs

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

feanor_math/reduce_lift/
poly_factor_gcd.rs
