26 #ifndef CRYPTO3_MATH_ARITHMETIC_SEQUENCE_DOMAIN_HPP
27 #define CRYPTO3_MATH_ARITHMETIC_SEQUENCE_DOMAIN_HPP
45 template<
typename FieldType>
46 class evaluation_domain;
48 template<
typename FieldType>
50 typedef typename FieldType::value_type value_type;
61 compute_subproduct_tree<FieldType>(this->subproduct_tree, log2(this->m));
65 arithmetic_sequence = std::vector<value_type>(this->m);
66 for (std::size_t i = 0; i < this->m; i++) {
67 arithmetic_sequence[i] = arithmetic_generator * value_type(i);
70 precomputation_sentinel =
true;
75 throw std::invalid_argument(
"arithmetic(): expected m > 1");
79 throw std::invalid_argument(
80 "arithmetic(): expected arithmetic_params<FieldType>::arithmetic_generator.is_zero() "
84 precomputation_sentinel =
false;
87 void fft(std::vector<value_type> &a) {
88 if (a.size() != this->m) {
89 if (a.size() < this->m) {
90 a.resize(this->m, value_type(0));
92 throw std::invalid_argument(
"arithmetic: expected a.size() == this->m");
96 if (!this->precomputation_sentinel) {
101 monomial_to_newton_basis<FieldType>(a, subproduct_tree, this->m);
104 std::vector<value_type> S(this->m);
105 S[0] = value_type::one();
107 value_type factorial = value_type::one();
108 for (std::size_t i = 1; i < this->m; i++) {
109 factorial *= value_type(i);
110 S[i] = (factorial * arithmetic_generator).inversed();
117 #pragma omp parallel for
119 for (std::size_t i = 0; i < this->m; i++) {
120 a[i] *= S[i].inversed();
125 if (a.size() != this->m) {
126 if (a.size() < this->m) {
127 a.resize(this->m, value_type(0));
129 throw std::invalid_argument(
"arithmetic: expected a.size() == this->m");
133 if (!this->precomputation_sentinel)
137 std::vector<value_type> S(this->m);
138 S[0] = value_type::one();
140 std::vector<value_type> W(this->m);
143 value_type factorial = value_type::one();
144 for (std::size_t i = 1; i < this->m; i++) {
145 factorial *= value_type(i);
146 S[i] = (factorial * arithmetic_generator).inversed();
156 newton_to_monomial_basis<FieldType>(a, subproduct_tree, this->m);
164 if (!precomputation_sentinel)
171 for (std::size_t i = 0; i < this->m; ++i) {
172 if (arithmetic_sequence[i] == t)
174 std::vector<value_type> res(this->m, value_type::zero());
175 res[i] = value_type::one();
184 std::vector<value_type> l(this->m);
185 l[0] = t - this->arithmetic_sequence[0];
187 value_type l_vanish = l[0];
188 value_type g_vanish = value_type::one();
190 for (std::size_t i = 1; i < this->m; i++) {
191 l[i] = t - this->arithmetic_sequence[i];
193 g_vanish *= -this->arithmetic_sequence[i];
196 std::vector<value_type> w(this->m);
197 w[0] = g_vanish.inversed() * (this->arithmetic_generator.pow(this->m - 1));
199 l[0] = l_vanish * l[0].inversed() * w[0];
200 for (std::size_t i = 1; i < this->m; i++) {
201 value_type num = this->arithmetic_sequence[i - 1] - this->arithmetic_sequence[this->m - 1];
202 w[i] = w[i - 1] * num * this->arithmetic_sequence[i].inversed();
203 l[i] = l_vanish * l[i].inversed() * w[i];
209 if (!this->precomputation_sentinel)
212 return this->arithmetic_sequence[idx];
215 if (!this->precomputation_sentinel)
219 value_type Z = value_type::one();
220 for (std::size_t i = 0; i < this->m; i++) {
221 Z *= (t - this->arithmetic_sequence[i]);
225 void add_poly_z(
const value_type &coeff, std::vector<value_type> &H) {
226 if (H.size() != this->m + 1)
227 throw std::invalid_argument(
"arithmetic: expected H.size() == this->m+1");
229 if (!this->precomputation_sentinel)
232 std::vector<value_type> x(2, value_type::zero());
233 x[0] = -this->arithmetic_sequence[0];
234 x[1] = value_type::one();
236 std::vector<value_type> t(2, value_type::zero());
238 for (std::size_t i = 1; i < this->m + 1; i++) {
239 t[0] = -this->arithmetic_sequence[i];
240 t[1] = value_type::one();
246 #pragma omp parallel for
248 for (std::size_t i = 0; i < this->m + 1; i++) {
249 H[i] += (x[i] * coeff);
253 const value_type coset = this->arithmetic_generator;
254 const value_type Z_inverse_at_coset = this->compute_vanishing_polynomial(coset).inversed();
255 for (std::size_t i = 0; i < this->m; ++i) {
256 P[i] *= Z_inverse_at_coset;
Definition: arithmetic_sequence_domain.hpp:49
void do_precomputation()
Definition: arithmetic_sequence_domain.hpp:60
std::vector< value_type > evaluate_all_lagrange_polynomials(const value_type &t)
Definition: arithmetic_sequence_domain.hpp:159
std::vector< std::vector< std::vector< value_type > > > subproduct_tree
Definition: arithmetic_sequence_domain.hpp:56
FieldType field_type
Definition: arithmetic_sequence_domain.hpp:53
std::vector< value_type > arithmetic_sequence
Definition: arithmetic_sequence_domain.hpp:57
value_type get_domain_element(const std::size_t idx)
Definition: arithmetic_sequence_domain.hpp:208
bool precomputation_sentinel
Definition: arithmetic_sequence_domain.hpp:55
void add_poly_z(const value_type &coeff, std::vector< value_type > &H)
Definition: arithmetic_sequence_domain.hpp:225
value_type arithmetic_generator
Definition: arithmetic_sequence_domain.hpp:58
void inverse_fft(std::vector< value_type > &a)
Definition: arithmetic_sequence_domain.hpp:124
void divide_by_z_on_coset(std::vector< value_type > &P)
Definition: arithmetic_sequence_domain.hpp:252
arithmetic_sequence_domain(const std::size_t m)
Definition: arithmetic_sequence_domain.hpp:73
value_type compute_vanishing_polynomial(const value_type &t)
Definition: arithmetic_sequence_domain.hpp:214
void fft(std::vector< value_type > &a)
Definition: arithmetic_sequence_domain.hpp:87
Definition: evaluation_domain.hpp:41
void multiplication(Range &c, const Range &a, const Range &b)
Definition: basic_operations.hpp:192
bool is_zero(const Range &a)
Definition: basic_operations.hpp:43
Definition: fields/params.hpp:58