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 % 8 == 0 {
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 = if (B * N) % 8 == 0 {
95                (B * N) / 8
96            } else {
97                ((B * N) / 8) + 1
98            };
99            bytes = vec![0u8; bytes_len];
100            for i in 0..bits.len() {
101                bytes[i / 8] |= u8::from(bits[i]) << (i % 8);
102            }
103        }
104        BigUint::from_bytes_le(&bytes)
105    }
106
107    /// Split a foreign field element into a vector of `B` (limb bitsize) bits field
108    /// elements of type `F` in little-endian. Right now it is written
109    /// so that it gives `N` (limb count) limbs, even if it fits in less bits.
110    fn big_to_vec(fe: BigUint) -> Vec<F> {
111        if B % 8 == 0 {
112            let bytes = fe.to_bytes_le();
113            let chunks: Vec<&[u8]> = bytes.chunks(B / 8).collect();
114            chunks
115                .iter()
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            let chunks: Vec<_> = bits.chunks(B).collect();
129            chunks
130                .into_iter()
131                .map(|chunk| F::from_bits(chunk).expect("failed to deserialize"))
132                .collect()
133        }
134    }
135}
136
137impl<F: PrimeField, const B: usize, const N: usize> ForeignElement<F, B, N> {
138    /// Initializes a new foreign element from an element in the native field
139    pub fn from_field(field: F) -> Self {
140        Self::from_biguint(field.into())
141    }
142}
143
144impl<F: Field, const B: usize, const N: usize> Index<usize> for ForeignElement<F, B, N> {
145    type Output = F;
146    fn index(&self, idx: usize) -> &Self::Output {
147        &self.limbs[idx]
148    }
149}
150
151impl<F: Field, const B: usize, const N: usize> IndexMut<usize> for ForeignElement<F, B, N> {
152    fn index_mut(&mut self, idx: usize) -> &mut Self::Output {
153        &mut self.limbs[idx]
154    }
155}
156
157impl<F: Field, const B: usize, const N: usize> Debug for ForeignElement<F, B, N> {
158    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
159        write!(f, "ForeignElement(")?;
160        for i in 0..self.len {
161            write!(f, "{:?}", self.limbs[i].to_hex())?;
162            if i != self.len - 1 {
163                write!(f, ", ")?;
164            }
165        }
166        write!(f, ")")
167    }
168}
169
170/// Foreign field helpers for `B` the limb size.
171pub trait ForeignFieldHelpers<F, const B: usize> {
172    /// 2^{B}
173    fn two_to_limb() -> F;
174
175    /// 2^{2 * B}
176    fn two_to_2limb() -> F;
177
178    /// 2^{3 * B}
179    fn two_to_3limb() -> F;
180}
181
182impl<F: Field, const B: usize, const N: usize> ForeignFieldHelpers<F, B>
183    for ForeignElement<F, B, N>
184{
185    fn two_to_limb() -> F {
186        F::from(2u64).pow([B as u64])
187    }
188
189    fn two_to_2limb() -> F {
190        F::from(2u64).pow([2 * B as u64])
191    }
192
193    fn two_to_3limb() -> F {
194        // Self?
195        F::from(2u64).pow([3 * B as u64])
196    }
197}
o1_utils/foreign_field.rs

o1_utils/
foreign_field.rs
