eth_pairings/
traits.rs

1use std::fmt;
2
3/// This trait represents an element of a field.
4pub trait FieldElement:
5    Sized 
6    + Eq 
7    + Clone 
8    + Send 
9    + Sync 
10    + fmt::Debug 
11    + fmt::Display
12{
13    /// Returns true iff this element is zero.
14    fn is_zero(&self) -> bool;
15
16    /// Squares this element.
17    fn square(&mut self);
18
19    /// Doubles this element.
20    fn double(&mut self);
21
22    /// Negates this element.
23    fn negate(&mut self);
24
25    /// Adds another element to this element.
26    fn add_assign(&mut self, other: &Self);
27
28    /// Subtracts another element from this element.
29    fn sub_assign(&mut self, other: &Self);
30
31    /// Multiplies another element by this element.
32    fn mul_assign(&mut self, other: &Self);
33
34    /// Computes the multiplicative inverse of this element, if nonzero.
35    fn inverse(&self) -> Option<Self>;
36
37    /// Exponentiates this element by a number represented with `u64` limbs,
38    /// least significant digit first.
39    fn pow<S: AsRef<[u64]>>(&self, exp: S) -> Self;
40
41    fn conjugate(&mut self);
42
43    fn mul_by_nonresidue<EXT: FieldExtension<Element = Self>>(&mut self, for_extension: &EXT);
44
45    fn frobenius_map(&mut self, power: usize);
46}
47
48pub trait ZeroAndOne {
49    type Params;
50    fn zero(f: Self::Params) -> Self;
51    fn one(f: Self::Params) -> Self;
52}
53
54pub trait FieldExtension {
55    const EXTENSION_DEGREE: usize;
56
57    type Element;
58
59    fn multiply_by_non_residue(&self, el: &mut Self::Element);
60}
61
62#[derive(Debug)]
63pub struct BitIterator<E> {
64    t: E,
65    n: usize,
66}
67
68impl<E: AsRef<[u64]>> BitIterator<E> {
69    pub fn new(t: E) -> Self {
70        let n = t.as_ref().len() * 64;
71
72        BitIterator { t, n }
73    }
74}
75
76impl<E: AsRef<[u64]>> Iterator for BitIterator<E> {
77    type Item = bool;
78
79    fn next(&mut self) -> Option<bool> {
80        if self.n == 0 {
81            None
82        } else {
83            self.n -= 1;
84            let part = self.n / 64;
85            let bit = self.n - (64 * part);
86
87            Some(self.t.as_ref()[part] & (1 << bit) > 0)
88        }
89    }
90}
91
92
93// this bit iterator skips initial zeroes until reaches MSB
94#[derive(Debug)]
95pub struct MsbBitIterator<E> {
96    t: E,
97    n: usize,
98}
99
100impl<E: AsRef<[u64]>> MsbBitIterator<E> {
101    pub fn new(t: E) -> Self {
102        let r = t.as_ref();
103        let mut n = r.len() * 64;
104        let mut found_one = false;
105        for limb in (0..r.len()).rev() {
106            if found_one {
107                break;
108            }
109            if r[limb] == 0 {
110                n -= 64;
111                continue;
112            }
113            // counting from MSB in limb
114            for bit in 0..64 {
115                if r[limb] & (1 << (63 - bit)) == 0 {
116                    n -= 1;
117                } else {
118                    found_one = true;
119                    break;
120                }
121            }
122        }
123
124        MsbBitIterator { t, n }
125    }
126}
127
128impl<E: AsRef<[u64]>> Iterator for MsbBitIterator<E> {
129    type Item = bool;
130
131    fn next(&mut self) -> Option<bool> {
132        if self.n == 0 {
133            None
134        } else {
135            self.n -= 1;
136            let part = self.n / 64;
137            let bit = self.n - (64 * part);
138
139            Some(self.t.as_ref()[part] & (1 << bit) > 0)
140        }
141    }
142}
143
144// this is LSB bit iterator
145#[derive(Debug)]
146pub struct LsbBitIterator<E> {
147    t: E,
148    n: usize,
149    max: usize
150}
151
152impl<E: AsRef<[u64]>> LsbBitIterator<E> {
153    pub fn new(t: E) -> Self {
154        let max = t.as_ref().len() * 64;
155        let n = 0;
156        LsbBitIterator { t, n, max}
157    }
158}
159
160impl<E: AsRef<[u64]>> Iterator for LsbBitIterator<E> {
161    type Item = bool;
162
163    fn next(&mut self) -> Option<bool> {
164        if self.n == self.max {
165            None
166        } else {
167            let part = self.n / 64;
168            let bit = self.n - (64 * part);
169            self.n += 1;
170
171            Some(self.t.as_ref()[part] & (1 << bit) > 0)
172        }
173    }
174}
175
176// /// This trait represents an element of a field that has a square root operation described for it.
177// pub trait SqrtFieldElement: FieldElement {
178//     /// Returns the Legendre symbol of the field element.
179//     fn legendre(&self) -> LegendreSymbol;
180
181//     /// Returns the square root of the field element, if it is
182//     /// quadratic residue.
183//     fn sqrt(&self) -> Option<Self>;
184// }
185
186// #[derive(Debug, PartialEq)]
187// pub enum LegendreSymbol {
188//     Zero = 0,
189//     QuadraticResidue = 1,
190//     QuadraticNonResidue = -1,
191// }
192
193
194#[cfg(test)]
195mod bit_iter_tests {
196    #[test]
197    fn test_msb_iter() {
198        use super::MsbBitIterator;
199        let word: u64 = 0x0103;
200        let iter = MsbBitIterator::new([word, 0]);
201        let bits: Vec<bool> = iter.collect();
202        assert!(bits.len() == 9);
203        assert!(bits == vec![true,
204                            false, false, false, false,
205                            false, false, true, true]);
206    }
207}
eth_pairings/traits.rs

eth_pairings/
traits.rs
