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

o1_utils/
foreign_field.rs
