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

feanor_math/rings/
finite.rs
