91std::vector<typename C::AffinePoint>
basemul_setup(
const typename C::AffinePoint& p,
size_t max_scalar_bits) {
92 static_assert(WindowBits >= 1 && WindowBits <= 8);
95 constexpr size_t WindowElements = (1 << WindowBits) - 1;
97 const size_t Windows = (max_scalar_bits + WindowBits - 1) / WindowBits;
99 const size_t TableSize = Windows * WindowElements;
101 std::vector<typename C::ProjectivePoint> table;
102 table.reserve(TableSize);
104 auto accum = C::ProjectivePoint::from_affine(p);
106 for(
size_t i = 0; i != TableSize; i += WindowElements) {
107 table.push_back(accum);
109 for(
size_t j = 1; j != WindowElements; ++j) {
112 table.emplace_back(table[i + j / 2].dbl());
114 table.emplace_back(table[i + j - 1] + table[i]);
118 accum = table[i + (WindowElements / 2)].dbl();
126typename C::ProjectivePoint
basemul_exec(std::span<const typename C::AffinePoint> table,
127 const BlindedScalar& scalar,
128 const Blinding& blinding) {
130 static constexpr size_t WindowElements = (1 << WindowBits) - 1;
135 const size_t w_0 = scalar.get_window(0);
136 const auto tbl_0 = table.first(WindowElements);
137 auto pt = C::ProjectivePoint::from_affine(C::AffinePoint::ct_select(tbl_0, w_0));
138 blinding.randomize_rep(pt, 0);
142 const size_t windows = (scalar.bits() + WindowBits - 1) / WindowBits;
144 for(
size_t i = 1; i != windows; ++i) {
145 const size_t w_i = scalar.get_window(WindowBits * i);
146 const auto tbl_i = table.subspan(WindowElements * i, WindowElements);
153 accum += C::AffinePoint::ct_select(tbl_i, w_i);
156 if(i < Blinding::Rerandomizations) {
157 blinding.randomize_rep(accum, i);
178std::vector<typename C::AffinePoint>
basemul_booth_setup(
const typename C::AffinePoint& p,
size_t max_scalar_bits) {
179 static_assert(WindowBits >= 1 && WindowBits <= 8);
182 constexpr size_t WindowElements = 1 << (WindowBits - 1);
184 const size_t Windows = (max_scalar_bits + WindowBits - 1) / WindowBits;
186 const size_t TableSize = Windows * WindowElements;
188 std::vector<typename C::ProjectivePoint> table;
189 table.reserve(TableSize);
191 auto accum = C::ProjectivePoint::from_affine(p);
193 for(
size_t i = 0; i != TableSize; i += WindowElements) {
194 table.push_back(accum);
196 for(
size_t j = 1; j != WindowElements; ++j) {
199 table.emplace_back(table[i + j / 2].dbl());
201 table.emplace_back(table[i + j - 1] + table[i]);
207 accum = table[i + WindowElements - 1].dbl();
216 const BlindedScalar& scalar,
217 const Blinding& blinding) {
218 static constexpr size_t WindowElements = 1 << (WindowBits - 1);
220 const size_t windows = (scalar.bits() + WindowBits) / WindowBits;
224 const size_t w_bits = scalar.get_window(0) & ((1 << WindowBits) - 1);
225 const size_t raw = w_bits << 1;
227 const auto tbl_0 = table.first(WindowElements);
229 auto pt = C::ProjectivePoint::from_affine(C::AffinePoint::ct_select(tbl_0, tidx));
230 pt.conditional_assign(tneg, pt.negate());
231 blinding.randomize_rep(pt, 0);
235 for(
size_t i = 1; i != windows; ++i) {
237 const size_t bit_pos = WindowBits * i - 1;
238 const size_t raw = scalar.get_window(bit_pos);
241 const auto tbl_i = table.subspan(WindowElements * i, WindowElements);
243 accum = C::ProjectivePoint::add_or_sub(accum, C::AffinePoint::ct_select(tbl_i, tidx), tneg);
246 if(i < Blinding::Rerandomizations) {
247 blinding.randomize_rep(accum, i);
263 const ScalarBits& scalar,
264 typename C::ProjectivePoint accum) {
265 static constexpr size_t WindowElements = 1 << (WindowBits - 1);
267 const size_t windows = (scalar.bits() + WindowBits) / WindowBits;
270 for(
size_t i = 0; i != windows; ++i) {
274 (i == 0) ? ((scalar.get_window(0) & ((1 << WindowBits) - 1)) << 1) : scalar.get_window(WindowBits * i - 1);
280 accum = C::ProjectivePoint::add_or_sub(accum, table[WindowElements * i + tidx - 1], tneg);
365 std::vector<AffinePoint> pts;
374 const auto f2 = f.square();
375 const auto f3 = f2 * f;
380 const auto zt2 = zt.square();
381 return Table{std::move(pts), zt,
a * zt2.square()};
388 std::vector<ProjectivePoint> chain;
391 std::vector<FieldElement> h;
394 chain.push_back(ProjectivePoint::from_affine(p));
395 chain.push_back(chain[0].dbl());
396 for(
size_t i = 2; i != n; ++i) {
397 const auto pt_h = ProjectivePoint::add_mixed_h(chain[i - 1], p);
398 chain.push_back(pt_h.first);
399 h.push_back(pt_h.second);
406 std::vector<AffinePoint> pts;
410 pts.push_back(rescale(chain[n - 1], u));
414 for(
size_t i = n - 2; i > 0; --i) {
419 pts.push_back(rescale(chain[i], mu));
423 pts.push_back(rescale(chain[0], zt));
425 std::reverse(pts.begin(), pts.end());
427 return finish(std::move(pts), zt,
a);
430 static Table build(std::span<const ProjectivePoint> pts,
434 const size_t n = pts.size();
438 std::vector<FieldElement>
z;
440 for(
const auto& pt : pts) {
442 z_i.conditional_assign(pt.is_identity(), one);
447 std::vector<FieldElement> prefix;
449 prefix.push_back(
z[0]);
450 for(
size_t i = 1; i != n; ++i) {
451 prefix.push_back(prefix[i - 1] *
z[i]);
459 std::vector<AffinePoint> scaled;
463 for(
size_t i = n; i > 0; --i) {
464 const size_t idx = i - 1;
469 return rescale(pts[idx], suffix);
471 return rescale(pts[idx], prefix[idx - 1] * suffix);
474 pt.conditional_assign(pts[idx].is_identity(), AffinePoint::identity(pt));
475 scaled.push_back(pt);
480 std::reverse(scaled.begin(), scaled.end());
482 return finish(std::move(scaled), zt,
a);
485 std::vector<AffinePoint> m_table;
495 const BlindedScalar& scalar,
496 const Blinding& blinding) {
497 const size_t windows = (scalar.bits() + WindowBits - 1) / WindowBits;
500 const size_t w_0 = scalar.get_window((windows - 1) * WindowBits);
501 auto pt = C::ProjectivePoint::from_affine(table.
ct_select(w_0));
502 blinding.randomize_rep(pt, 0);
506 for(
size_t i = 1; i != windows; ++i) {
507 accum = accum.dbl_n_iso(table.
a(), WindowBits);
508 auto w_i = scalar.get_window((windows - i - 1) * WindowBits);
536 accum = C::ProjectivePoint::add_mixed_iso(accum, table.
ct_select(w_i), table.
a());
539 if(i < Blinding::Rerandomizations) {
540 blinding.randomize_rep(accum, i);
545 return typename C::ProjectivePoint(accum.x(), accum.y(), accum.z() * table.
z());
556 static_assert(W >= 2 && W <= 7);
558 constexpr size_t TableSize = 1 << (W - 2);
560 std::vector<typename C::ProjectivePoint> table;
561 table.reserve(TableSize);
563 const auto p2 = C::ProjectivePoint::from_affine(p).dbl();
565 table.push_back(C::ProjectivePoint::from_affine(p));
566 for(
size_t i = 1; i != TableSize; ++i) {
567 table.push_back(table[i - 1] + p2);
596std::vector<typename C::ProjectivePoint>
mul2_setup(
const typename C::AffinePoint& p,
597 const typename C::AffinePoint& q) {
598 static_assert(WindowBits >= 1 && WindowBits <= 4);
601 constexpr size_t TableSize = (1 << (2 * WindowBits)) - 1;
602 constexpr size_t WindowSize = (1 << WindowBits);
604 std::vector<typename C::ProjectivePoint> table;
605 table.reserve(TableSize);
607 for(
size_t i = 0; i != TableSize; ++i) {
608 const size_t t_i = (i + 1);
609 const size_t p_i = t_i % WindowSize;
610 const size_t q_i = (t_i >> WindowBits) % WindowSize;
615 const auto next_tbl_e = [&]() {
616 if(p_i % 2 == 0 && q_i % 2 == 0) {
619 return table[(t_i / 2) - 1].dbl();
620 }
else if(p_i > 0 && q_i > 0) {
623 return p + table[(q_i << WindowBits) - 1];
624 }
else if(q_i == 1) {
625 return table[p_i - 1] + q;
627 return table[p_i - 1] + table[(q_i << WindowBits) - 1];
629 }
else if(p_i > 0 && q_i == 0) {
633 return C::ProjectivePoint::from_affine(p);
636 return p + table[p_i - 1 - 1];
638 }
else if(p_i == 0 && q_i > 0) {
641 return C::ProjectivePoint::from_affine(q);
644 return q + table[((q_i - 1) << WindowBits) - 1];
651 table.emplace_back(next_tbl_e());
659 const BlindedScalar& x,
660 const BlindedScalar& y,
661 const Blinding& blinding) {
662 const size_t Windows = (x.bits() + WindowBits - 1) / WindowBits;
665 const size_t w_1 = x.get_window((Windows - 1) * WindowBits);
666 const size_t w_2 = y.get_window((Windows - 1) * WindowBits);
667 const size_t window = w_1 + (w_2 << WindowBits);
668 auto pt = C::ProjectivePoint::from_affine(table.
ct_select(window));
669 blinding.randomize_rep(pt, 0);
673 for(
size_t i = 1; i != Windows; ++i) {
674 accum = accum.dbl_n_iso(table.
a(), WindowBits);
676 const size_t w_1 = x.get_window((Windows - i - 1) * WindowBits);
677 const size_t w_2 = y.get_window((Windows - i - 1) * WindowBits);
678 const size_t window = w_1 + (w_2 << WindowBits);
679 accum = C::ProjectivePoint::add_mixed_iso(accum, table.
ct_select(window), table.
a());
682 if(i < Blinding::Rerandomizations) {
683 blinding.randomize_rep(accum, i);
688 return typename C::ProjectivePoint(accum.x(), accum.y(), accum.z() * table.
z());