7#ifndef BOTAN_PCURVES_ALGOS_H_
8#define BOTAN_PCURVES_ALGOS_H_
10#include <botan/types.h>
11#include <botan/internal/ct_utils.h>
26 { C::fe_invert2(fe) } -> std::same_as<typename C::FieldElement>;
38 return C::fe_invert2(fe) * fe;
51 { C::fe_sqrt(fe) } -> std::same_as<typename C::FieldElement>;
63 auto z = C::fe_sqrt(fe);
66 z.conditional_assign(!correct, C::FieldElement::zero());
77inline constexpr auto to_affine(
const typename C::ProjectivePoint& pt) {
82 const auto z2_inv = C::fe_invert2(pt.z());
83 const auto z3_inv = z2_inv.square() * pt.z();
84 return typename C::AffinePoint(pt.x() * z2_inv, pt.y() * z3_inv);
87 const auto z2_inv = z_inv.square();
88 const auto z3_inv = z_inv * z2_inv;
89 return typename C::AffinePoint(pt.x() * z2_inv, pt.y() * z3_inv);
99 return pt.x() * C::fe_invert2(pt.z());
102 const auto z2_inv = z_inv.square();
103 return pt.x() * z2_inv;
107template <
typename C,
bool VariableTime = false>
109 using AffinePoint =
typename C::AffinePoint;
111 const size_t N = projective.size();
112 std::vector<AffinePoint> affine;
117 for(
const auto& pt : projective) {
118 any_identity = any_identity || pt.is_identity();
127 if(N <= 2 || any_identity.
as_bool()) {
131 for(
size_t i = 0; i != N; ++i) {
135 std::vector<typename C::FieldElement> c;
145 c.push_back(projective[0].z());
146 for(
size_t i = 1; i != N; ++i) {
147 c.push_back(c[i - 1] * projective[i].z());
151 if constexpr(VariableTime) {
152 return c[N - 1].invert_vartime();
158 for(
size_t i = N - 1; i > 0; --i) {
159 const auto& p = projective[i];
161 const auto z_inv = s_inv * c[i - 1];
162 const auto z2_inv = z_inv.square();
163 const auto z3_inv = z_inv * z2_inv;
165 s_inv = s_inv * p.z();
167 affine.push_back(AffinePoint(p.x() * z2_inv, p.y() * z3_inv));
170 const auto z2_inv = s_inv.square();
171 const auto z3_inv = s_inv * z2_inv;
172 affine.push_back(AffinePoint(projective[0].x() * z2_inv, projective[0].y() * z3_inv));
173 std::reverse(affine.begin(), affine.end());
187template <
typename ProjectivePo
int,
typename FieldElement>
188inline constexpr ProjectivePoint
point_add(
const ProjectivePoint& a,
const ProjectivePoint& b) {
189 const auto a_is_identity = a.is_identity();
190 const auto b_is_identity = b.is_identity();
192 const auto Z1Z1 = a.z().square();
193 const auto Z2Z2 = b.z().square();
194 const auto U1 = a.x() * Z2Z2;
195 const auto U2 = b.x() * Z1Z1;
196 const auto S1 = a.y() * b.z() * Z2Z2;
197 const auto S2 = b.y() * a.z() * Z1Z1;
198 const auto H = U2 - U1;
199 const auto r = S2 - S1;
211 if((r.is_zero() && H.is_zero() && !(a_is_identity && b_is_identity)).as_bool()) {
215 const auto HH = H.square();
216 const auto HHH = H * HH;
217 const auto V = U1 * HH;
218 const auto t2 = r.square();
219 const auto t3 = V + V;
220 const auto t4 = t2 - HHH;
222 const auto t5 = V - X3;
223 const auto t6 = S1 * HHH;
224 const auto t7 = r * t5;
226 const auto t8 = b.z() * H;
227 auto Z3 = a.z() * t8;
230 FieldElement::conditional_assign(X3, Y3, Z3, a_is_identity, b.x(), b.y(), b.z());
233 FieldElement::conditional_assign(X3, Y3, Z3, b_is_identity, a.x(), a.y(), a.z());
235 return ProjectivePoint(X3, Y3, Z3);
246template <
typename ProjectivePo
int,
typename AffinePo
int,
typename FieldElement>
247inline constexpr std::pair<ProjectivePoint, FieldElement>
point_add_mixed_h(
const ProjectivePoint& a,
248 const AffinePoint& b,
249 const FieldElement& one,
250 const FieldElement& curve_a) {
251 const auto a_is_identity = a.is_identity();
252 const auto b_is_identity = b.is_identity();
260 const auto Z1Z1 = a.z().square();
261 const auto U2 = b.x() * Z1Z1;
262 const auto S2 = b.y() * a.z() * Z1Z1;
263 const auto H = U2 - a.x();
264 const auto r = S2 - a.y();
276 if((r.is_zero() && H.is_zero() && !(a_is_identity && b_is_identity)).as_bool()) {
277 return {a.dbl_iso(curve_a), H};
280 const auto HH = H.square();
281 const auto HHH = H * HH;
282 const auto V = a.x() * HH;
283 const auto t2 = r.square();
284 const auto t3 = V + V;
285 const auto t4 = t2 - HHH;
287 const auto t5 = V - X3;
288 const auto t6 = a.y() * HHH;
289 const auto t7 = r * t5;
294 FieldElement::conditional_assign(X3, Y3, Z3, a_is_identity, b.x(), b.y(), one);
297 FieldElement::conditional_assign(X3, Y3, Z3, b_is_identity, a.x(), a.y(), a.z());
299 return {ProjectivePoint(X3, Y3, Z3), H};
302template <
typename ProjectivePo
int,
typename AffinePo
int,
typename FieldElement>
304 const AffinePoint& b,
305 const FieldElement& one,
306 const FieldElement& curve_a) {
313template <
typename ProjectivePo
int,
typename AffinePo
int,
typename FieldElement>
315 const AffinePoint& b,
317 const FieldElement& one,
318 const FieldElement& curve_a) {
319 const auto a_is_identity = a.is_identity();
320 const auto b_is_identity = b.is_identity();
329 by.conditional_assign(sub, by.negate());
331 const auto Z1Z1 = a.z().square();
332 const auto U2 = b.x() * Z1Z1;
333 const auto S2 = by * a.z() * Z1Z1;
334 const auto H = U2 - a.x();
335 const auto r = S2 - a.y();
347 if((r.is_zero() && H.is_zero() && !(a_is_identity && b_is_identity)).as_bool()) {
348 return a.dbl_iso(curve_a);
351 const auto HH = H.square();
352 const auto HHH = H * HH;
353 const auto V = a.x() * HH;
354 const auto t2 = r.square();
355 const auto t3 = V + V;
356 const auto t4 = t2 - HHH;
358 const auto t5 = V - X3;
359 const auto t6 = a.y() * HHH;
360 const auto t7 = r * t5;
365 FieldElement::conditional_assign(X3, Y3, Z3, a_is_identity, b.x(), by, one);
368 FieldElement::conditional_assign(X3, Y3, Z3, b_is_identity, a.x(), a.y(), a.z());
370 return ProjectivePoint(X3, Y3, Z3);
383template <
typename ProjectivePo
int>
389 const auto z2 = pt.z().square();
390 const auto m = (pt.x() - z2).mul3() * (pt.x() + z2);
393 const auto y2 = pt.y().square();
394 const auto s = pt.x().mul4() * y2;
395 const auto nx = m.square() - s.mul2();
396 const auto ny = m * (s - nx) - y2.square().mul8();
397 const auto nz = pt.y().mul2() * pt.z();
399 return ProjectivePoint(nx, ny, nz);
402template <
typename ProjectivePo
int>
403inline constexpr ProjectivePoint
dbl_a_zero(
const ProjectivePoint& pt) {
406 const auto m = pt.x().square().mul3();
409 const auto y2 = pt.y().square();
410 const auto s = pt.x().mul4() * y2;
411 const auto nx = m.square() - s.mul2();
412 const auto ny = m * (s - nx) - y2.square().mul8();
413 const auto nz = pt.y().mul2() * pt.z();
415 return ProjectivePoint(nx, ny, nz);
418template <
typename ProjectivePo
int,
typename FieldElement>
419inline constexpr ProjectivePoint
dbl_generic(
const ProjectivePoint& pt,
const FieldElement& A) {
421 const auto z2 = pt.z().square();
422 const auto m = pt.x().square().mul3() + A * z2.square();
425 const auto y2 = pt.y().square();
426 const auto s = pt.x().mul4() * y2;
427 const auto nx = m.square() - s.mul2();
428 const auto ny = m * (s - nx) - y2.square().mul8();
429 const auto nz = pt.y().mul2() * pt.z();
431 return ProjectivePoint(nx, ny, nz);
453template <
typename ProjectivePo
int>
454inline constexpr ProjectivePoint
dbl_n_a_minus_3(
const ProjectivePoint& pt,
size_t n) {
456 auto ny = pt.y().mul2();
458 auto w = nz.square().square();
462 const auto ny2 = ny.square();
463 const auto ny4 = ny2.square();
464 const auto t1 = (nx.square() - w).mul3();
465 const auto t2 = nx * ny2;
466 nx = t1.square() - t2.mul2();
468 ny = t1 * (t2 - nx).mul2() - ny4;
475 return ProjectivePoint(nx, ny.div2(), nz);
478template <
typename ProjectivePo
int>
479inline constexpr ProjectivePoint
dbl_n_a_zero(
const ProjectivePoint& pt,
size_t n) {
481 auto ny = pt.y().mul2();
486 const auto ny2 = ny.square();
487 const auto ny4 = ny2.square();
488 const auto t1 = nx.square().mul3();
489 const auto t2 = nx * ny2;
490 nx = t1.square() - t2.mul2();
492 ny = t1 * (t2 - nx).mul2() - ny4;
495 return ProjectivePoint(nx, ny.div2(), nz);
498template <
typename ProjectivePo
int,
typename FieldElement>
499inline constexpr ProjectivePoint
dbl_n_generic(
const ProjectivePoint& pt,
const FieldElement& A,
size_t n) {
501 auto ny = pt.y().mul2();
503 auto w = nz.square().square() * A;
507 const auto ny2 = ny.square();
508 const auto ny4 = ny2.square();
509 const auto t1 = nx.square().mul3() + w;
510 const auto t2 = nx * ny2;
511 nx = t1.square() - t2.mul2();
513 ny = t1 * (t2 - nx).mul2() - ny4;
520 return ProjectivePoint(nx, ny.div2(), nz);
static constexpr Choice no()
constexpr bool as_bool() const
auto to_affine_x(const typename C::ProjectivePoint &pt)
constexpr CT::Option< typename C::FieldElement > sqrt_field_element(const typename C::FieldElement &fe)
constexpr ProjectivePoint dbl_n_generic(const ProjectivePoint &pt, const FieldElement &A, size_t n)
constexpr ProjectivePoint dbl_a_minus_3(const ProjectivePoint &pt)
constexpr ProjectivePoint dbl_n_a_zero(const ProjectivePoint &pt, size_t n)
auto to_affine_batch(std::span< const typename C::ProjectivePoint > projective)
constexpr ProjectivePoint dbl_a_zero(const ProjectivePoint &pt)
constexpr auto to_affine(const typename C::ProjectivePoint &pt)
constexpr auto invert_field_element(const typename C::FieldElement &fe)
constexpr ProjectivePoint point_add_or_sub_mixed(const ProjectivePoint &a, const AffinePoint &b, CT::Choice sub, const FieldElement &one, const FieldElement &curve_a)
constexpr ProjectivePoint dbl_n_a_minus_3(const ProjectivePoint &pt, size_t n)
constexpr ProjectivePoint dbl_generic(const ProjectivePoint &pt, const FieldElement &A)
constexpr ProjectivePoint point_add(const ProjectivePoint &a, const ProjectivePoint &b)
constexpr std::pair< ProjectivePoint, FieldElement > point_add_mixed_h(const ProjectivePoint &a, const AffinePoint &b, const FieldElement &one, const FieldElement &curve_a)
constexpr ProjectivePoint point_add_mixed(const ProjectivePoint &a, const AffinePoint &b, const FieldElement &one, const FieldElement &curve_a)