feanor_math/algorithms/
galois.rs

1
2use std::fmt::Debug;
3use std::hash::Hash;
4
5use crate::computation::*;
6use crate::homomorphism::*;
7use crate::field::*;
8use crate::divisibility::*;
9use crate::rings::extension::number_field::*;
10use crate::rings::extension::*;
11use crate::primitive_int::*;
12use crate::rings::poly::dense_poly::DensePolyRing;
13use crate::rings::poly::*;
14use crate::integer::*;
15use crate::rings::rational::*;
16use crate::ring::*;
17use crate::seq::VectorFn;
18use super::splitting_field::extend_number_field_promise_is_irreducible;
19use super::splitting_field::splitting_field;
20use super::sqr_mul::generic_pow_shortest_chain_table;
21
22///
23/// Computes the Galois closure of `field`.
24///
25/// If the field is already a Galois extension of `Q`, all conjugates of its canonical
26/// generator are returned via [`Result::Err`] instead.
27/// 
28#[stability::unstable(feature = "enable")]
29pub fn compute_galois_closure<Controller: ComputationController>(field: NumberField, controller: Controller) -> Result<
30        FreeAlgebraHom<NumberField, NumberField>,
31        (NumberField, Vec<El<NumberField>>)
32    >
33{
34    let poly_ring = DensePolyRing::new(field, "X");
35    let gen_poly = poly_ring.base_ring().generating_poly(&poly_ring, poly_ring.base_ring().inclusion());
36    let poly_to_factor = poly_ring.checked_div(
37        &gen_poly,
38        &poly_ring.sub(poly_ring.indeterminate(), poly_ring.inclusion().map(poly_ring.base_ring().canonical_gen()))
39    ).unwrap();
40
41    let mut extended_field = false;
42    let (into_extension_field, roots) = splitting_field(
43        poly_ring,
44        poly_to_factor,
45        |poly_ring, extend_with, controller| {
46            extended_field = true;
47            extend_number_field_promise_is_irreducible(poly_ring, &extend_with, controller)
48        },
49        controller
50    );
51
52    if extended_field {
53        return Ok(into_extension_field);
54    } else {
55        let (field, field_again, _) = into_extension_field.destruct();
56        debug_assert!(field.get_ring() == field_again.get_ring());
57        return Err((field, [field_again.canonical_gen()].into_iter().chain(roots.into_iter().map(|(f, _)| f)).collect()));
58    }
59}
60
61#[stability::unstable(feature = "enable")]
62pub struct GaloisAutomorphism<K, Impl, I>
63    where K: RingStore<Type = NumberFieldBase<Impl, I>>,
64        Impl: RingStore,
65        Impl::Type: Field + FreeAlgebra,
66        <Impl::Type as RingExtension>::BaseRing: RingStore<Type = RationalFieldBase<I>>,
67        I: RingStore,
68        I::Type: IntegerRing
69{
70    field: K,
71    image_of_canonical_gen_powers: Vec<El<K>>
72}
73
74impl<K, Impl, I> GaloisAutomorphism<K, Impl, I>
75    where K: RingStore<Type = NumberFieldBase<Impl, I>>,
76        Impl: RingStore,
77        Impl::Type: Field + FreeAlgebra,
78        <Impl::Type as RingExtension>::BaseRing: RingStore<Type = RationalFieldBase<I>>,
79        I: RingStore,
80        I::Type: IntegerRing
81{
82    ///
83    /// Creates a new Galois automorphism, mapping the canonical generator
84    /// of field to the given element.
85    /// 
86    #[stability::unstable(feature = "enable")]
87    pub fn new(field: K, image_of_canonical_gen: El<K>) -> Self {
88        let poly_ring = DensePolyRing::new(field.base_ring(), "X");
89        assert!(field.is_zero(&poly_ring.evaluate(&field.generating_poly(&poly_ring, field.base_ring().identity()), &image_of_canonical_gen, field.inclusion())));
90        return Self {
91            image_of_canonical_gen_powers: (0..field.rank()).map(|i| field.pow(field.clone_el(&image_of_canonical_gen), i)).collect(),
92            field: field
93        };
94    }
95
96    ///
97    /// Returns the galois automorphism `x -> self(first(x))`
98    /// 
99    #[stability::unstable(feature = "enable")]
100    pub fn compose_gal(self, first: &Self) -> Self {
101        assert!(self.field.get_ring() == first.field.get_ring());
102        let new_image = self.map_ref(&first.image_of_canonical_gen_powers[1]);
103        return Self::new(self.field, new_image);
104    }
105    
106    ///
107    /// Returns the galois automorphism `x -> self(...(self(x))...)`, where
108    /// `self` is applied `k` times.
109    /// 
110    #[stability::unstable(feature = "enable")]
111    pub fn pow(self, k: usize) -> Self {
112        let field = self.field;
113        let poly_ring = DensePolyRing::new(field.base_ring(), "X");
114        let new_image = generic_pow_shortest_chain_table(
115            field.clone_el(&self.image_of_canonical_gen_powers[1]), 
116            &(k as i64), 
117            StaticRing::<i64>::RING, 
118            |x| Ok(poly_ring.evaluate(&field.poly_repr(&poly_ring, x, field.base_ring().identity()), x, field.inclusion())), 
119            |x, y| Ok(poly_ring.evaluate(&field.poly_repr(&poly_ring, x, field.base_ring().identity()), y, field.inclusion())), 
120            |x| field.clone_el(x), 
121            field.canonical_gen()
122        ).unwrap_or_else(no_error);
123        return Self::new(field, new_image);
124    }
125
126    ///
127    /// Returns true if this is the identity map.
128    /// 
129    #[stability::unstable(feature = "enable")]
130    pub fn is_identity(&self) -> bool {
131        self.field.eq_el(&self.image_of_canonical_gen_powers[1], &self.field.canonical_gen())
132    }
133
134    ///
135    /// Returns the inverse of this automorphism
136    /// 
137    #[stability::unstable(feature = "enable")]
138    pub fn invert(self) -> Self {
139        let k = self.field.rank() - 1;
140        self.pow(k)
141    }
142}
143
144impl<K, Impl, I> Homomorphism<NumberFieldBase<Impl, I>, NumberFieldBase<Impl, I>> for GaloisAutomorphism<K, Impl, I>
145    where K: RingStore<Type = NumberFieldBase<Impl, I>>,
146        Impl: RingStore,
147        Impl::Type: Field + FreeAlgebra,
148        <Impl::Type as RingExtension>::BaseRing: RingStore<Type = RationalFieldBase<I>>,
149        I: RingStore,
150        I::Type: IntegerRing
151{
152    type DomainStore = K;
153    type CodomainStore = K;
154
155    fn codomain<'a>(&'a self) -> &'a Self::CodomainStore {
156        &self.field
157    }
158
159    fn domain<'a>(&'a self) -> &'a Self::DomainStore {
160        &self.field
161    }
162
163    fn map_ref(&self, x: &<NumberFieldBase<Impl, I> as RingBase>::Element) -> <NumberFieldBase<Impl, I> as RingBase>::Element {
164        let coeffs_wrt_basis = self.field.wrt_canonical_basis(x);
165        let hom = self.field.inclusion();
166        return self.field.sum(self.image_of_canonical_gen_powers.iter().zip(coeffs_wrt_basis.iter()).map(|(x, y)| hom.mul_ref_map(x, &y)));
167    }
168
169    fn map(&self, x: <NumberFieldBase<Impl, I> as RingBase>::Element) -> <NumberFieldBase<Impl, I> as RingBase>::Element {
170        self.map_ref(&x)
171    }
172}
173
174impl<K, Impl, I> Debug for GaloisAutomorphism<K, Impl, I>
175    where K: RingStore<Type = NumberFieldBase<Impl, I>>,
176        Impl: RingStore,
177        Impl::Type: Field + FreeAlgebra,
178        <Impl::Type as RingExtension>::BaseRing: RingStore<Type = RationalFieldBase<I>>,
179        I: RingStore,
180        I::Type: IntegerRing
181{
182    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
183        f.debug_struct("GaloisAutomorphism").field("gen_image", &self.field.format(&self.image_of_canonical_gen_powers[1])).finish()
184    }
185}
186
187impl<K, Impl, I> Clone for GaloisAutomorphism<K, Impl, I>
188    where K: RingStore<Type = NumberFieldBase<Impl, I>> + Clone,
189        Impl: RingStore,
190        Impl::Type: Field + FreeAlgebra,
191        <Impl::Type as RingExtension>::BaseRing: RingStore<Type = RationalFieldBase<I>>,
192        I: RingStore,
193        I::Type: IntegerRing
194{
195    fn clone(&self) -> Self {
196        Self {
197            field: self.field.clone(),
198            image_of_canonical_gen_powers: self.image_of_canonical_gen_powers.iter().map(|x| self.field.clone_el(x)).collect()
199        }
200    }
201}
202
203impl<K, Impl, I> PartialEq for GaloisAutomorphism<K, Impl, I>
204    where K: RingStore<Type = NumberFieldBase<Impl, I>>,
205        Impl: RingStore,
206        Impl::Type: Field + FreeAlgebra,
207        <Impl::Type as RingExtension>::BaseRing: RingStore<Type = RationalFieldBase<I>>,
208        I: RingStore,
209        I::Type: IntegerRing
210{
211    fn eq(&self, other: &Self) -> bool {
212        assert!(self.field.get_ring() == other.field.get_ring());
213        self.field.eq_el(&self.image_of_canonical_gen_powers[1], &other.image_of_canonical_gen_powers[1])
214    }
215}
216
217impl<K, Impl, I> Eq for GaloisAutomorphism<K, Impl, I>
218    where K: RingStore<Type = NumberFieldBase<Impl, I>>,
219        Impl: RingStore,
220        Impl::Type: Field + FreeAlgebra,
221        <Impl::Type as RingExtension>::BaseRing: RingStore<Type = RationalFieldBase<I>>,
222        I: RingStore,
223        I::Type: IntegerRing
224{}
225
226impl<K, Impl, I> Hash for GaloisAutomorphism<K, Impl, I>
227    where K: RingStore<Type = NumberFieldBase<Impl, I>>,
228        Impl: RingStore,
229        Impl::Type: Field + FreeAlgebra + HashableElRing,
230        <Impl::Type as RingExtension>::BaseRing: RingStore<Type = RationalFieldBase<I>>,
231        I: RingStore,
232        I::Type: IntegerRing
233{
234    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
235        self.field.hash(&self.image_of_canonical_gen_powers[1], state)
236    }
237}
238
239///
240/// If the number field is galois, returns its Galois group.
241/// 
242/// Otherwise, returns its embedding into its Galois closure as [`Result::Err`].
243/// 
244#[stability::unstable(feature = "enable")]
245pub fn compute_galois_group<K, Controller>(field: K, controller: Controller) -> Result<
246        Vec<GaloisAutomorphism<K, DefaultNumberFieldImpl, BigIntRing>>, 
247        FreeAlgebraHom<K, NumberField>
248    >
249    where K: Clone + RingStore<Type = NumberFieldBase<DefaultNumberFieldImpl, BigIntRing>>,
250        Controller: ComputationController
251{
252    match compute_galois_closure(RingValue::from_ref(field.get_ring()).clone(), controller) {
253        Ok(embedding) => {
254            let (_, target, image) = embedding.destruct();
255            return Err(FreeAlgebraHom::promise_is_well_defined(field, target, image));
256        },
257        Err((_, conjugates)) => {
258            let mut result: Vec<_> = conjugates.into_iter().map(|x| GaloisAutomorphism::new(field.clone(), x)).collect();
259            let id_idx = result.iter().enumerate().filter(|(_, g)| g.is_identity()).next().unwrap().0;
260            result.swap(0, id_idx);
261            return Ok(result);
262        }
263    }
264}
265
266///
267/// Finds the Galois automorphism that will become complex conjugation under
268/// the given embedding `K -> C`.
269/// 
270#[stability::unstable(feature = "enable")]
271pub fn find_complex_conjugation<'a, K1, K2, K3>(
272    field: K1, 
273    complex_embedding: &ComplexEmbedding<K2, DefaultNumberFieldImpl, BigIntRing>, 
274    galois_group: &'a [GaloisAutomorphism<K3, DefaultNumberFieldImpl, BigIntRing>]
275) -> &'a GaloisAutomorphism<K3, DefaultNumberFieldImpl, BigIntRing>
276    where K1: RingStore<Type = NumberFieldBase<DefaultNumberFieldImpl, BigIntRing>>,
277        K2: RingStore<Type = NumberFieldBase<DefaultNumberFieldImpl, BigIntRing>>,
278        K3: RingStore<Type = NumberFieldBase<DefaultNumberFieldImpl, BigIntRing>>,
279{
280    assert!(complex_embedding.domain().get_ring() == field.get_ring());
281    assert!(galois_group.iter().all(|g| g.domain().get_ring() == field.get_ring()));
282    assert_eq!(field.rank(), galois_group.len());
283
284    let CC = complex_embedding.codomain();
285    let target = CC.conjugate(complex_embedding.map(field.canonical_gen()));
286    let mut result = None;
287    for g in galois_group {
288        let conj = g.map(field.canonical_gen());
289        let image = complex_embedding.map_ref(&conj);
290        let dist = CC.abs(CC.sub(target, image));
291        let error = complex_embedding.absolute_error_bound_at(&conj);
292        if dist <= error {
293            assert!(result.is_none(), "not enough precision to separate all complex roots");
294            result = Some(g);
295        }
296    }
297
298    return result.unwrap();
299}
300
301#[cfg(test)]
302use crate::algorithms::poly_factor::FactorPolyField;
303
304#[test]
305fn test_compute_galois_closure() {
306    let ZZ = BigIntRing::RING;
307    let ZZX = DensePolyRing::new(&ZZ, "X");
308
309    let [f] = ZZX.with_wrapped_indeterminate(|X| [X.pow_ref(2) - 2]);
310    let number_field = NumberField::new(&ZZX, &f);
311    let (number_field, conjugates) = compute_galois_closure(number_field, TEST_LOG_PROGRESS).err().unwrap();
312    assert_el_eq!(&number_field, number_field.canonical_gen(), &conjugates[0]);
313    assert_el_eq!(&number_field, number_field.negate(number_field.canonical_gen()), &conjugates[1]);
314
315    let [f] = ZZX.with_wrapped_indeterminate(|X| [X.pow_ref(4) - 2]);
316    let number_field = NumberField::new(&ZZX, &f);
317    let into_closure = compute_galois_closure(number_field, TEST_LOG_PROGRESS).ok().unwrap();
318    let number_field = into_closure.domain();
319    assert_eq!(8, into_closure.codomain().rank());
320    crate::homomorphism::generic_tests::test_homomorphism_axioms(&into_closure, (0..8).map(|i| number_field.pow(number_field.canonical_gen(), i)));
321    let KX = DensePolyRing::new(into_closure.codomain(), "X");
322    let (factors, _) = <_ as FactorPolyField>::factor_poly(&KX, &number_field.generating_poly(&KX, KX.base_ring().inclusion()));
323    assert_eq!(4, factors.len());
324    
325    let [f] = ZZX.with_wrapped_indeterminate(|X| [X.pow_ref(3) - X.pow_ref(2) + 1]);
326    let number_field = NumberField::new(&ZZX, &f);
327    let into_closure = compute_galois_closure(number_field, TEST_LOG_PROGRESS).ok().unwrap();
328    let number_field = into_closure.domain();
329    assert_eq!(6, into_closure.codomain().rank());
330    crate::homomorphism::generic_tests::test_homomorphism_axioms(&into_closure, (0..6).map(|i| number_field.pow(number_field.canonical_gen(), i)));
331    let KX = DensePolyRing::new(into_closure.codomain(), "X");
332    let (factors, _) = <_ as FactorPolyField>::factor_poly(&KX, &number_field.generating_poly(&KX, KX.base_ring().inclusion()));
333    assert_eq!(3, factors.len());
334}
335
336#[test]
337fn test_compute_galois_group() {
338    let ZZ = BigIntRing::RING;
339    let ZZX = DensePolyRing::new(&ZZ, "X");
340    
341    let [f] = ZZX.with_wrapped_indeterminate(|X| [X.pow_ref(3) - X.pow_ref(2) - 6 * X + 7]);
342    let number_field = NumberField::new(&ZZX, &f);
343    let galois_group = compute_galois_group(&number_field, TEST_LOG_PROGRESS).ok().unwrap();
344    assert_eq!(3, galois_group.len());
345    assert!(galois_group[0].is_identity());
346    let g = &galois_group[1];
347    assert_eq!(&g.clone().pow(2), &galois_group[2]);
348    assert_eq!(&g.clone().pow(3), &galois_group[0]);
349
350    // the galois group in this case is C12
351    let [f] = ZZX.with_wrapped_indeterminate(|X| [X.pow_ref(12) - X.pow_ref(11) + 3 * X.pow_ref(10) - 4 * X.pow_ref(9) + 9 * X.pow_ref(8) + 2 * X.pow_ref(7) + 12 * X.pow_ref(6) + X.pow_ref(5) + 25 * X.pow_ref(4) - 11 * X.pow_ref(3) + 5 * X.pow_ref(2) - 2 * X + 1]);
352    let number_field = NumberField::new(&ZZX, &f);
353    let galois_group = compute_galois_group(&number_field, TEST_LOG_PROGRESS).ok().unwrap();
354    assert_eq!(12, galois_group.len());
355    let g = galois_group.iter().filter(|g| !(*g).clone().pow(4).is_identity() && !(*g).clone().pow(6).is_identity()).next().unwrap();
356    assert!(g.clone().pow(12).is_identity());
357    for i in 0..12 {
358        assert!(galois_group.contains(&g.clone().pow(i)));
359    }
360
361    // the galois group in this case is D5
362    let [f] = ZZX.with_wrapped_indeterminate(|X| [X.pow_ref(10) - 2 * X.pow_ref(8) - 9 * X.pow_ref(6) + 57 * X.pow_ref(4) - 69 * X.pow_ref(2) + 47]);
363    let number_field = NumberField::new(&ZZX, &f);
364    let galois_group = compute_galois_group(&number_field, TEST_LOG_PROGRESS).ok().unwrap();
365    assert_eq!(10, galois_group.len());
366    let id = &galois_group[0];
367    assert!(id.is_identity());
368    let mut g1 = &galois_group[1];
369    assert!(!g1.is_identity());
370    let subgroup: Vec<_> = [id.clone()].into_iter().chain((1..).map(|i| g1.clone().pow(i)).take_while(|g| !g.is_identity())).collect();
371    let mut g2 = galois_group.iter().filter(|g| !subgroup.contains(g)).next().unwrap();
372    if g1.clone().pow(2).is_identity() {
373        std::mem::swap(&mut g1, &mut g2);
374    }
375    // now g1 has order 5 and g2 has order 2, and together they generate the Dihedral group D5
376    assert!(!g1.is_identity());
377    assert!(!g2.is_identity());
378    assert!(g1.clone().pow(5).is_identity());
379    assert!(g2.clone().pow(2).is_identity());
380    assert_eq!(g2.clone().compose_gal(&g1).compose_gal(&g2), g1.clone().invert());
381
382}
383
384#[test]
385fn test_complex_conjugation() {
386    let ZZ = BigIntRing::RING;
387    let ZZX = DensePolyRing::new(&ZZ, "X");
388    
389    let [f] = ZZX.with_wrapped_indeterminate(|X| [X.pow_ref(2) + 1]);
390    let number_field = NumberField::new(&ZZX, &f);
391    let galois_group = compute_galois_group(&number_field, TEST_LOG_PROGRESS).ok().unwrap();
392    let complex_embedding = number_field.choose_complex_embedding();
393    let conjugation = find_complex_conjugation(&number_field, &complex_embedding, &galois_group);
394    assert_el_eq!(&number_field, number_field.negate(number_field.canonical_gen()), conjugation.map(number_field.canonical_gen()));
395    
396    let [f] = ZZX.with_wrapped_indeterminate(|X| [X.pow_ref(4) + X.pow_ref(3) + X.pow_ref(2) + X + 1]);
397    let number_field = NumberField::new(&ZZX, &f);
398    let galois_group = compute_galois_group(&number_field, TEST_LOG_PROGRESS).ok().unwrap();
399    let complex_embedding = number_field.choose_complex_embedding();
400    let conjugation = find_complex_conjugation(&number_field, &complex_embedding, &galois_group);
401    assert_el_eq!(&number_field, number_field.invert(&number_field.canonical_gen()).unwrap(), conjugation.map(number_field.canonical_gen()));
402}
feanor_math/algorithms/galois.rs

feanor_math/algorithms/
galois.rs
