1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

use crate::ring::*;
use crate::homomorphism::*;
use crate::primitive_int::{StaticRing, StaticRingBase};
use crate::rings::zn::{ZnRing, ZnRingStore};
use crate::divisibility::DivisibilityRingStore;
use crate::integer::IntegerRingStore;

use super::int_factor::factor;

pub fn is_prim_root_of_unity_pow2<R: RingStore>(ring: R, el: &El<R>, log2_n: usize) -> bool {
    if log2_n == 0 {
        return ring.is_one(el);
    }
    ring.is_neg_one(&ring.pow(ring.clone_el(&el), 1 << (log2_n - 1)))
}

pub fn is_root_of_unity<R: RingStore>(ring: R, el: &El<R>, n: usize) -> bool {
    assert!(n >= 1);
    ring.is_one(&ring.pow(ring.clone_el(&el), n))
}

pub fn is_prim_root_of_unity<R: RingStore>(ring: R, el: &El<R>, n: usize) -> bool {
    assert!(n > 1);
    if !is_root_of_unity(&ring, el, n) {
        return false;
    }
    for (p, _) in factor(&StaticRing::<i128>::RING, n as i128) {
        if is_root_of_unity(&ring, el, n / p as usize) {
            return false;
        }
    }
    return true;
}

pub fn get_prim_root_of_unity<R>(ring: R, n: usize) -> Option<El<R>>
    where R: ZnRingStore, R::Type: ZnRing, <R::Type as ZnRing>::IntegerRingBase: CanHomFrom<StaticRingBase<i64>>
{
    assert!(ring.is_field());
    let ZZ = ring.integer_ring();
    let order = ZZ.sub_ref_fst(ring.modulus(), ZZ.one());
    let power = ZZ.checked_div(&order, &ZZ.coerce(&StaticRing::<i64>::RING, n as i64))?;
    
    let mut rng = oorandom::Rand64::new(ZZ.default_hash(ring.modulus()) as u128);
    let mut current = ring.pow_gen(ring.random_element(|| rng.rand_u64()), &power, ZZ);
    while !is_prim_root_of_unity(&ring, &current, n) {
        current = ring.pow_gen(ring.random_element(|| rng.rand_u64()), &power, ZZ);
    }
    assert!(is_prim_root_of_unity(&ring, &current, n));
    return Some(current);
}

pub fn get_prim_root_of_unity_pow2<R>(ring: R, log2_n: usize) -> Option<El<R>>
    where R: ZnRingStore, R::Type: ZnRing, <R::Type as ZnRing>::IntegerRingBase: CanHomFrom<StaticRingBase<i64>>
{
    assert!(ring.is_field());
    let ZZ = ring.integer_ring();
    let order = ZZ.sub_ref_fst(ring.modulus(), ZZ.one());
    let power = ZZ.checked_div(&order, &ZZ.power_of_two(log2_n))?;
    
    let mut rng = oorandom::Rand64::new(ZZ.default_hash(ring.modulus()) as u128);
    let mut current = ring.pow_gen(ring.random_element(|| rng.rand_u64()), &power, ZZ);
    while !is_prim_root_of_unity_pow2(&ring, &current, log2_n) {
        current = ring.pow_gen(ring.random_element(|| rng.rand_u64()), &power, ZZ);
    }
    assert!(is_prim_root_of_unity_pow2(&ring, &current, log2_n));
    return Some(current);
}

#[cfg(test)]
use crate::rings::zn::zn_static::Zn;

#[test]
fn test_is_prim_root_of_unity() {
    let ring = Zn::<17>::RING;
    assert!(is_prim_root_of_unity_pow2(ring, &ring.int_hom().map(2), 3));
    assert!(!is_prim_root_of_unity_pow2(ring, &ring.int_hom().map(2), 4));
    assert!(is_prim_root_of_unity_pow2(ring, &ring.int_hom().map(3), 4));

    let ring = Zn::<101>::RING;
    assert!(is_prim_root_of_unity(&ring, &ring.int_hom().map(36), 5));
    assert!(is_prim_root_of_unity(&ring, &ring.int_hom().map(3), 100));
    assert!(is_prim_root_of_unity(&ring, &ring.int_hom().map(5), 25));
    assert!(!is_prim_root_of_unity(&ring, &ring.int_hom().map(5), 50));
    assert!(is_prim_root_of_unity(&ring, &ring.int_hom().map(6), 10));
    assert!(!is_prim_root_of_unity(&ring, &ring.int_hom().map(6), 50));
}