lambdaworks_math/circle/
cosets.rs

1extern crate alloc;
2use crate::circle::point::CirclePoint;
3use crate::field::fields::mersenne31::field::Mersenne31Field;
4#[cfg(feature = "alloc")]
5use alloc::vec::Vec;
6
7/// Given g_n, a generator of the subgroup of size n of the circle, i.e. <g_n>,
8/// and given a shift, that is a another point of the circle,
9/// we define the coset shift + <g_n> which is the set of all the points in
10/// <g_n> plus the shift.
11/// For example, if <g_4> = {p1, p2, p3, p4}, then g_8 + <g_4> = {g_8 + p1, g_8 + p2, g_8 + p3, g_8 + p4}.
12
13#[derive(Debug, Clone)]
14pub struct Coset {
15    // Coset: shift + <g_n> where n = 2^{log_2_size}.
16    // Example: g_16 + <g_8>, n = 8, log_2_size = 3, shift = g_16.
17    pub log_2_size: u32, //TODO: Change log_2_size to u8 because log_2_size < 31.
18    pub shift: CirclePoint<Mersenne31Field>,
19}
20
21impl Coset {
22    pub fn new(log_2_size: u32, shift: CirclePoint<Mersenne31Field>) -> Self {
23        Coset { log_2_size, shift }
24    }
25
26    /// Returns the coset g_2n + <g_n>
27    pub fn new_standard(log_2_size: u32) -> Self {
28        // shift is a generator of the subgroup of order 2n = 2^{log_2_size + 1}.
29        let shift = CirclePoint::get_generator_of_subgroup(log_2_size + 1);
30        Coset { log_2_size, shift }
31    }
32
33    /// Returns g_n, the generator of the subgroup of order n = 2^log_2_size.
34    pub fn get_generator(&self) -> CirclePoint<Mersenne31Field> {
35        CirclePoint::GENERATOR.repeated_double(31 - self.log_2_size)
36    }
37
38    /// Given a standard coset g_2n + <g_n>, returns the subcoset with half size g_2n + <g_{n/2}>
39    pub fn half_coset(coset: Self) -> Self {
40        Coset {
41            log_2_size: coset.log_2_size - 1,
42            shift: coset.shift,
43        }
44    }
45
46    /// Given a coset shift + G returns the coset -shift + G.
47    /// Note that (g_2n + <g_{n/2}>) U (-g_2n + <g_{n/2}>) = g_2n + <g_n>.
48    pub fn conjugate(coset: Self) -> Self {
49        Coset {
50            log_2_size: coset.log_2_size,
51            shift: coset.shift.conjugate(),
52        }
53    }
54
55    /// Returns the vector of shift + g for every g in <g_n>.
56    /// where g = i * g_n for i = 0, ..., n-1.
57    #[cfg(feature = "alloc")]
58    pub fn get_coset_points(coset: &Self) -> Vec<CirclePoint<Mersenne31Field>> {
59        // g_n the generator of the subgroup of order n.
60        let generator_n = CirclePoint::get_generator_of_subgroup(coset.log_2_size);
61        let size: usize = 1 << coset.log_2_size;
62        core::iter::successors(Some(coset.shift.clone()), move |prev| {
63            Some(prev + &generator_n)
64        })
65        .take(size)
66        .collect()
67    }
68}
69
70#[cfg(test)]
71mod tests {
72    use super::*;
73
74    #[test]
75    fn coset_points_vector_has_right_size() {
76        let coset = Coset::new_standard(3);
77        let points = Coset::get_coset_points(&coset);
78        assert_eq!(1 << coset.log_2_size, points.len())
79    }
80
81    #[test]
82    fn antipode_of_coset_point_is_in_coset() {
83        let coset = Coset::new_standard(3);
84        let points = Coset::get_coset_points(&coset);
85        let point = points[2].clone();
86        let anitpode_point = points[6].clone();
87        assert_eq!(anitpode_point, point.antipode())
88    }
89
90    #[test]
91    fn coset_generator_has_right_order() {
92        let coset = Coset::new(2, CirclePoint::GENERATOR * 3);
93        let generator_n = coset.get_generator();
94        assert_eq!(generator_n.repeated_double(2), CirclePoint::zero());
95    }
96}
lambdaworks_math/circle/cosets.rs

lambdaworks_math/circle/
cosets.rs
