feanor_math/algorithms/
unity_root.rs

1use crate::MAX_PROBABILISTIC_REPETITIONS;
2use crate::field::Field;
3use crate::integer::int_cast;
4use crate::homomorphism::Homomorphism;
5use crate::integer::BigIntRing;
6use crate::integer::IntegerRing;
7use crate::ring::*;
8use crate::primitive_int::*;
9use crate::rings::finite::*;
10use crate::divisibility::DivisibilityRingStore;
11use crate::integer::IntegerRingStore;
12use crate::ordered::OrderedRingStore;
13use crate::rings::zn::ZnRing;
14
15use super::int_factor::factor;
16
17#[stability::unstable(feature = "enable")]
18pub fn is_prim_root_of_unity_pow2<R: RingStore>(ring: R, el: &El<R>, log2_n: usize) -> bool {
19    if log2_n == 0 {
20        return ring.is_one(el);
21    }
22    ring.is_neg_one(&ring.pow(ring.clone_el(&el), 1 << (log2_n - 1)))
23}
24
25#[stability::unstable(feature = "enable")]
26pub fn is_root_of_unity<R: RingStore>(ring: R, el: &El<R>, n: usize) -> bool {
27    is_root_of_unity_gen(ring, el, &n.try_into().unwrap(), StaticRing::<i64>::RING)
28}
29
30#[stability::unstable(feature = "enable")]
31pub fn is_root_of_unity_gen<R: RingStore, I: RingStore>(ring: R, el: &El<R>, n: &El<I>, ZZ: I) -> bool
32    where I::Type: IntegerRing
33{
34    assert!(ZZ.is_pos(n));
35    ring.is_one(&ring.pow_gen(ring.clone_el(&el), n, ZZ))
36}
37
38#[stability::unstable(feature = "enable")]
39pub fn is_prim_root_of_unity<R: RingStore>(ring: R, el: &El<R>, n: usize) -> bool {
40    is_prim_root_of_unity_gen(ring, el, &n.try_into().unwrap(), StaticRing::<i64>::RING)
41}
42
43#[stability::unstable(feature = "enable")]
44pub fn is_prim_root_of_unity_gen<R: RingStore, I>(ring: R, el: &El<R>, n: &El<I>, ZZ: I) -> bool
45    where I: RingStore + Copy,
46        I::Type: IntegerRing
47{
48    if !is_root_of_unity_gen(&ring, el, n, ZZ) {
49        return false;
50    }
51    for (p, _) in factor(&ZZ, ZZ.clone_el(n)) {
52        if is_root_of_unity_gen(&ring, el, &ZZ.checked_div(n, &p).unwrap(), ZZ) {
53            return false;
54        }
55    }
56    return true;
57}
58
59#[stability::unstable(feature = "enable")]
60pub fn get_prim_root_of_unity_gen<R, I>(ring: R, n: &El<I>, ZZ: I, order: &El<I>) -> Option<El<R>>
61    where R: RingStore, 
62        R::Type: FiniteRing,
63        I: RingStore + Copy,
64        I::Type: IntegerRing
65{
66    let power = ZZ.checked_div(order, n)?;
67    
68    let mut rng = oorandom::Rand64::new(ZZ.default_hash(&ring.size(&ZZ).unwrap()) as u128);
69    let mut current = ring.pow_gen(ring.random_element(|| rng.rand_u64()), &power, ZZ);
70    for _ in 0..MAX_PROBABILISTIC_REPETITIONS {
71        if is_prim_root_of_unity_gen(&ring, &current, n, ZZ) {
72            return Some(current);
73        }
74        current = ring.pow_gen(ring.random_element(|| rng.rand_u64()), &power, ZZ);
75    }
76    unreachable!()
77}
78
79///
80/// Returns a primitive `n`-th root of unity in the given finite field,
81/// or `None`, if the order of the multiplicative group of the field is
82/// not divisible by `n`.
83/// 
84pub fn get_prim_root_of_unity<R>(ring: R, n: usize) -> Option<El<R>>
85    where R: RingStore, 
86        R::Type: FiniteRing + Field
87{
88    let order = BigIntRing::RING.sub(ring.size(&BigIntRing::RING).unwrap(), BigIntRing::RING.one());
89    get_prim_root_of_unity_gen(ring, &int_cast(n.try_into().unwrap(), BigIntRing::RING, StaticRing::<i64>::RING), BigIntRing::RING, &order)
90}
91
92#[stability::unstable(feature = "enable")]
93pub fn get_prim_root_of_unity_zn_gen<R, I>(ring: R, ZZ: &I, n: &El<I>) -> Option<El<R>>
94    where R: RingStore, 
95        R::Type: ZnRing,
96        I: RingStore,
97        I::Type: IntegerRing
98{
99    let order = factor(ZZ, ring.characteristic(ZZ).unwrap()).into_iter().map(|(p, e)| if ZZ.eq_el(&p, &ZZ.int_hom().map(2)) {
100        match e {
101            1 => ZZ.one(),
102            2 => p,
103            e => ZZ.pow(p, e - 2)
104        }
105    } else {
106        ZZ.mul(ZZ.sub_ref_fst(&p, ZZ.one()), ZZ.pow(p, e - 1))
107    }).fold(ZZ.one(), |current, next| if ZZ.is_lt(&current, &next) { next } else { current });
108    get_prim_root_of_unity_gen(ring, n, ZZ, &order)
109}
110
111///
112/// Returns a primitive `n`-th root of unity in the given ring `Z/kZ`,
113/// or `None`, if the order of the multiplicative group of the field is
114/// not divisible by `n`.
115/// 
116/// Note that if `Z/kZ` is not a prime, it may have more than `phi(k)`
117/// primitive roots of unity, in particular there may be `a, b` with
118/// `<a>, <b> <= (Z/kZ)*` both of order `n`, but `<a> n <b> = { 1 }`.
119/// 
120#[stability::unstable(feature = "enable")]
121pub fn get_prim_root_of_unity_zn<R>(ring: R, n: usize) -> Option<El<R>>
122    where R: RingStore, 
123        R::Type: ZnRing
124{
125    get_prim_root_of_unity_zn_gen(ring, &BigIntRing::RING, &int_cast(n as i64, BigIntRing::RING, StaticRing::<i64>::RING))
126}
127
128///
129/// Returns a primitive `2^log2_n`-th root of unity in the given finite field,
130/// or `None`, if the order of the multiplicative group of the field is
131/// not divisible by `2^log2_n`.
132/// 
133pub fn get_prim_root_of_unity_pow2<R>(ring: R, log2_n: usize) -> Option<El<R>>
134    where R: RingStore, 
135        R::Type: FiniteRing + Field
136{
137    let order = BigIntRing::RING.sub(ring.size(&BigIntRing::RING).unwrap(), BigIntRing::RING.one());
138    get_prim_root_of_unity_gen(ring, &BigIntRing::RING.power_of_two(log2_n), BigIntRing::RING, &order)
139}
140
141///
142/// Returns a primitive `n`-th root of unity in the given ring `Z/kZ`,
143/// or `None`, if the order of the multiplicative group of the field is
144/// not divisible by `n`.
145/// 
146/// Note that if `Z/kZ` is not a prime, it may have more than `phi(k)`
147/// primitive roots of unity, in particular there may be `a, b` with
148/// `<a>, <b> <= (Z/kZ)*` both of order `n`, but `<a> n <b> = { 1 }`.
149/// 
150#[stability::unstable(feature = "enable")]
151pub fn get_prim_root_of_unity_pow2_zn<R, I>(ring: R, log2_n: usize) -> Option<El<R>>
152    where R: RingStore, 
153        R::Type: ZnRing
154{
155    get_prim_root_of_unity_zn_gen(ring, &BigIntRing::RING, &BigIntRing::RING.power_of_two(log2_n))
156}
157
158#[cfg(test)]
159use crate::rings::zn::zn_static::{Zn, Fp};
160#[cfg(test)]
161use crate::algorithms::poly_factor::FactorPolyField;
162#[cfg(test)]
163use crate::algorithms::cyclotomic::cyclotomic_polynomial;
164#[cfg(test)]
165use crate::rings::poly::dense_poly::DensePolyRing;
166#[cfg(test)]
167use crate::rings::poly::PolyRingStore;
168#[cfg(test)]
169use crate::rings::extension::galois_field::GaloisField;
170
171#[test]
172fn test_is_prim_root_of_unity() {
173    let ring = Zn::<17>::RING;
174    assert!(is_prim_root_of_unity_pow2(ring, &ring.int_hom().map(2), 3));
175    assert!(!is_prim_root_of_unity_pow2(ring, &ring.int_hom().map(2), 4));
176    assert!(is_prim_root_of_unity_pow2(ring, &ring.int_hom().map(3), 4));
177
178    let ring = Zn::<101>::RING;
179    assert!(is_prim_root_of_unity(&ring, &ring.int_hom().map(36), 5));
180    assert!(is_prim_root_of_unity(&ring, &ring.int_hom().map(3), 100));
181    assert!(is_prim_root_of_unity(&ring, &ring.int_hom().map(5), 25));
182    assert!(!is_prim_root_of_unity(&ring, &ring.int_hom().map(5), 50));
183    assert!(is_prim_root_of_unity(&ring, &ring.int_hom().map(6), 10));
184    assert!(!is_prim_root_of_unity(&ring, &ring.int_hom().map(6), 50));
185
186    let ring = GaloisField::new(23, 2);
187    assert!(is_prim_root_of_unity(&ring, &ring.int_hom().map(-1), 2));
188    assert!(is_prim_root_of_unity(&ring, &ring.int_hom().map(2), 11));
189    let poly_ring = DensePolyRing::new(&ring, "X");
190    let (factorization, _) = <_ as FactorPolyField>::factor_poly(&poly_ring, &cyclotomic_polynomial(&poly_ring, 16));
191    for (mut factor, _) in factorization {
192        let normalization = poly_ring.base_ring().invert(poly_ring.lc(&factor).unwrap()).unwrap();
193        poly_ring.inclusion().mul_assign_map(&mut factor, normalization);
194        assert!(is_prim_root_of_unity(&ring, poly_ring.coefficient_at(&factor, 0), 16));
195        assert!(is_prim_root_of_unity_pow2(&ring, poly_ring.coefficient_at(&factor, 0), 4));
196    }
197}
198
199#[test]
200fn test_get_prim_root_of_unity() {
201    let ring = Fp::<17>::RING;
202    assert!(is_prim_root_of_unity_pow2(&ring, &get_prim_root_of_unity_pow2(&ring, 4).unwrap(), 4));
203    assert!(get_prim_root_of_unity_pow2(&ring, 5).is_none());
204
205    let ring = Fp::<101>::RING;
206    assert!(is_prim_root_of_unity_pow2(&ring, &get_prim_root_of_unity_pow2(&ring, 2).unwrap(), 2));
207    assert!(is_prim_root_of_unity(&ring, &get_prim_root_of_unity(&ring, 25).unwrap(), 25));
208    assert!(get_prim_root_of_unity_pow2(&ring, 3).is_none());
209    assert!(get_prim_root_of_unity(&ring, 125).is_none());
210    
211    let ring = GaloisField::new(23, 2);
212    assert!(is_prim_root_of_unity_pow2(&ring, &get_prim_root_of_unity_pow2(&ring, 4).unwrap(), 4));
213    assert!(get_prim_root_of_unity_pow2(&ring, 5).is_none());
214    assert!(is_prim_root_of_unity(&ring, &get_prim_root_of_unity(&ring, 3).unwrap(), 3));
215
216    let ring = GaloisField::new(17, 16);
217    assert!(is_prim_root_of_unity_pow2(&ring, &get_prim_root_of_unity_pow2(&ring, 4).unwrap(), 4));
218}
219
220#[test]
221fn test_get_prim_root_of_unity_zn() {
222    let ring = Zn::<1>::RING;
223    assert!(get_prim_root_of_unity_zn(&ring, 2).is_none());
224
225    let ring = Fp::<2>::RING;
226    assert!(get_prim_root_of_unity_zn(&ring, 2).is_none());
227
228    let ring = Zn::<4>::RING;
229    assert!(is_prim_root_of_unity(&ring, &get_prim_root_of_unity_zn(&ring, 2).unwrap(), 2));
230    assert!(get_prim_root_of_unity_zn(&ring, 4).is_none());
231
232    let ring = Zn::<8>::RING;
233    assert!(is_prim_root_of_unity(&ring, &get_prim_root_of_unity_zn(&ring, 2).unwrap(), 2));
234    assert!(get_prim_root_of_unity_zn(&ring, 4).is_none());
235
236    let ring = Zn::<16>::RING;
237    assert!(is_prim_root_of_unity(&ring, &get_prim_root_of_unity_zn(&ring, 4).unwrap(), 4));
238    assert!(get_prim_root_of_unity_zn(&ring, 5).is_none());
239
240    let ring = Zn::<15>::RING;
241    assert!(is_prim_root_of_unity(&ring, &get_prim_root_of_unity_zn(&ring, 4).unwrap(), 4));
242    assert!(get_prim_root_of_unity_zn(&ring, 5).is_none());
243
244    let ring = Zn::<75>::RING;
245    assert!(is_prim_root_of_unity(&ring, &get_prim_root_of_unity_zn(&ring, 5).unwrap(), 5));
246    assert!(is_prim_root_of_unity(&ring, &get_prim_root_of_unity_zn(&ring, 4).unwrap(), 4));
247    assert!(get_prim_root_of_unity_zn(&ring, 3).is_none());
248    assert!(get_prim_root_of_unity_zn(&ring, 8).is_none());
249}
feanor_math/algorithms/unity_root.rs

feanor_math/algorithms/
unity_root.rs
