1 /** @file 2 ***************************************************************************** 3 * @author This file is part of libff, developed by SCIPR Lab 4 * and contributors (see AUTHORS). 5 * @copyright MIT license (see LICENSE file) 6 *****************************************************************************/ 7 8 #ifndef BN_UTILS_TCC_ 9 #define BN_UTILS_TCC_ 10 11 namespace libff { 12 13 template<typename FieldT> bn_batch_invert(std::vector<FieldT> & vec)14void bn_batch_invert(std::vector<FieldT> &vec) 15 { 16 std::vector<FieldT> prod; 17 prod.reserve(vec.size()); 18 19 FieldT acc = 1; 20 21 for (auto el : vec) 22 { 23 assert(!el.isZero()); 24 prod.emplace_back(acc); 25 FieldT::mul(acc, acc, el); 26 } 27 28 FieldT acc_inverse = acc; 29 acc_inverse.inverse(); 30 31 for (long i = vec.size()-1; i >= 0; --i) 32 { 33 const FieldT old_el = vec[i]; 34 FieldT::mul(vec[i], acc_inverse, prod[i]); 35 FieldT::mul(acc_inverse, acc_inverse, old_el); 36 } 37 } 38 39 } // libff 40 #endif // FIELD_UTILS_TCC_ 41