ark_ff/fields/models/small_fp/
small_fp_backend.rs

1use crate::{AdditiveGroup, BigInt, FftField, One, PrimeField, SqrtPrecomputation, Zero};
2use ark_std::{
3    cmp::*,
4    fmt::{Display, Formatter, Result as FmtResult},
5    hash::Hash,
6    marker::PhantomData,
7    str::FromStr,
8};
9use educe::Educe;
10use num_traits::Unsigned;
11
12pub use ark_ff_macros::SmallFpConfig;
13
14/// A trait that specifies the configuration of a prime field, including the
15/// modulus, generator, and arithmetic implementation.
16///
17/// This trait is intended to be implemented through the derive
18/// macro, which allows specifying different backends for field arithmetic,
19/// such as "standard" or "montgomery".
20pub trait SmallFpConfig: Send + Sync + 'static + Sized {
21    type T: Copy
22        + Default
23        + PartialEq
24        + Eq
25        + Hash
26        + Sync
27        + Send
28        + PartialOrd
29        + Display
30        + Unsigned
31        + core::fmt::Debug
32        + core::ops::Add<Output = Self::T>
33        + core::ops::Sub<Output = Self::T>
34        + core::ops::Mul<Output = Self::T>
35        + core::ops::Div<Output = Self::T>
36        + core::ops::Rem<Output = Self::T>
37        + Into<u128>
38        + TryFrom<u128>;
39
40    /// The modulus of the field.
41    const MODULUS: Self::T;
42    const MODULUS_U128: u128;
43
44    // TODO: the value can be 1 or 2, it would be nice to have it generic.
45    /// Number of bigint limbs used to represent the field elements.
46    const NUM_BIG_INT_LIMBS: usize = 1;
47
48    /// A multiplicative generator of the field.
49    /// `Self::GENERATOR` is an element having multiplicative order
50    /// `Self::MODULUS - 1`.
51    const GENERATOR: SmallFp<Self>;
52
53    /// Additive identity of the field, i.e. the element `e`
54    /// such that, for all elements `f` of the field, `e + f = f`.
55    const ZERO: SmallFp<Self>;
56
57    /// Multiplicative identity of the field, i.e. the element `e`
58    /// such that, for all elements `f` of the field, `e * f = f`.
59    const ONE: SmallFp<Self>;
60
61    /// Negation of the multiplicative identity of the field.
62    const NEG_ONE: SmallFp<Self>;
63
64    /// Let `N` be the size of the multiplicative group defined by the field.
65    /// Then `TWO_ADICITY` is the two-adicity of `N`, i.e. the integer `s`
66    /// such that `N = 2^s * t` for some odd integer `t`.
67    const TWO_ADICITY: u32;
68
69    /// 2^s root of unity computed by GENERATOR^t
70    const TWO_ADIC_ROOT_OF_UNITY: SmallFp<Self>;
71
72    /// An integer `b` such that there exists a multiplicative subgroup
73    /// of size `b^k` for some integer `k`.
74    const SMALL_SUBGROUP_BASE: Option<u32> = None;
75
76    /// The integer `k` such that there exists a multiplicative subgroup
77    /// of size `Self::SMALL_SUBGROUP_BASE^k`.
78    const SMALL_SUBGROUP_BASE_ADICITY: Option<u32> = None;
79
80    /// GENERATOR^((MODULUS-1) / (2^s *
81    /// SMALL_SUBGROUP_BASE^SMALL_SUBGROUP_BASE_ADICITY)) Used for mixed-radix
82    /// FFT.
83    const LARGE_SUBGROUP_ROOT_OF_UNITY: Option<SmallFp<Self>> = None;
84
85    /// Precomputed material for use when computing square roots.
86    /// Currently uses the generic Tonelli-Shanks,
87    /// which works for every modulus.
88    const SQRT_PRECOMP: Option<SqrtPrecomputation<SmallFp<Self>>>;
89
90    /// Set a += b.
91    fn add_assign(a: &mut SmallFp<Self>, b: &SmallFp<Self>);
92
93    /// Set a -= b.
94    fn sub_assign(a: &mut SmallFp<Self>, b: &SmallFp<Self>);
95
96    /// Set a = a + a.
97    fn double_in_place(a: &mut SmallFp<Self>);
98
99    /// Set a = -a;
100    fn neg_in_place(a: &mut SmallFp<Self>);
101
102    /// Set a *= b.
103    fn mul_assign(a: &mut SmallFp<Self>, b: &SmallFp<Self>);
104
105    /// Compute the inner product `<a, b>`.
106    fn sum_of_products<const T: usize>(
107        a: &[SmallFp<Self>; T],
108        b: &[SmallFp<Self>; T],
109    ) -> SmallFp<Self>;
110
111    /// Set a *= a.
112    fn square_in_place(a: &mut SmallFp<Self>);
113
114    /// Compute a^{-1} if `a` is not zero.
115    fn inverse(a: &SmallFp<Self>) -> Option<SmallFp<Self>>;
116
117    /// Construct a field element from a standard integer value
118    fn new(value: Self::T) -> SmallFp<Self>;
119
120    /// Construct a field element from an integer in the range
121    /// `0..(Self::MODULUS - 1)`. Returns `None` if the integer is outside
122    /// this range.
123    fn from_bigint(other: BigInt<1>) -> Option<SmallFp<Self>>;
124
125    /// Convert a field element to an integer in the range `0..(Self::MODULUS -
126    /// 1)`.
127    fn into_bigint(other: SmallFp<Self>) -> BigInt<1>;
128}
129
130/// Represents an element of the prime field F_p, where `p == P::MODULUS`.
131///
132/// This type can represent elements in any field of size up to 128 bits.
133/// The arithmetic implementation is determined by the `P: SmallFpConfig`
134/// parameter, which can be configured to use different backends
135#[derive(Educe)]
136#[educe(Default, Hash, Clone, Copy, PartialEq, Eq)]
137pub struct SmallFp<P: SmallFpConfig> {
138    pub value: P::T,
139    _phantom: PhantomData<P>,
140}
141
142impl<P: SmallFpConfig> SmallFp<P> {
143    #[doc(hidden)]
144    #[inline]
145    pub fn is_geq_modulus(&self) -> bool {
146        self.value >= P::MODULUS
147    }
148
149    // Does NOT perform Montgomery conversion or modular reduction
150    pub const fn from_raw(value: P::T) -> Self {
151        Self {
152            value,
153            _phantom: PhantomData,
154        }
155    }
156
157    // Creates a new field element in Montgomery form
158    #[inline]
159    pub fn new(value: P::T) -> Self {
160        P::new(value)
161    }
162
163    pub const fn num_bits_to_shave() -> usize {
164        primitive_type_bit_size(P::MODULUS_U128) - (Self::MODULUS_BIT_SIZE as usize)
165    }
166}
167
168impl<P: SmallFpConfig> ark_std::fmt::Debug for SmallFp<P> {
169    fn fmt(&self, f: &mut Formatter<'_>) -> ark_std::fmt::Result {
170        ark_std::fmt::Debug::fmt(&self.into_bigint(), f)
171    }
172}
173
174impl<P: SmallFpConfig> Zero for SmallFp<P> {
175    #[inline]
176    fn zero() -> Self {
177        P::ZERO
178    }
179
180    #[inline]
181    fn is_zero(&self) -> bool {
182        *self == P::ZERO
183    }
184}
185
186impl<P: SmallFpConfig> One for SmallFp<P> {
187    #[inline]
188    fn one() -> Self {
189        P::ONE
190    }
191
192    #[inline]
193    fn is_one(&self) -> bool {
194        *self == P::ONE
195    }
196}
197
198impl<P: SmallFpConfig> AdditiveGroup for SmallFp<P> {
199    type Scalar = Self;
200    const ZERO: Self = P::ZERO;
201
202    #[inline]
203    fn double(&self) -> Self {
204        let mut temp = *self;
205        AdditiveGroup::double_in_place(&mut temp);
206        temp
207    }
208
209    #[inline]
210    fn double_in_place(&mut self) -> &mut Self {
211        P::double_in_place(self);
212        self
213    }
214
215    #[inline]
216    fn neg_in_place(&mut self) -> &mut Self {
217        P::neg_in_place(self);
218        self
219    }
220}
221
222const fn const_to_bigint(value: u128) -> BigInt<1> {
223    BigInt::<1>::new([value as u64])
224}
225
226const fn const_num_bits_u128(value: u128) -> u32 {
227    if value == 0 {
228        0
229    } else {
230        128 - value.leading_zeros()
231    }
232}
233
234const fn primitive_type_bit_size(modulus_u128: u128) -> usize {
235    match modulus_u128 {
236        x if x <= u8::MAX as u128 => 8,
237        x if x <= u16::MAX as u128 => 16,
238        x if x <= u32::MAX as u128 => 32,
239        _ => 64,
240    }
241}
242
243impl<P: SmallFpConfig> PrimeField for SmallFp<P> {
244    type BigInt = BigInt<1>;
245
246    const MODULUS: Self::BigInt = const_to_bigint(P::MODULUS_U128);
247    const MODULUS_MINUS_ONE_DIV_TWO: Self::BigInt = Self::MODULUS.divide_by_2_round_down();
248    const MODULUS_BIT_SIZE: u32 = const_num_bits_u128(P::MODULUS_U128);
249    const TRACE: Self::BigInt = Self::MODULUS.two_adic_coefficient();
250    const TRACE_MINUS_ONE_DIV_TWO: Self::BigInt = Self::TRACE.divide_by_2_round_down();
251
252    #[inline]
253    fn from_bigint(r: BigInt<1>) -> Option<Self> {
254        P::from_bigint(r)
255    }
256
257    fn into_bigint(self) -> BigInt<1> {
258        P::into_bigint(self)
259    }
260}
261
262impl<P: SmallFpConfig> FftField for SmallFp<P> {
263    const GENERATOR: Self = P::GENERATOR;
264    const TWO_ADICITY: u32 = P::TWO_ADICITY;
265    const TWO_ADIC_ROOT_OF_UNITY: Self = P::TWO_ADIC_ROOT_OF_UNITY;
266    const SMALL_SUBGROUP_BASE: Option<u32> = P::SMALL_SUBGROUP_BASE;
267    const SMALL_SUBGROUP_BASE_ADICITY: Option<u32> = P::SMALL_SUBGROUP_BASE_ADICITY;
268    const LARGE_SUBGROUP_ROOT_OF_UNITY: Option<Self> = P::LARGE_SUBGROUP_ROOT_OF_UNITY;
269}
270
271/// Note that this implementation of `Ord` compares field elements viewing
272/// them as integers in the range 0, 1, ..., P::MODULUS - 1. However, other
273/// implementations of `PrimeField` might choose a different ordering, and
274/// as such, users should use this `Ord` for applications where
275/// any ordering suffices (like in a BTreeMap), and not in applications
276/// where a particular ordering is required.
277impl<P: SmallFpConfig> Ord for SmallFp<P> {
278    #[inline(always)]
279    fn cmp(&self, other: &Self) -> Ordering {
280        self.into_bigint().cmp(&other.into_bigint())
281    }
282}
283
284/// Note that this implementation of `PartialOrd` compares field elements
285/// viewing them as integers in the range 0, 1, ..., `P::MODULUS` - 1. However,
286/// other implementations of `PrimeField` might choose a different ordering, and
287/// as such, users should use this `PartialOrd` for applications where
288/// any ordering suffices (like in a BTreeMap), and not in applications
289/// where a particular ordering is required.
290impl<P: SmallFpConfig> PartialOrd for SmallFp<P> {
291    #[inline(always)]
292    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
293        Some(self.cmp(other))
294    }
295}
296
297impl<P: SmallFpConfig> ark_std::rand::distributions::Distribution<SmallFp<P>>
298    for ark_std::rand::distributions::Standard
299{
300    #[inline]
301    fn sample<R: ark_std::rand::Rng + ?Sized>(&self, rng: &mut R) -> SmallFp<P> {
302        macro_rules! sample_loop {
303            ($ty:ty) => {
304                loop {
305                    let mut val: $ty = rng.sample(ark_std::rand::distributions::Standard);
306                    let shave_bits = SmallFp::<P>::num_bits_to_shave();
307                    let mask = <$ty>::MAX >> shave_bits;
308                    val &= mask;
309                    if val > 0 && u128::from(val) < P::MODULUS_U128 {
310                        return SmallFp::from(val);
311                    }
312                }
313            };
314        }
315
316        match P::MODULUS_U128 {
317            modulus if modulus <= u8::MAX as u128 => sample_loop!(u8),
318            modulus if modulus <= u16::MAX as u128 => sample_loop!(u16),
319            modulus if modulus <= u32::MAX as u128 => sample_loop!(u32),
320            _ => sample_loop!(u64),
321        }
322    }
323}
324
325#[derive(Debug)]
326pub enum ParseSmallFpError {
327    Empty,
328    InvalidFormat,
329    InvalidLeadingZero,
330}
331
332impl<P: SmallFpConfig> FromStr for SmallFp<P> {
333    type Err = ParseSmallFpError;
334
335    /// Interpret a string of numbers as a (congruent) prime field element.
336    /// Does not accept unnecessary leading zeroes or a blank string.
337    fn from_str(s: &str) -> Result<Self, Self::Err> {
338        if s.is_empty() {
339            return Err(ParseSmallFpError::Empty);
340        }
341        if s.starts_with('0') && s.len() > 1 {
342            return Err(ParseSmallFpError::InvalidLeadingZero);
343        }
344
345        match s.parse::<u128>() {
346            Ok(val) => Ok(SmallFp::from(val)),
347            Err(_) => Err(ParseSmallFpError::InvalidFormat),
348        }
349    }
350}
351
352/// Outputs a string containing the value of `self`,
353/// represented as a decimal without leading zeroes.
354impl<P: SmallFpConfig> Display for SmallFp<P> {
355    #[inline]
356    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
357        // Always use BigInt conversion to display the true mathematical value
358        let bigint = P::into_bigint(*self);
359        write!(f, "{}", bigint)
360    }
361}
ark_ff/fields/models/small_fp/small_fp_backend.rs

ark_ff/fields/models/small_fp/
small_fp_backend.rs
