lambdaworks_math/field/
traits.rs

1use super::{element::FieldElement, errors::FieldError};
2use crate::traits::ByteConversion;
3use crate::{errors::CreationError, unsigned_integer::traits::IsUnsignedInteger};
4use core::fmt::Debug;
5
6/// Represents different configurations that powers of roots of unity can be in. Some of these may
7/// be necessary for FFT (as twiddle factors).
8#[derive(Clone, Copy)]
9pub enum RootsConfig {
10    Natural,            // w^0, w^1, w^2...
11    NaturalInversed,    // w^0, w^-1, w^-2...
12    BitReverse,         // same as first but exponents are bit-reversed.
13    BitReverseInversed, // same as above but exponents are negated.
14}
15
16/// Represents the subfield relation between two fields.
17pub trait IsSubFieldOf<F: IsField>: IsField {
18    fn mul(a: &Self::BaseType, b: &F::BaseType) -> F::BaseType;
19    fn add(a: &Self::BaseType, b: &F::BaseType) -> F::BaseType;
20    fn div(a: &Self::BaseType, b: &F::BaseType) -> Result<F::BaseType, FieldError>;
21    fn sub(a: &Self::BaseType, b: &F::BaseType) -> F::BaseType;
22    fn embed(a: Self::BaseType) -> F::BaseType;
23    #[cfg(feature = "alloc")]
24    fn to_subfield_vec(b: F::BaseType) -> alloc::vec::Vec<Self::BaseType>;
25}
26
27impl<F> IsSubFieldOf<F> for F
28where
29    F: IsField,
30{
31    #[inline(always)]
32    fn mul(a: &Self::BaseType, b: &F::BaseType) -> F::BaseType {
33        F::mul(a, b)
34    }
35
36    #[inline(always)]
37    fn add(a: &Self::BaseType, b: &F::BaseType) -> F::BaseType {
38        F::add(a, b)
39    }
40
41    #[inline(always)]
42    fn sub(a: &Self::BaseType, b: &F::BaseType) -> F::BaseType {
43        F::sub(a, b)
44    }
45
46    #[inline(always)]
47    fn div(a: &Self::BaseType, b: &F::BaseType) -> Result<Self::BaseType, FieldError> {
48        F::div(a, b)
49    }
50
51    #[inline(always)]
52    fn embed(a: Self::BaseType) -> F::BaseType {
53        a
54    }
55
56    #[cfg(feature = "alloc")]
57    fn to_subfield_vec(b: F::BaseType) -> alloc::vec::Vec<Self::BaseType> {
58        alloc::vec![b]
59    }
60}
61
62/// Trait to define necessary parameters for FFT-friendly Fields.
63/// Two-Adic fields are ones whose order is of the form  $2^n k + 1$.
64/// Here $n$ is usually called the *two-adicity* of the field. The
65/// reason we care about it is that in an $n$-adic field there are $2^j$-roots
66/// of unity for every `j` between 1 and n, which is needed to do Fast Fourier.
67/// A two-adic primitive root of unity is a number w that satisfies w^(2^n) = 1
68/// and w^(j) != 1 for every j below 2^n. With this primitive root we can generate
69/// any other root of unity we need to perform FFT.
70pub trait IsFFTField: IsField {
71    const TWO_ADICITY: u64;
72    const TWO_ADIC_PRIMITVE_ROOT_OF_UNITY: Self::BaseType;
73
74    /// Used for searching this field's implementation in other languages, e.g in MSL
75    /// for executing parallel operations with the Metal API.
76    fn field_name() -> &'static str {
77        ""
78    }
79
80    /// Returns a primitive root of unity of order $2^{order}$.
81    /// This is an element w such that w^{2^order} = 1 modulo p and
82    /// w^k <> 1 modulo p for k not congruent to 2^order
83    fn get_primitive_root_of_unity(order: u64) -> Result<FieldElement<Self>, FieldError> {
84        let two_adic_primitive_root_of_unity =
85            FieldElement::new(Self::TWO_ADIC_PRIMITVE_ROOT_OF_UNITY);
86        if order == 0 {
87            return Ok(FieldElement::one());
88        }
89        if order > Self::TWO_ADICITY {
90            return Err(FieldError::RootOfUnityError(order));
91        }
92        let log_power = Self::TWO_ADICITY - order;
93        let root = (0..log_power).fold(two_adic_primitive_root_of_unity, |acc, _| acc.square());
94        Ok(root)
95    }
96}
97
98/// Trait to add field behaviour to a struct.
99pub trait IsField: Debug + Clone {
100    /// The underlying base type for representing elements from the field.
101    // TODO: Relax Unpin for non cuda usage
102    type BaseType: Clone + Debug + Unpin + ByteConversion + Default;
103
104    /// Returns the sum of `a` and `b`.
105    fn add(a: &Self::BaseType, b: &Self::BaseType) -> Self::BaseType;
106
107    /// Returns the double of `a`.
108    fn double(a: &Self::BaseType) -> Self::BaseType {
109        Self::add(a, a)
110    }
111
112    /// Returns the multiplication of `a` and `b`.
113    fn mul(a: &Self::BaseType, b: &Self::BaseType) -> Self::BaseType;
114
115    /// Returns the multiplication of `a` and `a`.
116    fn square(a: &Self::BaseType) -> Self::BaseType {
117        Self::mul(a, a)
118    }
119
120    /// Returns the power of `a` to the `T`, a^T
121    /// Uses the square and multiply algorithm, which takes O(log2(T)) steps
122    /// This is a non-constant time implementation!
123    fn pow<T>(a: &Self::BaseType, mut exponent: T) -> Self::BaseType
124    where
125        T: IsUnsignedInteger,
126    {
127        let zero = T::from(0);
128        let one = T::from(1);
129
130        if exponent == zero {
131            Self::one()
132        } else if exponent == one {
133            a.clone()
134        } else {
135            let mut result = a.clone();
136
137            while exponent & one == zero {
138                result = Self::square(&result);
139                exponent >>= 1;
140            }
141
142            if exponent == zero {
143                result
144            } else {
145                let mut base = result.clone();
146                exponent >>= 1;
147
148                while exponent != zero {
149                    base = Self::square(&base);
150                    if exponent & one == one {
151                        result = Self::mul(&result, &base);
152                    }
153                    exponent >>= 1;
154                }
155
156                result
157            }
158        }
159    }
160
161    /// Returns the subtraction of `a` and `b`.
162    fn sub(a: &Self::BaseType, b: &Self::BaseType) -> Self::BaseType;
163
164    /// Returns the additive inverse of `a`.
165    fn neg(a: &Self::BaseType) -> Self::BaseType;
166
167    /// Returns the multiplicative inverse of `a`.
168    fn inv(a: &Self::BaseType) -> Result<Self::BaseType, FieldError>;
169
170    /// Returns the division of `a` and `b`.
171    fn div(a: &Self::BaseType, b: &Self::BaseType) -> Result<Self::BaseType, FieldError>;
172
173    /// Returns a boolean indicating whether `a` and `b` are equal or not.
174    fn eq(a: &Self::BaseType, b: &Self::BaseType) -> bool;
175
176    /// Returns the additive neutral element.
177    fn zero() -> Self::BaseType {
178        Self::BaseType::default()
179    }
180
181    /// Returns the multiplicative neutral element.
182    fn one() -> Self::BaseType;
183
184    /// Returns the element `x * 1` where 1 is the multiplicative neutral element.
185    fn from_u64(x: u64) -> Self::BaseType;
186
187    /// Takes as input an element of BaseType and returns the internal representation
188    /// of that element in the field.
189    fn from_base_type(x: Self::BaseType) -> Self::BaseType;
190}
191
192/// Provides the Legendre symbol for an element modulo p
193/// The Legendre symbol is Zero if a is congruent to 0 modulo p
194/// It is equal to One if a is a square modulo p (which means it has a square root)
195/// It is equal to MinusOne if a is not a square modulo p
196/// For example, p - 1 is not a square modulo p if p is congruent to 3 modulo 4
197/// This applies to Mersenne primes, for example
198#[derive(PartialEq)]
199pub enum LegendreSymbol {
200    MinusOne,
201    Zero,
202    One,
203}
204
205pub trait IsPrimeField: IsField {
206    type RepresentativeType: IsUnsignedInteger;
207
208    /// Returns the integer representative in
209    /// the range [0, p-1], where p the modulus
210    fn representative(a: &Self::BaseType) -> Self::RepresentativeType;
211
212    /// Returns p - 1, which is -1 mod p
213    fn modulus_minus_one() -> Self::RepresentativeType {
214        Self::representative(&Self::neg(&Self::one()))
215    }
216
217    /// Creates a BaseType from a Hex String
218    /// 0x is optional
219    /// Returns an `CreationError::InvalidHexString`if the value is not a hexstring
220    fn from_hex(hex_string: &str) -> Result<Self::BaseType, CreationError>;
221
222    #[cfg(feature = "std")]
223    /// Creates a hexstring from a `FieldElement` without `0x`.
224    fn to_hex(a: &Self::BaseType) -> String;
225
226    /// Returns the number of bits of the max element of the field, as per field documentation, not internal representation.
227    /// This is `log2(max FE)` rounded up
228    fn field_bit_size() -> usize;
229
230    /// Computes the Legendre symbol using Euler's criterion
231    /// This is important to ensure that we find the square root of elements that are quadratic residues
232    fn legendre_symbol(a: &Self::BaseType) -> LegendreSymbol {
233        let symbol = Self::pow(a, Self::modulus_minus_one() >> 1);
234
235        match symbol {
236            x if Self::eq(&x, &Self::zero()) => LegendreSymbol::Zero,
237            x if Self::eq(&x, &Self::one()) => LegendreSymbol::One,
238            _ => LegendreSymbol::MinusOne,
239        }
240    }
241
242    /// Returns the two square roots of `self` if they exist and
243    /// `None` otherwise
244    fn sqrt(a: &Self::BaseType) -> Option<(Self::BaseType, Self::BaseType)> {
245        match Self::legendre_symbol(a) {
246            LegendreSymbol::Zero => return Some((Self::zero(), Self::zero())),
247            LegendreSymbol::MinusOne => return None,
248            LegendreSymbol::One => (),
249        };
250
251        let integer_one = Self::RepresentativeType::from(1_u16);
252        let mut s: usize = 0;
253        let mut q = Self::modulus_minus_one();
254
255        while q & integer_one != integer_one {
256            s += 1;
257            q >>= 1;
258        }
259
260        let mut c = {
261            // Calculate a non residue:
262            let mut non_qr = Self::from_u64(2);
263            while Self::legendre_symbol(&non_qr) != LegendreSymbol::MinusOne {
264                non_qr = Self::add(&non_qr, &Self::one());
265            }
266
267            Self::pow(&non_qr, q)
268        };
269
270        let mut x = Self::pow(a, (q + integer_one) >> 1);
271        let mut t = Self::pow(a, q);
272        let mut m = s;
273
274        let one = Self::one();
275        while !Self::eq(&t, &one) {
276            let i = {
277                let mut i = 0;
278                let mut t = t.clone();
279                let minus_one = Self::neg(&Self::one());
280                while !Self::eq(&t, &minus_one) {
281                    i += 1;
282                    t = Self::mul(&t, &t);
283                }
284                i + 1
285            };
286
287            let b = (0..(m - i - 1)).fold(c, |acc, _| Self::square(&acc));
288
289            c = Self::mul(&b, &b);
290            x = Self::mul(&x, &b);
291            t = Self::mul(&t, &c);
292            m = i;
293        }
294
295        let neg_x = Self::neg(&x);
296        Some((x, neg_x))
297    }
298}
299
300/// This trait is necessary for sampling a random field element with a uniform distribution.
301pub trait HasDefaultTranscript: IsField {
302    /// This function should truncates the sampled bits to the quantity required to represent the order of the base field
303    /// and returns a field element.
304    fn get_random_field_element_from_rng(rng: &mut impl rand::Rng) -> FieldElement<Self>;
305}
lambdaworks_math/field/traits.rs

lambdaworks_math/field/
traits.rs
