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 as i64), 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 as i64), 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#[stability::unstable(feature = "enable")]
76pub fn get_prim_root_of_unity<R>(ring: R, n: usize) -> Option<El<R>>
77    where R: RingStore, 
78        R::Type: FiniteRing + Field
79{
80    get_prim_root_of_unity_gen(ring, &int_cast(n as i64, BigIntRing::RING, StaticRing::<i64>::RING), BigIntRing::RING)
81}
82
83#[stability::unstable(feature = "enable")]
84pub fn get_prim_root_of_unity_pow2<R>(ring: R, log2_n: usize) -> Option<El<R>>
85    where R: RingStore, 
86        R::Type: FiniteRing + Field
87{
88    const ZZ: BigIntRing = BigIntRing::RING;
89    let order = ZZ.sub(ring.size(&ZZ).unwrap(), ZZ.one());
90    let power = ZZ.checked_div(&order, &ZZ.power_of_two(log2_n))?;
91    
92    let mut rng = oorandom::Rand64::new(ZZ.default_hash(&ring.size(&ZZ).unwrap()) as u128);
93    let mut current = ring.pow_gen(ring.random_element(|| rng.rand_u64()), &power, ZZ);
94    while !is_prim_root_of_unity_pow2(&ring, &current, log2_n) {
95        current = ring.pow_gen(ring.random_element(|| rng.rand_u64()), &power, ZZ);
96    }
97    assert!(is_prim_root_of_unity_pow2(&ring, &current, log2_n));
98    return Some(current);
99}
100
101#[cfg(test)]
102use crate::rings::zn::zn_static::{Zn, Fp};
103#[cfg(test)]
104use crate::algorithms::poly_factor::FactorPolyField;
105#[cfg(test)]
106use crate::homomorphism::*;
107#[cfg(test)]
108use crate::algorithms::cyclotomic::cyclotomic_polynomial;
109#[cfg(test)]
110use crate::rings::poly::dense_poly::DensePolyRing;
111#[cfg(test)]
112use crate::rings::poly::PolyRingStore;
113#[cfg(test)]
114use crate::rings::extension::galois_field::GaloisField;
115
116#[test]
117fn test_is_prim_root_of_unity() {
118    let ring = Zn::<17>::RING;
119    assert!(is_prim_root_of_unity_pow2(ring, &ring.int_hom().map(2), 3));
120    assert!(!is_prim_root_of_unity_pow2(ring, &ring.int_hom().map(2), 4));
121    assert!(is_prim_root_of_unity_pow2(ring, &ring.int_hom().map(3), 4));
122
123    let ring = Zn::<101>::RING;
124    assert!(is_prim_root_of_unity(&ring, &ring.int_hom().map(36), 5));
125    assert!(is_prim_root_of_unity(&ring, &ring.int_hom().map(3), 100));
126    assert!(is_prim_root_of_unity(&ring, &ring.int_hom().map(5), 25));
127    assert!(!is_prim_root_of_unity(&ring, &ring.int_hom().map(5), 50));
128    assert!(is_prim_root_of_unity(&ring, &ring.int_hom().map(6), 10));
129    assert!(!is_prim_root_of_unity(&ring, &ring.int_hom().map(6), 50));
130
131    let ring = GaloisField::new(23, 2);
132    assert!(is_prim_root_of_unity(&ring, &ring.int_hom().map(-1), 2));
133    assert!(is_prim_root_of_unity(&ring, &ring.int_hom().map(2), 11));
134    let poly_ring = DensePolyRing::new(&ring, "X");
135    let (factorization, _) = <_ as FactorPolyField>::factor_poly(&poly_ring, &cyclotomic_polynomial(&poly_ring, 16));
136    for (mut factor, _) in factorization {
137        let normalization = poly_ring.base_ring().invert(poly_ring.lc(&factor).unwrap()).unwrap();
138        poly_ring.inclusion().mul_assign_map(&mut factor, normalization);
139        assert!(is_prim_root_of_unity(&ring, poly_ring.coefficient_at(&factor, 0), 16));
140        assert!(is_prim_root_of_unity_pow2(&ring, poly_ring.coefficient_at(&factor, 0), 4));
141    }
142}
143
144#[test]
145fn test_get_prim_root_of_unity() {
146    let ring = Fp::<17>::RING;
147    assert!(is_prim_root_of_unity_pow2(&ring, &get_prim_root_of_unity_pow2(&ring, 4).unwrap(), 4));
148    assert!(get_prim_root_of_unity_pow2(&ring, 5).is_none());
149
150    let ring = Fp::<101>::RING;
151    assert!(is_prim_root_of_unity_pow2(&ring, &get_prim_root_of_unity_pow2(&ring, 2).unwrap(), 2));
152    assert!(is_prim_root_of_unity(&ring, &get_prim_root_of_unity(&ring, 25).unwrap(), 25));
153    assert!(get_prim_root_of_unity_pow2(&ring, 3).is_none());
154    assert!(get_prim_root_of_unity(&ring, 125).is_none());
155    
156    let ring = GaloisField::new(23, 2);
157    assert!(is_prim_root_of_unity_pow2(&ring, &get_prim_root_of_unity_pow2(&ring, 4).unwrap(), 4));
158    assert!(get_prim_root_of_unity_pow2(&ring, 5).is_none());
159    assert!(is_prim_root_of_unity(&ring, &get_prim_root_of_unity(&ring, 3).unwrap(), 3));
160
161    let ring = GaloisField::new(17, 16);
162    assert!(is_prim_root_of_unity_pow2(&ring, &get_prim_root_of_unity_pow2(&ring, 4).unwrap(), 4));
163}
feanor_math/algorithms/unity_root.rs

feanor_math/algorithms/
unity_root.rs
