snarkvm_fields/
lib.rs

1// Copyright 2024 Aleo Network Foundation
2// This file is part of the snarkVM library.
3
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at:
7
8// http://www.apache.org/licenses/LICENSE-2.0
9
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15
16#![allow(clippy::module_inception)]
17#![forbid(unsafe_code)]
18
19#[macro_use]
20extern crate thiserror;
21
22#[macro_use]
23mod macros;
24
25pub mod errors;
26pub use errors::*;
27
28mod fp_256;
29pub use fp_256::*;
30
31mod fp_384;
32pub use fp_384::*;
33
34mod fp2;
35pub use fp2::*;
36
37pub mod fp6_3over2;
38
39mod fp12_2over3over2;
40pub use fp12_2over3over2::*;
41
42mod legendre;
43pub use legendre::*;
44
45mod to_field_vec;
46#[allow(unused_imports)]
47pub use to_field_vec::*;
48
49pub mod traits;
50pub use traits::*;
51
52use snarkvm_utilities::{
53    FromBytes,
54    ToBytes,
55    biginteger::*,
56    serialize::{CanonicalDeserialize, CanonicalDeserializeWithFlags, CanonicalSerialize, CanonicalSerializeWithFlags},
57};
58
59impl_field_to_biginteger!(Fp256, BigInteger256, Fp256Parameters);
60impl_field_to_biginteger!(Fp384, BigInteger384, Fp384Parameters);
61
62impl_primefield_serializer!(Fp256, Fp256Parameters, 32);
63impl_primefield_serializer!(Fp384, Fp384Parameters, 48);
64
65// Given a vector of field elements {v_i}, compute the vector {v_i^(-1)}
66pub fn batch_inversion<F: Field>(v: &mut [F]) {
67    batch_inversion_and_mul(v, &F::one());
68}
69
70#[cfg(feature = "serial")]
71// Given a vector of field elements {v_i}, compute the vector {coeff * v_i^(-1)}
72pub fn batch_inversion_and_mul<F: Field>(v: &mut [F], coeff: &F) {
73    serial_batch_inversion_and_mul(v, coeff);
74}
75
76#[cfg(not(feature = "serial"))]
77// Given a vector of field elements {v_i}, compute the vector {coeff * v_i^(-1)}
78pub fn batch_inversion_and_mul<F: Field>(v: &mut [F], coeff: &F) {
79    use rayon::prelude::*;
80    // Divide the vector v evenly between all available cores
81    let min_elements_per_thread = 1;
82    let num_cpus_available = snarkvm_utilities::parallel::max_available_threads();
83    let num_elems = v.len();
84    let num_elem_per_thread = min_elements_per_thread.max(num_elems / num_cpus_available);
85
86    // Batch invert in parallel, without copying the vector
87    v.par_chunks_mut(num_elem_per_thread).for_each(|chunk| {
88        serial_batch_inversion_and_mul(chunk, coeff);
89    });
90}
91
92/// Given a vector of field elements {v_i}, compute the vector {coeff * v_i^(-1)}.
93/// This method is explicitly single-threaded.
94fn serial_batch_inversion_and_mul<F: Field>(v: &mut [F], coeff: &F) {
95    // Montgomery’s Trick and Fast Implementation of Masked AES
96    // Genelle, Prouff and Quisquater
97    // Section 3.2
98    // but with an optimization to multiply every element in the returned vector by
99    // coeff
100
101    // First pass: compute [a, ab, abc, ...]
102    let mut prod = Vec::with_capacity(v.len());
103    let mut tmp = F::one();
104    for f in v.iter().filter(|f| !f.is_zero()) {
105        tmp.mul_assign(f);
106        prod.push(tmp);
107    }
108
109    // Invert `tmp`.
110    tmp = tmp.inverse().unwrap(); // Guaranteed to be nonzero.
111
112    // Multiply product by coeff, so all inverses will be scaled by coeff
113    tmp *= coeff;
114
115    // Second pass: iterate backwards to compute inverses
116    for (f, s) in v.iter_mut()
117        // Backwards
118        .rev()
119        // Ignore normalized elements
120        .filter(|f| !f.is_zero())
121        // Backwards, skip last element, fill in one for last term.
122        .zip(prod.into_iter().rev().skip(1).chain(Some(F::one())))
123    {
124        // tmp := tmp * f; f := tmp * s = 1/f
125        let new_tmp = tmp * *f;
126        *f = tmp * s;
127        tmp = new_tmp;
128    }
129}
snarkvm_fields/lib.rs

snarkvm_fields/
lib.rs
