o1_utils/
foreign_field.rs

1//! Describes helpers for foreign field arithmetics
2//! Generic parameters are as follows:
3//! - `B` is a bit length of one limb
4//! - `N` is a number of limbs that is used to represent one foreign field element
5
6use crate::field_helpers::FieldHelpers;
7use ark_ff::{Field, PrimeField};
8use num_bigint::BigUint;
9use std::{
10    fmt::{Debug, Formatter},
11    ops::{Index, IndexMut},
12};
13
14/// Represents a foreign field element
15#[derive(Clone, PartialEq, Eq)]
16/// Represents a foreign field element
17pub struct ForeignElement<F: Field, const B: usize, const N: usize> {
18    /// limbs in little endian order
19    pub limbs: [F; N],
20    /// number of limbs used for the foreign field element
21    len: usize,
22}
23
24impl<F: Field, const B: usize, const N: usize> ForeignElement<F, B, N> {
25    /// Creates a new foreign element from an array containing N limbs
26    pub const fn new(limbs: [F; N]) -> Self {
27        Self { limbs, len: N }
28    }
29
30    /// Creates a new foreign element representing the value zero
31    #[must_use]
32    pub fn zero() -> Self {
33        Self {
34            limbs: [F::zero(); N],
35            len: N,
36        }
37    }
38
39    /// Initializes a new foreign element from a [`BigUint`]
40    ///
41    /// # Panics
42    ///
43    /// Panics if the `BigUint` is too large to fit in the `N` limbs.
44    #[must_use]
45    pub fn from_biguint(big: &BigUint) -> Self {
46        let vec = Self::big_to_vec(big);
47
48        // create an array of N native elements containing the limbs
49        // until the array is full in big endian, so most significant
50        // limbs may be zero if the big number is smaller
51        assert!(vec.len() <= N, "BigUint element is too large for N limbs");
52
53        let mut limbs = [F::zero(); N];
54        for (i, term) in vec.iter().enumerate() {
55            limbs[i] = *term;
56        }
57
58        Self {
59            limbs,
60            len: limbs.len(),
61        }
62    }
63
64    /// Initializes a new foreign element from an absolute `BigUint` but the equivalent
65    /// foreign element obtained corresponds to the negated input. It first converts the
66    /// input big element to a big integer modulo the foreign field modulus, and then
67    /// computes the negation of the result.
68    #[must_use]
69    pub fn neg(&self, modulus: &BigUint) -> Self {
70        let big = self.to_biguint();
71        let ok = big % modulus;
72        let neg = modulus - ok;
73        Self::from_biguint(&neg)
74    }
75
76    /// Initializes a new foreign element from a set of bytes in big endian
77    #[must_use]
78    pub fn from_be(bytes: &[u8]) -> Self {
79        Self::from_biguint(&BigUint::from_bytes_be(bytes))
80    }
81
82    /// Obtains the big integer representation of the foreign field element
83    #[must_use]
84    pub fn to_biguint(&self) -> BigUint {
85        let mut bytes = vec![];
86        if B.is_multiple_of(8) {
87            // limbs are stored in little endian
88            for limb in self.limbs {
89                let crumb = &limb.to_bytes()[0..B / 8];
90                bytes.extend_from_slice(crumb);
91            }
92        } else {
93            let mut bits: Vec<bool> = vec![];
94            for limb in self.limbs {
95                // Only take lower B bits, as there might be more (zeroes) in the high ones.
96                bits.extend(limb.to_bits().into_iter().take(B));
97            }
98
99            let bytes_len = (B * N).div_ceil(8);
100            bytes = vec![0u8; bytes_len];
101            for (i, &bit) in bits.iter().enumerate() {
102                bytes[i / 8] |= u8::from(bit) << (i % 8);
103            }
104        }
105        BigUint::from_bytes_le(&bytes)
106    }
107
108    /// Split a foreign field element into a vector of `B` (limb bitsize) bits field
109    /// elements of type `F` in little-endian. Right now it is written
110    /// so that it gives `N` (limb count) limbs, even if it fits in less bits.
111    fn big_to_vec(fe: &BigUint) -> Vec<F> {
112        if B.is_multiple_of(8) {
113            let bytes = fe.to_bytes_le();
114            bytes
115                .chunks(B / 8)
116                .map(|chunk| F::from_random_bytes(chunk).expect("failed to deserialize"))
117                .collect()
118        } else {
119            // Quite inefficient
120            let mut bits = vec![]; // can be slice not vec, but B*N is not const?
121            assert!(
122                fe.bits() <= (B * N) as u64,
123                "BigUint too big to be represented in B*N elements"
124            );
125            for i in 0..B * N {
126                bits.push(fe.bit(i as u64));
127            }
128            bits.chunks(B)
129                .map(|chunk| F::from_bits(chunk).expect("failed to deserialize"))
130                .collect()
131        }
132    }
133}
134
135impl<F: PrimeField, const B: usize, const N: usize> ForeignElement<F, B, N> {
136    /// Initializes a new foreign element from an element in the native field
137    pub fn from_field(field: F) -> Self {
138        Self::from_biguint(&field.into())
139    }
140}
141
142impl<F: Field, const B: usize, const N: usize> Index<usize> for ForeignElement<F, B, N> {
143    type Output = F;
144    fn index(&self, idx: usize) -> &Self::Output {
145        &self.limbs[idx]
146    }
147}
148
149impl<F: Field, const B: usize, const N: usize> IndexMut<usize> for ForeignElement<F, B, N> {
150    fn index_mut(&mut self, idx: usize) -> &mut Self::Output {
151        &mut self.limbs[idx]
152    }
153}
154
155impl<F: Field, const B: usize, const N: usize> Debug for ForeignElement<F, B, N> {
156    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
157        write!(f, "ForeignElement(")?;
158        for i in 0..self.len {
159            write!(f, "{:?}", self.limbs[i].to_hex())?;
160            if i != self.len - 1 {
161                write!(f, ", ")?;
162            }
163        }
164        write!(f, ")")
165    }
166}
167
168/// Foreign field helpers for `B` the limb size.
169pub trait ForeignFieldHelpers<F, const B: usize> {
170    /// 2^{B}
171    fn two_to_limb() -> F;
172
173    /// 2^{2 * B}
174    fn two_to_2limb() -> F;
175
176    /// 2^{3 * B}
177    fn two_to_3limb() -> F;
178}
179
180impl<F: Field, const B: usize, const N: usize> ForeignFieldHelpers<F, B>
181    for ForeignElement<F, B, N>
182{
183    fn two_to_limb() -> F {
184        F::from(2u64).pow([B as u64])
185    }
186
187    fn two_to_2limb() -> F {
188        F::from(2u64).pow([2 * B as u64])
189    }
190
191    fn two_to_3limb() -> F {
192        // Self?
193        F::from(2u64).pow([3 * B as u64])
194    }
195}
o1_utils/foreign_field.rs

o1_utils/
foreign_field.rs
