feanor_math/algorithms/
unity_root.rs

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

feanor_math/algorithms/
unity_root.rs
