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

feanor_math/rings/
finite.rs
