feanor_math/rings/
finite.rs

1use std::marker::PhantomData;
2
3use crate::algorithms::int_factor::is_prime_power;
4use crate::field::*;
5use crate::homomorphism::Homomorphism;
6use crate::integer::{BigIntRing, IntegerRing, IntegerRingStore};
7use crate::ring::*;
8use crate::specialization::FiniteRingSpecializable;
9use crate::unsafe_any::UnsafeAny;
10
11/// Trait for rings that are finite.
12///
13/// Currently [`FiniteRing`] is a subtrait of the unstable trait [`FiniteRingSpecializable`],
14/// so it is at the moment impossible to implement [`FiniteRing`] for a custom ring type
15/// without enabling unstable features. Sorry.
16pub trait FiniteRing: RingBase + FiniteRingSpecializable {
17    /// Type of the iterator returned by [`FiniteRing::elements()`], which should
18    /// iterate over all elements of the ring.
19    type ElementsIter<'a>: Sized + Clone + Iterator<Item = <Self as RingBase>::Element>
20    where
21        Self: 'a;
22
23    /// Returns an iterator over all elements of this ring.
24    /// The order is not specified.
25    fn elements<'a>(&'a self) -> Self::ElementsIter<'a>;
26
27    /// Returns a uniformly random element from this ring, using the randomness
28    /// provided by `rng`.
29    fn random_element<G: FnMut() -> u64>(&self, rng: G) -> <Self as RingBase>::Element;
30
31    /// Returns the number of elements in this ring, if it fits within
32    /// the given integer ring.
33    fn size<I: IntegerRingStore + Copy>(&self, ZZ: I) -> Option<El<I>>
34    where
35        I::Type: IntegerRing;
36}
37
38/// [`RingStore`] for [`FiniteRing`]
39pub trait FiniteRingStore: RingStore
40where
41    Self::Type: FiniteRing,
42{
43    /// See [`FiniteRing::elements()`].
44    fn elements<'a>(&'a self) -> <Self::Type as FiniteRing>::ElementsIter<'a> { self.get_ring().elements() }
45
46    /// See [`FiniteRing::random_element()`].
47    fn random_element<G: FnMut() -> u64>(&self, rng: G) -> El<Self> { self.get_ring().random_element(rng) }
48
49    /// See [`FiniteRing::size()`].
50    fn size<I: IntegerRingStore + Copy>(&self, ZZ: I) -> Option<El<I>>
51    where
52        I::Type: IntegerRing,
53    {
54        self.get_ring().size(ZZ)
55    }
56}
57
58impl<R: RingStore> FiniteRingStore for R where R::Type: FiniteRing {}
59
60#[stability::unstable(feature = "enable")]
61pub struct UnsafeAnyFrobeniusDataGuarded<GuardType: ?Sized> {
62    content: UnsafeAny,
63    guard: PhantomData<GuardType>,
64}
65
66impl<GuardType: ?Sized> UnsafeAnyFrobeniusDataGuarded<GuardType> {
67    #[stability::unstable(feature = "enable")]
68    pub fn uninit() -> UnsafeAnyFrobeniusDataGuarded<GuardType> {
69        Self {
70            content: UnsafeAny::uninit(),
71            guard: PhantomData,
72        }
73    }
74
75    #[stability::unstable(feature = "enable")]
76    pub unsafe fn from<T>(value: T) -> UnsafeAnyFrobeniusDataGuarded<GuardType> {
77        Self {
78            content: unsafe { UnsafeAny::from(value) },
79            guard: PhantomData,
80        }
81    }
82
83    #[stability::unstable(feature = "enable")]
84    pub unsafe fn get<'a, T>(&'a self) -> &'a T { unsafe { self.content.get() } }
85}
86
87#[stability::unstable(feature = "enable")]
88pub trait ComputeFrobeniusRing: Field + FiniteRing {
89    type FrobeniusData;
90
91    fn create_frobenius(&self, exponent_of_p: usize) -> (Self::FrobeniusData, usize);
92
93    fn apply_frobenius(
94        &self,
95        _frobenius_data: &Self::FrobeniusData,
96        exponent_of_p: usize,
97        x: Self::Element,
98    ) -> Self::Element;
99}
100
101impl<R> ComputeFrobeniusRing for R
102where
103    R: ?Sized + Field + FiniteRing,
104{
105    type FrobeniusData = UnsafeAnyFrobeniusDataGuarded<R>;
106
107    default fn create_frobenius(&self, exponent_of_p: usize) -> (Self::FrobeniusData, usize) {
108        (UnsafeAnyFrobeniusDataGuarded::uninit(), exponent_of_p)
109    }
110
111    default fn apply_frobenius(
112        &self,
113        _frobenius_data: &Self::FrobeniusData,
114        exponent_of_p: usize,
115        x: Self::Element,
116    ) -> Self::Element {
117        if exponent_of_p == 0 {
118            return x;
119        } else {
120            let (p, e) = is_prime_power(BigIntRing::RING, &self.size(&BigIntRing::RING).unwrap()).unwrap();
121            return RingRef::new(self).pow_gen(x, &BigIntRing::RING.pow(p, exponent_of_p % e), BigIntRing::RING);
122        }
123    }
124}
125
126#[stability::unstable(feature = "enable")]
127pub struct Frobenius<R>
128where
129    R: RingStore,
130    R::Type: FiniteRing + Field,
131{
132    field: R,
133    data: <R::Type as ComputeFrobeniusRing>::FrobeniusData,
134    exponent_of_p: usize,
135}
136
137impl<R> Frobenius<R>
138where
139    R: RingStore,
140    R::Type: FiniteRing + Field,
141{
142    #[stability::unstable(feature = "enable")]
143    pub fn new(field: R, exponent_of_p: usize) -> Self {
144        let (_p, field_dimension) = is_prime_power(BigIntRing::RING, &field.size(BigIntRing::RING).unwrap()).unwrap();
145        let exponent_of_p = exponent_of_p % field_dimension;
146        let (data, exponent_of_p2) = field.get_ring().create_frobenius(exponent_of_p);
147        assert_eq!(exponent_of_p, exponent_of_p2);
148        return Self {
149            field,
150            data,
151            exponent_of_p,
152        };
153    }
154}
155
156impl<R> Homomorphism<R::Type, R::Type> for Frobenius<R>
157where
158    R: RingStore,
159    R::Type: FiniteRing + Field,
160{
161    type CodomainStore = R;
162    type DomainStore = R;
163
164    fn codomain(&self) -> &Self::CodomainStore { &self.field }
165
166    fn domain(&self) -> &Self::DomainStore { &self.field }
167
168    fn map(&self, x: <R::Type as RingBase>::Element) -> <R::Type as RingBase>::Element {
169        self.field.get_ring().apply_frobenius(&self.data, self.exponent_of_p, x)
170    }
171}
172
173#[cfg(any(test, feature = "generic_tests"))]
174pub mod generic_tests {
175
176    use super::{FiniteRing, FiniteRingStore, RingStore};
177    use crate::divisibility::DivisibilityRingStore;
178    use crate::integer::{BigIntRing, IntegerRingStore, int_cast};
179    use crate::ordered::OrderedRingStore;
180    use crate::primitive_int::StaticRing;
181
182    pub fn test_finite_ring_axioms<R>(ring: &R)
183    where
184        R: RingStore,
185        R::Type: FiniteRing,
186    {
187        let ZZ = BigIntRing::RING;
188        let size = ring.size(&ZZ).unwrap();
189        let char = ring.characteristic(&ZZ).unwrap();
190        assert!(ZZ.divides(&size, &char));
191
192        if ZZ.is_geq(&size, &ZZ.power_of_two(7)) {
193            assert_eq!(None, ring.size(&StaticRing::<i8>::RING));
194        }
195
196        if ZZ.is_leq(&size, &ZZ.power_of_two(30)) {
197            assert_eq!(
198                int_cast(size, &StaticRing::<i64>::RING, &ZZ) as usize,
199                ring.elements().count()
200            );
201        }
202    }
203}
feanor_math/rings/finite.rs

feanor_math/rings/
finite.rs
