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

o1_utils/
foreign_field.rs
