feanor_math/algorithms/
unity_root.rs

1use crate::field::Field;
2use crate::integer::int_cast;
3use crate::integer::BigIntRing;
4use crate::integer::IntegerRing;
5use crate::ring::*;
6use crate::primitive_int::*;
7use crate::rings::finite::*;
8use crate::divisibility::DivisibilityRingStore;
9use crate::integer::IntegerRingStore;
10use crate::ordered::OrderedRingStore;
11
12use super::int_factor::factor;
13
14#[stability::unstable(feature = "enable")]
15pub fn is_prim_root_of_unity_pow2<R: RingStore>(ring: R, el: &El<R>, log2_n: usize) -> bool {
16    if log2_n == 0 {
17        return ring.is_one(el);
18    }
19    ring.is_neg_one(&ring.pow(ring.clone_el(&el), 1 << (log2_n - 1)))
20}
21
22#[stability::unstable(feature = "enable")]
23pub fn is_root_of_unity<R: RingStore>(ring: R, el: &El<R>, n: usize) -> bool {
24    is_root_of_unity_gen(ring, el, &n.try_into().unwrap(), StaticRing::<i64>::RING)
25}
26
27#[stability::unstable(feature = "enable")]
28pub fn is_root_of_unity_gen<R: RingStore, I: RingStore>(ring: R, el: &El<R>, n: &El<I>, ZZ: I) -> bool
29    where 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
42    where I: RingStore + Copy,
43        I::Type: IntegerRing
44{
45    if !is_root_of_unity_gen(&ring, el, n, ZZ) {
46        return false;
47    }
48    for (p, _) in factor(&ZZ, ZZ.clone_el(n)) {
49        if is_root_of_unity_gen(&ring, el, &ZZ.checked_div(n, &p).unwrap(), ZZ) {
50            return false;
51        }
52    }
53    return true;
54}
55
56#[stability::unstable(feature = "enable")]
57pub fn get_prim_root_of_unity_gen<R, I>(ring: R, n: &El<I>, ZZ: I) -> Option<El<R>>
58    where R: RingStore, 
59        R::Type: FiniteRing + Field,
60        I: RingStore + Copy,
61        I::Type: IntegerRing
62{
63    let order = ZZ.sub(ring.size(&ZZ).unwrap(), ZZ.one());
64    let power = ZZ.checked_div(&order, n)?;
65    
66    let mut rng = oorandom::Rand64::new(ZZ.default_hash(&ring.size(&ZZ).unwrap()) as u128);
67    let mut current = ring.pow_gen(ring.random_element(|| rng.rand_u64()), &power, ZZ);
68    while !is_prim_root_of_unity_gen(&ring, &current, n, ZZ) {
69        current = ring.pow_gen(ring.random_element(|| rng.rand_u64()), &power, ZZ);
70    }
71    debug_assert!(is_prim_root_of_unity_gen(&ring, &current, n, ZZ));
72    return Some(current);
73}
74
75///
76/// Returns a primitive `n`-th root of unity in the given finite field,
77/// or `None`, if the order of the multiplicative group of the field is
78/// not divisible by `n`.
79/// 
80pub fn get_prim_root_of_unity<R>(ring: R, n: usize) -> Option<El<R>>
81    where R: RingStore, 
82        R::Type: FiniteRing + Field
83{
84    get_prim_root_of_unity_gen(ring, &int_cast(n.try_into().unwrap(), BigIntRing::RING, StaticRing::<i64>::RING), BigIntRing::RING)
85}
86
87///
88/// Returns a primitive `2^log2_n`-th root of unity in the given finite field,
89/// or `None`, if the order of the multiplicative group of the field is
90/// not divisible by `2^log2_n`.
91/// 
92pub fn get_prim_root_of_unity_pow2<R>(ring: R, log2_n: usize) -> Option<El<R>>
93    where R: RingStore, 
94        R::Type: FiniteRing + Field
95{
96    const ZZ: BigIntRing = BigIntRing::RING;
97    let order = ZZ.sub(ring.size(&ZZ).unwrap(), ZZ.one());
98    let power = ZZ.checked_div(&order, &ZZ.power_of_two(log2_n))?;
99    
100    let mut rng = oorandom::Rand64::new(ZZ.default_hash(&ring.size(&ZZ).unwrap()) as u128);
101    let mut current = ring.pow_gen(ring.random_element(|| rng.rand_u64()), &power, ZZ);
102    while !is_prim_root_of_unity_pow2(&ring, &current, log2_n) {
103        current = ring.pow_gen(ring.random_element(|| rng.rand_u64()), &power, ZZ);
104    }
105    assert!(is_prim_root_of_unity_pow2(&ring, &current, log2_n));
106    return Some(current);
107}
108
109#[cfg(test)]
110use crate::rings::zn::zn_static::{Zn, Fp};
111#[cfg(test)]
112use crate::algorithms::poly_factor::FactorPolyField;
113#[cfg(test)]
114use crate::homomorphism::*;
115#[cfg(test)]
116use crate::algorithms::cyclotomic::cyclotomic_polynomial;
117#[cfg(test)]
118use crate::rings::poly::dense_poly::DensePolyRing;
119#[cfg(test)]
120use crate::rings::poly::PolyRingStore;
121#[cfg(test)]
122use crate::rings::extension::galois_field::GaloisField;
123
124#[test]
125fn test_is_prim_root_of_unity() {
126    let ring = Zn::<17>::RING;
127    assert!(is_prim_root_of_unity_pow2(ring, &ring.int_hom().map(2), 3));
128    assert!(!is_prim_root_of_unity_pow2(ring, &ring.int_hom().map(2), 4));
129    assert!(is_prim_root_of_unity_pow2(ring, &ring.int_hom().map(3), 4));
130
131    let ring = Zn::<101>::RING;
132    assert!(is_prim_root_of_unity(&ring, &ring.int_hom().map(36), 5));
133    assert!(is_prim_root_of_unity(&ring, &ring.int_hom().map(3), 100));
134    assert!(is_prim_root_of_unity(&ring, &ring.int_hom().map(5), 25));
135    assert!(!is_prim_root_of_unity(&ring, &ring.int_hom().map(5), 50));
136    assert!(is_prim_root_of_unity(&ring, &ring.int_hom().map(6), 10));
137    assert!(!is_prim_root_of_unity(&ring, &ring.int_hom().map(6), 50));
138
139    let ring = GaloisField::new(23, 2);
140    assert!(is_prim_root_of_unity(&ring, &ring.int_hom().map(-1), 2));
141    assert!(is_prim_root_of_unity(&ring, &ring.int_hom().map(2), 11));
142    let poly_ring = DensePolyRing::new(&ring, "X");
143    let (factorization, _) = <_ as FactorPolyField>::factor_poly(&poly_ring, &cyclotomic_polynomial(&poly_ring, 16));
144    for (mut factor, _) in factorization {
145        let normalization = poly_ring.base_ring().invert(poly_ring.lc(&factor).unwrap()).unwrap();
146        poly_ring.inclusion().mul_assign_map(&mut factor, normalization);
147        assert!(is_prim_root_of_unity(&ring, poly_ring.coefficient_at(&factor, 0), 16));
148        assert!(is_prim_root_of_unity_pow2(&ring, poly_ring.coefficient_at(&factor, 0), 4));
149    }
150}
151
152#[test]
153fn test_get_prim_root_of_unity() {
154    let ring = Fp::<17>::RING;
155    assert!(is_prim_root_of_unity_pow2(&ring, &get_prim_root_of_unity_pow2(&ring, 4).unwrap(), 4));
156    assert!(get_prim_root_of_unity_pow2(&ring, 5).is_none());
157
158    let ring = Fp::<101>::RING;
159    assert!(is_prim_root_of_unity_pow2(&ring, &get_prim_root_of_unity_pow2(&ring, 2).unwrap(), 2));
160    assert!(is_prim_root_of_unity(&ring, &get_prim_root_of_unity(&ring, 25).unwrap(), 25));
161    assert!(get_prim_root_of_unity_pow2(&ring, 3).is_none());
162    assert!(get_prim_root_of_unity(&ring, 125).is_none());
163    
164    let ring = GaloisField::new(23, 2);
165    assert!(is_prim_root_of_unity_pow2(&ring, &get_prim_root_of_unity_pow2(&ring, 4).unwrap(), 4));
166    assert!(get_prim_root_of_unity_pow2(&ring, 5).is_none());
167    assert!(is_prim_root_of_unity(&ring, &get_prim_root_of_unity(&ring, 3).unwrap(), 3));
168
169    let ring = GaloisField::new(17, 16);
170    assert!(is_prim_root_of_unity_pow2(&ring, &get_prim_root_of_unity_pow2(&ring, 4).unwrap(), 4));
171}
feanor_math/algorithms/unity_root.rs

feanor_math/algorithms/
unity_root.rs
