feanor_math/algorithms/poly_gcd/
local.rs

1use std::fmt::Display;
2
3use crate::algorithms::linsolve::LinSolveRing;
4use crate::algorithms::miller_rabin::is_prime;
5use crate::computation::no_error;
6use crate::delegate::DelegateRing;
7use crate::delegate::DelegateRingImplFiniteRing;
8use crate::divisibility::*;
9use crate::homomorphism::*;
10use crate::local::PrincipalLocalRing;
11use crate::primitive_int::StaticRing;
12use crate::integer::*;
13use crate::ring::*;
14use crate::rings::zn::*;
15use crate::seq::*;
16use crate::specialization::FiniteRingSpecializable;
17
18use super::AsField;
19use super::AsFieldBase;
20use super::Field;
21use super::FiniteRing;
22
23///
24/// Trait for rings that support lifting partial factorizations of polynomials modulo a prime
25/// to the ring. For infinite fields, this is the most important approach to computing gcd's,
26/// and also factorizations (with some caveats...).
27/// 
28/// Note that here (and in `feanor-math` generally), the term "local" is used to refer to algorithms
29/// that work modulo prime ideals (or their powers), which is different from the mathematical concept
30/// of localization.
31/// 
32/// The general philosophy is similar to [`crate::compute_locally::EvaluatePolyLocallyRing`].
33/// However, when working with factorizations, it is usually better to compute modulo the factorization
34/// modulo an ideal `I`, and use Hensel lifting to derive the factorization modulo `I^e`.
35/// `EvaluatePolyLocallyRing` on the other hand is designed to allow computations modulo multiple different 
36/// maximal ideals.
37/// 
38/// I am currently not yet completely sure what the exact requirements of this trait would be,
39/// but conceptually, we want that for a random ideal `I` taken from some set of ideals (e.g. maximal
40/// ideals, prime ideals, ... depending on the context), the quotient `R / I` should be
41/// finite, and there should be a power `e` such that we can derive the factorization of some polynomial
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#[stability::unstable(feature = "enable")]
84pub trait PolyGCDLocallyDomain: Domain + DivisibilityRing + FiniteRingSpecializable {
85
86    ///
87    /// The proper way would be to define this with two lifetime parameters `'ring` and `'data`,
88    /// see also [`crate::compute_locally::EvaluatePolyLocallyRing::LocalRingBase`]
89    /// 
90    type LocalRingBase<'ring>: ?Sized + LinSolveRing
91        where Self: 'ring;
92
93    type LocalRing<'ring>: RingStore<Type = Self::LocalRingBase<'ring>>
94        where Self: 'ring;
95    
96    type LocalFieldBase<'ring>: ?Sized + CanIsoFromTo<Self::LocalRingBase<'ring>> + FiniteRing + Field + SelfIso
97        where Self: 'ring;
98
99    type LocalField<'ring>: RingStore<Type = Self::LocalFieldBase<'ring>>
100        where Self: 'ring;
101
102    type SuitableIdeal<'ring>
103        where Self: 'ring;
104
105    ///
106    /// Returns an exponent `e` such that we hope that the factors of a polynomial of given degree, 
107    /// involving the given coefficient can already be read of (via [`PolyGCDLocallyDomain::reconstruct_ring_el()`]) 
108    /// their reductions modulo `I^e`. Note that this is just a heuristic, and if it does not work,
109    /// the implementation will gradually try larger `e`. Thus, even if this function returns constant
110    /// 1, correctness will not be affected, but giving a good guess can improve performance
111    /// 
112    fn heuristic_exponent<'ring, 'a, I>(&self, _ideal: &Self::SuitableIdeal<'ring>, _poly_deg: usize, _coefficients: I) -> usize
113        where I: Iterator<Item = &'a Self::Element>,
114            Self: 'a,
115            Self: 'ring;
116
117    ///
118    /// Returns an ideal sampled at random from the interval of all supported ideals.
119    /// 
120    fn random_suitable_ideal<'ring, F>(&'ring self, rng: F) -> Self::SuitableIdeal<'ring>
121        where F: FnMut() -> u64;
122
123    fn maximal_ideal_factor_count<'ring>(&self, ideal: &Self::SuitableIdeal<'ring>) -> usize
124        where Self: 'ring;
125
126    ///
127    /// Returns `R / mi`, where `mi` is the `i`-th maximal ideal over `I`.
128    /// 
129    /// This will always be a field, since `mi` is a maximal ideal.
130    /// 
131    fn local_field_at<'ring>(&self, ideal: &Self::SuitableIdeal<'ring>, max_ideal_idx: usize) -> Self::LocalField<'ring>
132        where Self: 'ring;
133    
134    ///
135    /// Returns `R / mi^e`, where `mi` is the `i`-th maximal ideal over `I`.
136    /// 
137    fn local_ring_at<'ring>(&self, ideal: &Self::SuitableIdeal<'ring>, e: usize, max_ideal_idx: usize) -> Self::LocalRing<'ring>
138        where Self: 'ring;
139
140    ///
141    /// Computes the reduction map
142    /// ```text
143    ///   R -> R / mi^e
144    /// ```
145    /// where `mi` is the `i`-th maximal ideal over `I`.
146    /// 
147    fn reduce_ring_el<'ring>(&self, ideal: &Self::SuitableIdeal<'ring>, to: (&Self::LocalRing<'ring>, usize), max_ideal_idx: usize, x: Self::Element) -> El<Self::LocalRing<'ring>>
148        where Self: 'ring;
149
150    ///
151    /// Computes the reduction map
152    /// ```text
153    ///   R / mi^e1 -> R / mi^e2
154    /// ```
155    /// where `e1 >= e2` and `mi` is the `i`-th maximal ideal over `I`.
156    /// 
157    fn reduce_partial<'ring>(&self, ideal: &Self::SuitableIdeal<'ring>, from: (&Self::LocalRing<'ring>, usize), to: (&Self::LocalRing<'ring>, usize), max_ideal_idx: usize, x: El<Self::LocalRing<'ring>>) -> El<Self::LocalRing<'ring>>
158        where Self: 'ring;
159
160    ///
161    /// Computes any element `y` in `R / mi^to_e` such that `y = x mod mi^from_e`.
162    /// In particular, `y` does not have to be "short" in any sense, but any lift
163    /// is a valid result.
164    /// 
165    fn lift_partial<'ring>(&self, ideal: &Self::SuitableIdeal<'ring>, from: (&Self::LocalRing<'ring>, usize), to: (&Self::LocalRing<'ring>, usize), max_ideal_idx: usize, x: El<Self::LocalRing<'ring>>) -> El<Self::LocalRing<'ring>>
166        where Self: 'ring;
167
168    ///
169    /// Computes a "small" element `x in R` such that `x mod mi^e` is equal to the given value,
170    /// for every maximal ideal `mi` over `I`.
171    /// In cases where the factors of polynomials in `R[X]` do not necessarily have coefficients
172    /// in `R`, this function might have to do rational reconstruction. 
173    /// 
174    fn reconstruct_ring_el<'local, 'element, 'ring, V1, V2>(&self, ideal: &Self::SuitableIdeal<'ring>, from: V1, e: usize, x: V2) -> Self::Element
175        where Self: 'ring, 
176            V1: VectorFn<&'local Self::LocalRing<'ring>>,
177            V2: VectorFn<&'element El<Self::LocalRing<'ring>>>,
178            Self::LocalRing<'ring>: 'local,
179            El<Self::LocalRing<'ring>>: 'element,
180            'ring: 'local + 'element;
181
182    fn dbg_ideal<'ring>(&self, ideal: &Self::SuitableIdeal<'ring>, out: &mut std::fmt::Formatter) -> std::fmt::Result
183        where Self: 'ring;
184}
185
186///
187/// Subtrait of [`PolyGCDLocallyDomain`] that restricts the local rings to be [`ZnRing`],
188/// which is necessary when implementing some base cases.
189/// 
190#[stability::unstable(feature = "enable")]
191pub trait IntegerPolyGCDRing: PolyGCDLocallyDomain {
192
193    ///
194    /// It would be much preferrable if we could restrict associated types from supertraits,
195    /// this is just a workaround (and an ugly one at that)
196    /// 
197    type LocalRingAsZnBase<'ring>: ?Sized + CanIsoFromTo<Self::LocalRingBase<'ring>> + ZnRing
198        where Self: 'ring;
199
200    type LocalRingAsZn<'ring>: RingStore<Type = Self::LocalRingAsZnBase<'ring>>
201        where Self: 'ring;
202
203    fn local_ring_as_zn<'a, 'ring>(&self, local_field: &'a Self::LocalRing<'ring>) -> &'a Self::LocalRingAsZn<'ring>;
204
205    fn principal_ideal_generator<'ring>(&self, p: &Self::SuitableIdeal<'ring>) -> i64
206        where Self: 'ring
207    {
208        assert_eq!(1, self.maximal_ideal_factor_count(p));
209        let Fp = self.local_ring_at(p, 1, 0);
210        let Fp = self.local_ring_as_zn(&Fp);
211        return int_cast(Fp.integer_ring().clone_el(Fp.modulus()), StaticRing::<i64>::RING, Fp.integer_ring());
212    }
213}
214
215#[stability::unstable(feature = "enable")]
216pub struct IdealDisplayWrapper<'a, 'ring, R: 'ring + ?Sized + PolyGCDLocallyDomain> {
217    ring: &'a R,
218    ideal: &'a R::SuitableIdeal<'ring>
219}
220
221impl<'a, 'ring, R: 'ring + ?Sized + PolyGCDLocallyDomain> IdealDisplayWrapper<'a, 'ring, R> {
222
223    #[stability::unstable(feature = "enable")]
224    pub fn new(ring: &'a R, ideal: &'a R::SuitableIdeal<'ring>) -> Self {
225        Self {
226            ring: ring, 
227            ideal: ideal
228        }
229    }
230}
231
232impl<'a, 'ring, R: 'ring + ?Sized + PolyGCDLocallyDomain> Display for IdealDisplayWrapper<'a, 'ring, R> {
233
234    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
235        self.ring.dbg_ideal(self.ideal, f)
236    }
237}
238
239///
240/// The map `R -> R/m^e`, where `m` is a maximal ideal factor of the ideal `I`,
241/// as specified by [`PolyGCDLocallyDomain`].
242/// 
243#[stability::unstable(feature = "enable")]
244pub struct PolyGCDLocallyReductionMap<'ring, 'data, 'local, R>
245    where R: 'ring + ?Sized + PolyGCDLocallyDomain, 'ring: 'data
246{
247    ring: RingRef<'data, R>,
248    ideal: &'data R::SuitableIdeal<'ring>,
249    to: (&'local R::LocalRing<'ring>, usize),
250    max_ideal_idx: usize
251}
252
253impl<'ring, 'data, 'local, R> PolyGCDLocallyReductionMap<'ring, 'data, 'local, R>
254    where R: 'ring +?Sized + PolyGCDLocallyDomain, 'ring: 'data
255{
256    #[stability::unstable(feature = "enable")]
257    pub fn new(ring: &'data R, ideal: &'data R::SuitableIdeal<'ring>, to: &'local R::LocalRing<'ring>, to_e: usize, max_ideal_idx: usize) -> Self {
258        assert!(to.get_ring() == ring.local_ring_at(ideal, to_e, max_ideal_idx).get_ring());
259        Self {
260            ring: RingRef::new(ring),
261            ideal: ideal,
262            to: (to, to_e),
263            max_ideal_idx: max_ideal_idx
264        }
265    }
266}
267
268impl<'ring, 'data, 'local, R> Homomorphism<R, R::LocalRingBase<'ring>> for PolyGCDLocallyReductionMap<'ring, 'data, 'local, R>
269    where R: 'ring +?Sized + PolyGCDLocallyDomain, 'ring: 'data
270{
271    type CodomainStore = &'local R::LocalRing<'ring>;
272    type DomainStore = RingRef<'data, R>;
273
274    fn codomain<'b>(&'b self) -> &'b Self::CodomainStore {
275        &self.to.0
276    }
277
278    fn domain<'b>(&'b self) -> &'b Self::DomainStore {
279        &self.ring
280    }
281
282    fn map(&self, x: <R as RingBase>::Element) -> <R::LocalRingBase<'ring> as RingBase>::Element {
283        self.ring.get_ring().reduce_ring_el(self.ideal, (&self.to.0, self.to.1), self.max_ideal_idx, x)
284    }
285}
286
287///
288/// The map `R/m^r -> R/m^e`, where `r > e` and `m` is a maximal ideal factor of the 
289/// ideal `I`, as specified by [`PolyGCDLocallyDomain`].
290/// 
291#[stability::unstable(feature = "enable")]
292pub struct PolyGCDLocallyIntermediateReductionMap<'ring, 'data, 'local, R>
293    where R: 'ring + ?Sized + PolyGCDLocallyDomain, 'ring: 'data
294{
295    ring: RingRef<'data, R>,
296    ideal: &'data R::SuitableIdeal<'ring>,
297    from: (&'local R::LocalRing<'ring>, usize),
298    to: (&'local R::LocalRing<'ring>, usize),
299    max_ideal_idx: usize
300}
301
302impl<'ring, 'data, 'local, R> PolyGCDLocallyIntermediateReductionMap<'ring, 'data, 'local, R>
303    where R: 'ring + ?Sized + PolyGCDLocallyDomain, 'ring: 'data
304{
305    #[stability::unstable(feature = "enable")]
306    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 {
307        assert!(ring.local_ring_at(ideal, from_e, max_ideal_idx).get_ring() == from.get_ring());
308        assert!(ring.local_ring_at(ideal, to_e, max_ideal_idx).get_ring() == to.get_ring());
309        Self {
310            ring: RingRef::new(ring),
311            ideal: ideal,
312            from: (from, from_e),
313            to: (to, to_e),
314            max_ideal_idx: max_ideal_idx
315        }
316    }
317
318    #[stability::unstable(feature = "enable")]
319    pub fn parent_ring<'a>(&'a self) -> RingRef<'a, R> {
320        RingRef::new(self.ring.get_ring())
321    }
322
323    #[stability::unstable(feature = "enable")]
324    pub fn from_e(&self) -> usize {
325        self.from.1
326    }
327
328    #[stability::unstable(feature = "enable")]
329    pub fn to_e(&self) -> usize {
330        self.to.1
331    }
332
333    #[stability::unstable(feature = "enable")]
334    pub fn ideal<'a>(&'a self) -> &'a R::SuitableIdeal<'ring> {
335        &self.ideal
336    }
337
338    #[stability::unstable(feature = "enable")]
339    pub fn max_ideal_idx(&self) -> usize {
340        self.max_ideal_idx
341    }
342}
343
344impl<'ring, 'data, 'local, R> Homomorphism<R::LocalRingBase<'ring>, R::LocalRingBase<'ring>> for PolyGCDLocallyIntermediateReductionMap<'ring, 'data, 'local, R>
345    where R: 'ring + ?Sized + PolyGCDLocallyDomain, 'ring: 'data
346{
347    type CodomainStore = &'local R::LocalRing<'ring>;
348    type DomainStore = &'local R::LocalRing<'ring>;
349
350    fn codomain<'b>(&'b self) -> &'b Self::CodomainStore {
351        &self.to.0
352    }
353
354    fn domain<'b>(&'b self) -> &'b Self::DomainStore {
355        &self.from.0
356    }
357
358    fn map(&self, x: <R::LocalRingBase<'ring> as RingBase>::Element) -> <R::LocalRingBase<'ring> as RingBase>::Element {
359        self.ring.get_ring().reduce_partial(self.ideal, (&self.from.0, self.from.1), (&self.to.0, self.to.1), self.max_ideal_idx, x)
360    }
361}
362
363///
364/// The sequence of maps `R  ->  R/m1^e x ... x R/mr^e  ->  R/m1 x ... x R/mr`, where
365/// `m1, ..., mr` are the maximal ideals containing `I`, as specified by [`PolyGCDLocallyDomain`].
366/// 
367/// This sequence of maps is very relevant when using the compute-mod-p-and-lift approach
368/// for polynomial operations over infinite rings (e.g. `QQ`). This is also the primary use case
369/// for [`ReductionContext`].
370///
371#[stability::unstable(feature = "enable")]
372pub struct ReductionContext<'ring, 'data, R>
373    where R: 'ring + ?Sized + PolyGCDLocallyDomain, 'ring: 'data
374{
375    ring: RingRef<'data, R>,
376    ideal: &'data R::SuitableIdeal<'ring>,
377    from_e: usize,
378    from: Vec<R::LocalRing<'ring>>,
379    to: Vec<R::LocalRing<'ring>>
380}
381
382impl<'ring, 'data, R> ReductionContext<'ring, 'data, R>
383    where R: 'ring + ?Sized + PolyGCDLocallyDomain, 'ring: 'data
384{
385    #[stability::unstable(feature = "enable")]
386    pub fn new(ring: &'data R, ideal: &'data R::SuitableIdeal<'ring>, e: usize) -> Self {
387        assert!(e >= 1);
388        let maximal_ideal_factor_count = ring.maximal_ideal_factor_count(ideal);
389        Self {
390            ring: RingRef::new(ring), 
391            ideal: ideal, 
392            from_e: e,
393            from: (0..maximal_ideal_factor_count).map(|idx| ring.local_ring_at(ideal, e, idx)).collect::<Vec<_>>(), 
394            to: (0..maximal_ideal_factor_count).map(|idx| ring.local_ring_at(ideal, 1, idx)).collect::<Vec<_>>(),
395        }
396    }
397    
398    #[stability::unstable(feature = "enable")]
399    pub fn ideal(&self) -> &'data R::SuitableIdeal<'ring> {
400        self.ideal
401    }
402
403    #[stability::unstable(feature = "enable")]
404    pub fn main_ring_to_field_reduction<'local>(&'local self, max_ideal_idx: usize) -> PolyGCDLocallyReductionMap<'ring, 'data, 'local, R> {
405        PolyGCDLocallyReductionMap {
406            ideal: self.ideal,
407            ring: self.ring,
408            to: (self.to.at(max_ideal_idx), 1),
409            max_ideal_idx: max_ideal_idx
410        }
411    }
412
413    #[stability::unstable(feature = "enable")]
414    pub fn main_ring_to_intermediate_ring_reduction<'local>(&'local self, max_ideal_idx: usize) -> PolyGCDLocallyReductionMap<'ring, 'data, 'local, R> {
415        PolyGCDLocallyReductionMap {
416            ideal: self.ideal,
417            ring: self.ring,
418            to: (self.from.at(max_ideal_idx), self.from_e),
419            max_ideal_idx: max_ideal_idx
420        }
421    }
422
423    #[stability::unstable(feature = "enable")]
424    pub fn intermediate_ring_to_field_reduction<'local>(&'local self, max_ideal_idx: usize) -> PolyGCDLocallyIntermediateReductionMap<'ring, 'data, 'local, R> {
425        PolyGCDLocallyIntermediateReductionMap {
426            from: (&self.from[max_ideal_idx], self.from_e),
427            to: (&self.to[max_ideal_idx], 1),
428            max_ideal_idx: max_ideal_idx,
429            ring: self.ring,
430            ideal: self.ideal
431        }
432    }
433
434
435    #[stability::unstable(feature = "enable")]
436    pub fn len(&self) -> usize {
437        self.from.len()
438    }
439
440    #[stability::unstable(feature = "enable")]
441    pub fn reconstruct_ring_el<'local, V>(&self, els: V) -> R::Element
442        where V: VectorFn<&'local El<R::LocalRing<'ring>>>,
443            El<R::LocalRing<'ring>>: 'local,
444            'ring: 'local
445    {
446        fn do_reconstruction<'ring, 'local, R, V>(ring: &R, ideal: &R::SuitableIdeal<'ring>, local_rings: &[R::LocalRing<'ring>], e: usize, els: V) -> R::Element
447            where R: 'ring + ?Sized + PolyGCDLocallyDomain,
448                V: VectorFn<&'local El<R::LocalRing<'ring>>>,
449                El<R::LocalRing<'ring>>: 'local,
450                'ring: 'local
451        {
452            ring.reconstruct_ring_el(ideal, local_rings.as_fn(), e, els)
453        }
454        do_reconstruction(self.ring.get_ring(), self.ideal, &self.from[..], self.from_e, els)
455    }
456}
457
458#[stability::unstable(feature = "enable")]
459pub const INTRING_HEURISTIC_FACTOR_SIZE_OVER_POLY_SIZE_FACTOR: f64 = 0.25;
460
461#[macro_export]
462macro_rules! impl_poly_gcd_locally_for_ZZ {
463    (IntegerPolyGCDRing for $int_ring_type:ty) => {
464        impl_poly_gcd_locally_for_ZZ!{ <{}> IntegerPolyGCDRing for $int_ring_type where }
465    };
466    (<{$($gen_args:tt)*}> IntegerPolyGCDRing for $int_ring_type:ty where $($constraints:tt)*) => {
467
468        impl<$($gen_args)*> $crate::algorithms::poly_gcd::local::PolyGCDLocallyDomain for $int_ring_type
469            where $($constraints)*
470        {
471            type LocalRing<'ring> = $crate::rings::zn::zn_big::Zn<BigIntRing>
472                where Self: 'ring;
473            type LocalRingBase<'ring> = $crate::rings::zn::zn_big::ZnBase<BigIntRing>
474                where Self: 'ring;
475            type LocalFieldBase<'ring> = $crate::rings::field::AsFieldBase<$crate::rings::zn::zn_64::Zn>
476                where Self: 'ring;
477            type LocalField<'ring> = $crate::rings::field::AsField<$crate::rings::zn::zn_64::Zn>
478                where Self: 'ring;
479            type SuitableIdeal<'ring> = i64
480                where Self: 'ring;
481        
482            fn reconstruct_ring_el<'local, 'element, 'ring, V1, V2>(&self, _p: &Self::SuitableIdeal<'ring>, from: V1, _e: usize, x: V2) -> Self::Element
483                where Self: 'ring,
484                    V1: $crate::seq::VectorFn<&'local Self::LocalRing<'ring>>,
485                    V2: $crate::seq::VectorFn<&'element El<Self::LocalRing<'ring>>>
486            {
487                use $crate::rings::zn::*;
488                #[allow(unused)]
489                use $crate::seq::*;
490                assert_eq!(1, from.len());
491                assert_eq!(1, x.len());
492                int_cast(from.at(0).smallest_lift(from.at(0).clone_el(x.at(0))), RingRef::new(self), BigIntRing::RING)
493            }
494
495            fn maximal_ideal_factor_count<'ring>(&self, _p: &Self::SuitableIdeal<'ring>) -> usize
496                where Self: 'ring
497            {
498                1
499            }
500        
501            fn lift_partial<'ring>(&self, _p: &Self::SuitableIdeal<'ring>, from: (&Self::LocalRing<'ring>, usize), to: (&Self::LocalRing<'ring>, usize), max_ideal_idx: usize, x: El<Self::LocalRing<'ring>>) -> El<Self::LocalRing<'ring>>
502                where Self: 'ring
503            {
504                use $crate::rings::zn::*;
505                use $crate::homomorphism::*;
506
507                assert_eq!(0, max_ideal_idx);
508                assert!(from.1 <= to.1);
509                let hom = to.0.can_hom(to.0.integer_ring()).unwrap();
510                return hom.map(from.0.any_lift(x));
511            }
512        
513            fn local_field_at<'ring>(&self, p: &Self::SuitableIdeal<'ring>, max_ideal_idx: usize) -> Self::LocalField<'ring>
514                where Self: 'ring
515            {
516                use $crate::rings::zn::*;
517
518                assert_eq!(0, max_ideal_idx);
519                $crate::rings::zn::zn_64::Zn::new(*p as u64).as_field().ok().unwrap()
520            }
521        
522            fn local_ring_at<'ring>(&self, p: &Self::SuitableIdeal<'ring>, e: usize, max_ideal_idx: usize) -> Self::LocalRing<'ring>
523                where Self: 'ring
524            {
525                assert_eq!(0, max_ideal_idx);
526                $crate::rings::zn::zn_big::Zn::new(BigIntRing::RING, BigIntRing::RING.pow(int_cast(*p, BigIntRing::RING, StaticRing::<i64>::RING), e))
527            }
528        
529            fn random_suitable_ideal<'ring, F>(&'ring self, rng: F) -> Self::SuitableIdeal<'ring>
530                where F: FnMut() -> u64
531            {
532                let lower_bound = StaticRing::<i64>::RING.get_ring().get_uniformly_random_bits(24, rng);
533                return $crate::algorithms::miller_rabin::next_prime(StaticRing::<i64>::RING, lower_bound);
534            }
535        
536            fn reduce_ring_el<'ring>(&self, _p: &Self::SuitableIdeal<'ring>, to: (&Self::LocalRing<'ring>, usize), max_ideal_idx: usize, x: Self::Element) -> El<Self::LocalRing<'ring>>
537                where Self: 'ring
538            {
539                use $crate::homomorphism::*;
540
541                assert_eq!(0, max_ideal_idx);
542                let self_ref = RingRef::new(self);
543                let hom = to.0.can_hom(&self_ref).unwrap();
544                return hom.map(x);
545            }
546        
547            fn reduce_partial<'ring>(&self, _p: &Self::SuitableIdeal<'ring>, from: (&Self::LocalRing<'ring>, usize), to: (&Self::LocalRing<'ring>, usize), max_ideal_idx: usize, x: El<Self::LocalRing<'ring>>) -> El<Self::LocalRing<'ring>>
548                where Self: 'ring
549            {
550                use $crate::rings::zn::*;
551                use $crate::homomorphism::*;
552
553                assert_eq!(0, max_ideal_idx);
554                assert!(from.1 >= to.1);
555                let hom = to.0.can_hom(to.0.integer_ring()).unwrap();
556                return hom.map(from.0.smallest_lift(x));
557            }
558        
559            fn heuristic_exponent<'ring, 'a, I>(&self, p: &i64, poly_deg: usize, coefficients: I) -> usize
560                where I: Iterator<Item = &'a Self::Element>,
561                    Self: 'a,
562                    Self: 'ring
563            {
564                let log2_max_coeff = coefficients.map(|c| RingRef::new(self).abs_log2_ceil(c).unwrap_or(0)).max().unwrap_or(0);
565                // this is in no way a rigorous bound, but equals the worst-case bound at least asymptotically (up to constants)
566                return ((log2_max_coeff as f64 + poly_deg as f64) / (*p as f64).log2() * $crate::algorithms::poly_gcd::local::INTRING_HEURISTIC_FACTOR_SIZE_OVER_POLY_SIZE_FACTOR).ceil() as usize + 1;
567            }
568            
569            fn dbg_ideal<'ring>(&self, p: &Self::SuitableIdeal<'ring>, out: &mut std::fmt::Formatter) -> std::fmt::Result
570                where Self: 'ring
571            {
572                write!(out, "({})", p)
573            }
574        }
575
576        impl<$($gen_args)*> $crate::algorithms::poly_gcd::local::IntegerPolyGCDRing for $int_ring_type
577            where $($constraints)*
578        {
579            type LocalRingAsZnBase<'ring> = Self::LocalRingBase<'ring>
580                where Self: 'ring;
581
582            type LocalRingAsZn<'ring> = Self::LocalRing<'ring>
583                where Self: 'ring;
584
585            fn local_ring_as_zn<'a, 'ring>(&self, local_field: &'a Self::LocalRing<'ring>) -> &'a Self::LocalRingAsZn<'ring>
586                where Self: 'ring
587            {
588                local_field
589            }
590        }
591    };
592}
593
594///
595/// We cannot provide a blanket impl of [`super::PolyTFracGCDRing`] for finite fields, since it would
596/// conflict with the one for all rings that impl [`PolyGCDLocallyDomain`]. Thus, we implement
597/// [`PolyGCDLocallyDomain`] for all finite fields, and reuse the blanket impl.
598/// 
599/// Note that while technically, finite fields are always [`PolyGCDLocallyDomain`] - where the
600/// local rings are all equal to itself - we still panic in the implementations. In particular,
601/// giving a working implementation would be "correct", but this implementation should never be
602/// called anyway, since we specialize on finite fields previously anyway.
603/// 
604#[allow(unused)]
605impl<R> PolyGCDLocallyDomain for R
606    where R: ?Sized + FiniteRing + Field + SelfIso
607{
608    type LocalRingBase<'ring> = Self
609        where Self: 'ring;
610    type LocalRing<'ring> = RingRef<'ring, Self>
611        where Self: 'ring;
612                
613    type LocalFieldBase<'ring> = Self
614        where Self: 'ring;
615    type LocalField<'ring> = RingRef<'ring, Self>
616        where Self: 'ring;
617    type SuitableIdeal<'ring> = RingRef<'ring, Self>
618        where Self: 'ring;
619        
620    fn heuristic_exponent<'ring, 'element, IteratorType>(&self, _maximal_ideal: &Self::SuitableIdeal<'ring>, _poly_deg: usize, _coefficients: IteratorType) -> usize
621        where IteratorType: Iterator<Item = &'element Self::Element>,
622            Self: 'element,
623            Self: 'ring
624    {
625        unreachable!("this should never be called for finite fields, since specialized functions are available in this case")
626    }
627
628    fn maximal_ideal_factor_count<'ring>(&self,ideal: &Self::SuitableIdeal<'ring>) -> usize where Self:'ring {
629        unreachable!("this should never be called for finite fields, since specialized functions are available in this case")
630    }
631
632    fn random_suitable_ideal<'ring, RandomNumberFunction>(&'ring self, rng: RandomNumberFunction) -> Self::SuitableIdeal<'ring>
633        where RandomNumberFunction: FnMut() -> u64
634    {
635        unreachable!("this should never be called for finite fields, since specialized functions are available in this case")
636    }
637
638    fn local_field_at<'ring>(&self, p: &Self::SuitableIdeal<'ring>, max_ideal_idx: usize) -> Self::LocalField<'ring>
639        where Self: 'ring
640    {
641        unreachable!("this should never be called for finite fields, since specialized functions are available in this case")
642    }
643                
644    fn local_ring_at<'ring>(&self, p: &Self::SuitableIdeal<'ring>, e: usize, max_ideal_idx: usize) -> Self::LocalRing<'ring>
645        where Self: 'ring
646    {
647        unreachable!("this should never be called for finite fields, since specialized functions are available in this case")
648    }
649
650    fn reduce_ring_el<'ring>(&self, p: &Self::SuitableIdeal<'ring>, to: (&Self::LocalRing<'ring>, usize), max_ideal_idx: usize, x: Self::Element) -> El<Self::LocalRing<'ring>>
651        where Self: 'ring
652    {
653        unreachable!("this should never be called for finite fields, since specialized functions are available in this case")
654    }
655
656    fn reduce_partial<'ring>(&self, p: &Self::SuitableIdeal<'ring>, from: (&Self::LocalRing<'ring>, usize), to: (&Self::LocalRing<'ring>, usize), max_ideal_idx: usize, x: El<Self::LocalRing<'ring>>) -> El<Self::LocalRing<'ring>>
657        where Self: 'ring
658    {
659        unreachable!("this should never be called for finite fields, since specialized functions are available in this case")
660    }
661
662    fn lift_partial<'ring>(&self, p: &Self::SuitableIdeal<'ring>, from: (&Self::LocalRing<'ring>, usize), to: (&Self::LocalRing<'ring>, usize), max_ideal_idx: usize, x: El<Self::LocalRing<'ring>>) -> El<Self::LocalRing<'ring>>
663        where Self: 'ring
664    {
665        unreachable!("this should never be called for finite fields, since specialized functions are available in this case")
666    }
667
668    fn reconstruct_ring_el<'local, 'element, 'ring, V1, V2>(&self, p: &Self::SuitableIdeal<'ring>, from: V1, e: usize, x: V2) -> Self::Element
669        where Self: 'ring, 
670            V1: VectorFn<&'local Self::LocalRing<'ring>>,
671            V2: VectorFn<&'element El<Self::LocalRing<'ring>>>,
672            'ring: 'local + 'element,
673            Self::LocalRing<'ring>: 'local,
674            El<Self::LocalRing<'ring>>: 'element
675    {
676        unreachable!("this should never be called for finite fields, since specialized functions are available in this case")
677    }
678    
679    fn dbg_ideal<'ring>(&self, p: &Self::SuitableIdeal<'ring>, out: &mut std::fmt::Formatter) -> std::fmt::Result
680        where Self: 'ring
681    {
682        unreachable!("this should never be called for finite fields, since specialized functions are available in this case")
683    }
684}
685
686#[stability::unstable(feature = "enable")]
687pub struct IntegersWithLocalZnQuotient<'a, R>
688    where R: Sized + ZnRing + PrincipalLocalRing + FromModulusCreateableZnRing + LinSolveRing
689{
690    integers: &'a R::IntegerRing,
691    prime: El<R::IntegerRing>
692}
693
694impl<'a, R> IntegersWithLocalZnQuotient<'a, R>
695    where R: Sized + ZnRing + PrincipalLocalRing + FromModulusCreateableZnRing + LinSolveRing,
696        AsFieldBase<RingValue<R>>: CanIsoFromTo<R> + SelfIso
697{
698    #[stability::unstable(feature = "enable")]
699    pub fn new(integers: &'a R::IntegerRing, prime: El<R::IntegerRing>) -> Self {
700        assert!(is_prime(integers, &prime, 10));
701        return Self { integers, prime };
702    }
703
704    #[stability::unstable(feature = "enable")]
705    pub fn reduction_context<'b>(&'b self, from_e: usize, to_e: usize) -> ReductionContext<'b, 'b, Self> {
706        ReductionContext {
707            ring: RingRef::new(self),
708            ideal: &self.prime,
709            from_e: from_e,
710            from: vec![self.local_ring_at(&self.prime, from_e, 0)], 
711            to: vec![self.local_ring_at(&self.prime, to_e, 0)], 
712        }
713    }
714}
715
716impl<'a, R> PartialEq for IntegersWithLocalZnQuotient<'a, R>
717    where R: ?Sized + ZnRing + PrincipalLocalRing + FromModulusCreateableZnRing + LinSolveRing
718{
719    fn eq(&self, other: &Self) -> bool {
720        self.integers.get_ring() == other.integers.get_ring()
721    }
722}
723
724impl<'a, R> DelegateRing for IntegersWithLocalZnQuotient<'a, R>
725    where R: Sized + ZnRing + PrincipalLocalRing + FromModulusCreateableZnRing + LinSolveRing
726{
727    type Base = <R as ZnRing>::IntegerRingBase;
728    type Element = El<<R as ZnRing>::IntegerRing>;
729
730    fn get_delegate(&self) -> &Self::Base {
731        self.integers.get_ring()
732    }
733
734    fn delegate(&self, el: Self::Element) -> <Self::Base as RingBase>::Element { el }
735    fn delegate_mut<'b>(&self, el: &'b mut Self::Element) -> &'b mut <Self::Base as RingBase>::Element { el }
736    fn delegate_ref<'b>(&self, el: &'b Self::Element) -> &'b <Self::Base as RingBase>::Element { el }
737    fn rev_delegate(&self, el: <Self::Base as RingBase>::Element) -> Self::Element { el }
738}
739
740impl<'a, R> Domain for IntegersWithLocalZnQuotient<'a, R>
741    where R: Sized + ZnRing + PrincipalLocalRing + FromModulusCreateableZnRing
742{}
743
744impl<'a, R> DelegateRingImplFiniteRing for IntegersWithLocalZnQuotient<'a, R>
745    where R: Sized + ZnRing + PrincipalLocalRing + FromModulusCreateableZnRing
746{}
747
748impl<'a, R> PolyGCDLocallyDomain for IntegersWithLocalZnQuotient<'a, R>
749    where R: Sized + ZnRing + PrincipalLocalRing + FromModulusCreateableZnRing + LinSolveRing,
750        AsFieldBase<RingValue<R>>: CanIsoFromTo<R> + SelfIso
751{
752    type LocalRingBase<'ring> = R
753        where Self: 'ring;
754
755    type LocalRing<'ring> = RingValue<R>
756        where Self: 'ring;
757    
758    type LocalFieldBase<'ring> = AsFieldBase<RingValue<R>>
759        where Self: 'ring;
760
761    type LocalField<'ring> = AsField<RingValue<R>>
762        where Self: 'ring;
763
764    type SuitableIdeal<'ring> = Self::Element
765        where Self: 'ring;
766
767    fn heuristic_exponent<'ring, 'el, I>(&self, ideal: &Self::SuitableIdeal<'ring>, poly_deg: usize, coefficients: I) -> usize
768        where I: Iterator<Item = &'el Self::Element>,
769            Self: 'el + 'ring
770    {
771        let log2_max_coeff = coefficients.map(|c| self.integers.abs_log2_ceil(c).unwrap_or(0)).max().unwrap_or(0);
772        // this is in no way a rigorous bound, but equals the worst-case bound at least asymptotically (up to constants)
773        return ((log2_max_coeff as f64 + poly_deg as f64) / self.integers.abs_log2_floor(ideal).unwrap_or(1) as f64 * crate::algorithms::poly_gcd::local::INTRING_HEURISTIC_FACTOR_SIZE_OVER_POLY_SIZE_FACTOR).ceil() as usize + 1;
774    }
775
776    fn random_suitable_ideal<'ring, F>(&'ring self, _rng: F) -> Self::SuitableIdeal<'ring>
777        where F: FnMut() -> u64
778    {
779        self.integers.clone_el(&self.prime)
780    }
781
782    fn maximal_ideal_factor_count<'ring>(&self, ideal: &Self::SuitableIdeal<'ring>) -> usize
783        where Self: 'ring
784    {
785        debug_assert!(self.integers.eq_el(ideal, &self.prime));
786        1
787    }
788
789    fn local_field_at<'ring>(&self, ideal: &Self::SuitableIdeal<'ring>, max_ideal_idx: usize) -> Self::LocalField<'ring>
790        where Self: 'ring
791    {
792        assert_eq!(0, max_ideal_idx);
793        self.local_ring_at(ideal, 1, 0).as_field().ok().unwrap()
794    }
795    
796    fn local_ring_at<'ring>(&self, ideal: &Self::SuitableIdeal<'ring>, e: usize, max_ideal_idx: usize) -> Self::LocalRing<'ring>
797        where Self: 'ring
798    {
799        assert_eq!(0, max_ideal_idx);
800        assert!(self.integers.eq_el(ideal, &self.prime));
801        RingValue::from(R::create(|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))
802    }
803
804    fn reduce_ring_el<'ring>(&self, ideal: &Self::SuitableIdeal<'ring>, to: (&Self::LocalRing<'ring>, usize), max_ideal_idx: usize, x: Self::Element) -> El<Self::LocalRing<'ring>>
805        where Self: 'ring
806    {
807        debug_assert_eq!(0, max_ideal_idx);
808        debug_assert!(self.integers.eq_el(ideal, &self.prime));
809        debug_assert!(self.integers.eq_el(&self.integers.pow(self.integers.clone_el(&self.prime), to.1), to.0.modulus()));
810        to.0.coerce(&self.integers, x)
811    }
812
813    fn reduce_partial<'ring>(&self, ideal: &Self::SuitableIdeal<'ring>, from: (&Self::LocalRing<'ring>, usize), to: (&Self::LocalRing<'ring>, usize), max_ideal_idx: usize, x: El<Self::LocalRing<'ring>>) -> El<Self::LocalRing<'ring>>
814        where Self: 'ring
815    {
816        debug_assert_eq!(0, max_ideal_idx);
817        debug_assert!(self.integers.eq_el(ideal, &self.prime));
818        debug_assert!(self.integers.eq_el(&self.integers.pow(self.integers.clone_el(&self.prime), to.1), to.0.modulus()));
819        debug_assert!(self.integers.eq_el(&self.integers.pow(self.integers.clone_el(&self.prime), from.1), from.0.modulus()));
820        to.0.coerce(&self.integers, from.0.smallest_positive_lift(x))
821    }
822
823    fn lift_partial<'ring>(&self, ideal: &Self::SuitableIdeal<'ring>, from: (&Self::LocalRing<'ring>, usize), to: (&Self::LocalRing<'ring>, usize), max_ideal_idx: usize, x: El<Self::LocalRing<'ring>>) -> El<Self::LocalRing<'ring>>
824        where Self: 'ring
825    {
826        debug_assert_eq!(0, max_ideal_idx);
827        debug_assert!(self.integers.eq_el(ideal, &self.prime));
828        debug_assert!(self.integers.eq_el(&self.integers.pow(self.integers.clone_el(&self.prime), to.1), to.0.modulus()));
829        debug_assert!(self.integers.eq_el(&self.integers.pow(self.integers.clone_el(&self.prime), from.1), from.0.modulus()));
830        to.0.coerce(&self.integers, from.0.smallest_positive_lift(x))
831    }
832
833    fn reconstruct_ring_el<'local, 'element, 'ring, V1, V2>(&self, ideal: &Self::SuitableIdeal<'ring>, from: V1, e: usize, x: V2) -> Self::Element
834        where Self: 'ring, 
835            V1: VectorFn<&'local Self::LocalRing<'ring>>,
836            V2: VectorFn<&'element El<Self::LocalRing<'ring>>>,
837            Self::LocalRing<'ring>: 'local,
838            El<Self::LocalRing<'ring>>: 'element,
839            'ring: 'local + 'element
840    {
841        assert_eq!(1, x.len());
842        assert_eq!(1, from.len());
843        debug_assert!(self.integers.eq_el(ideal, &self.prime));
844        debug_assert!(self.integers.eq_el(&self.integers.pow(self.integers.clone_el(&self.prime), e), from.at(0).modulus()));
845        from.at(0).smallest_lift(from.at(0).clone_el(x.at(0)))
846    }
847
848    fn dbg_ideal<'ring>(&self, ideal: &Self::SuitableIdeal<'ring>, out: &mut std::fmt::Formatter) -> std::fmt::Result
849        where Self: 'ring
850    {
851        self.dbg(ideal, out)
852    }
853}
feanor_math/algorithms/poly_gcd/local.rs

feanor_math/algorithms/poly_gcd/
local.rs
