plonky2_field/
cosets.rs

1use alloc::vec::Vec;
2
3use num::bigint::BigUint;
4
5use crate::types::Field;
6
7/// Finds a set of shifts that result in unique cosets for the multiplicative subgroup of size
8/// `2^subgroup_bits`.
9pub fn get_unique_coset_shifts<F: Field>(subgroup_size: usize, num_shifts: usize) -> Vec<F> {
10    // From Lagrange's theorem.
11    let num_cosets = (F::order() - 1u32) / (subgroup_size as u32);
12    assert!(
13        BigUint::from(num_shifts) <= num_cosets,
14        "The subgroup does not have enough distinct cosets"
15    );
16
17    // Let g be a generator of the entire multiplicative group. Let n be the order of the subgroup.
18    // The subgroup can be written as <g^(|F*| / n)>. We can use g^0, ..., g^(num_shifts - 1) as our
19    // shifts, since g^i <g^(|F*| / n)> are distinct cosets provided i < |F*| / n, which we checked.
20    F::MULTIPLICATIVE_GROUP_GENERATOR
21        .powers()
22        .take(num_shifts)
23        .collect()
24}
25
26#[cfg(test)]
27mod tests {
28    use std::collections::HashSet;
29
30    use crate::cosets::get_unique_coset_shifts;
31    use crate::goldilocks_field::GoldilocksField;
32    use crate::types::Field;
33
34    #[test]
35    fn distinct_cosets() {
36        type F = GoldilocksField;
37        const SUBGROUP_BITS: usize = 5;
38        const NUM_SHIFTS: usize = 50;
39
40        let generator = F::primitive_root_of_unity(SUBGROUP_BITS);
41        let subgroup_size = 1 << SUBGROUP_BITS;
42
43        let shifts = get_unique_coset_shifts::<F>(subgroup_size, NUM_SHIFTS);
44
45        let mut union = HashSet::new();
46        for shift in shifts {
47            let coset = F::cyclic_subgroup_coset_known_order(generator, shift, subgroup_size);
48            assert!(
49                coset.into_iter().all(|x| union.insert(x)),
50                "Duplicate element!"
51            );
52        }
53    }
54}
plonky2_field/cosets.rs

plonky2_field/
cosets.rs
