26 #ifndef CRYPTO3_MATH_BASIC_RADIX2_DOMAIN_HPP
27 #define CRYPTO3_MATH_BASIC_RADIX2_DOMAIN_HPP
43 template<
typename FieldType>
44 class evaluation_domain;
46 template<
typename FieldType>
48 typedef typename FieldType::value_type value_type;
57 throw std::invalid_argument(
"basic_radix2(): expected m > 1");
59 if (!std::is_same<value_type, std::complex<double>>::value) {
60 const std::size_t logm =
static_cast<std::size_t
>(std::ceil(std::log2(m)));
62 throw std::invalid_argument(
63 "basic_radix2(): expected logm <= fields::arithmetic_params<FieldType>::s");
66 omega = unity_root<FieldType>(m);
69 void fft(std::vector<value_type> &a) {
70 if (a.size() != this->m) {
71 if (a.size() < this->m) {
72 a.resize(this->m, value_type(0));
74 throw std::invalid_argument(
"basic_radix2: expected a.size() == this->m");
78 _basic_radix2_fft<FieldType>(a, omega);
82 if (a.size() != this->m) {
83 if (a.size() < this->m) {
84 a.resize(this->m, value_type(0));
86 throw std::invalid_argument(
"basic_radix2: expected a.size() == this->m");
90 _basic_radix2_fft<FieldType>(a, omega.inversed());
92 const value_type sconst = value_type(a.size()).inversed();
93 for (std::size_t i = 0; i < a.size(); ++i) {
99 return detail::basic_radix2_evaluate_all_lagrange_polynomials<FieldType>(this->m, t);
103 return omega.pow(idx);
107 return (t.pow(this->m)) - value_type::one();
110 void add_poly_z(
const value_type &coeff, std::vector<value_type> &H) {
111 if (H.size() != this->m + 1)
112 throw std::invalid_argument(
"basic_radix2: expected H.size() == this->m+1");
120 const value_type Z_inverse_at_coset = this->compute_vanishing_polynomial(coset).inversed();
121 for (std::size_t i = 0; i < this->m; ++i) {
122 P[i] *= Z_inverse_at_coset;
Definition: basic_radix2_domain.hpp:47
std::vector< value_type > evaluate_all_lagrange_polynomials(const value_type &t)
Definition: basic_radix2_domain.hpp:98
basic_radix2_domain(const std::size_t m)
Definition: basic_radix2_domain.hpp:55
value_type omega
Definition: basic_radix2_domain.hpp:53
void add_poly_z(const value_type &coeff, std::vector< value_type > &H)
Definition: basic_radix2_domain.hpp:110
value_type get_domain_element(const std::size_t idx)
Definition: basic_radix2_domain.hpp:102
value_type compute_vanishing_polynomial(const value_type &t)
Definition: basic_radix2_domain.hpp:106
void divide_by_z_on_coset(std::vector< value_type > &P)
Definition: basic_radix2_domain.hpp:118
FieldType field_type
Definition: basic_radix2_domain.hpp:51
void inverse_fft(std::vector< value_type > &a)
Definition: basic_radix2_domain.hpp:81
void fft(std::vector< value_type > &a)
Definition: basic_radix2_domain.hpp:69
Definition: evaluation_domain.hpp:41
Definition: fields/params.hpp:58