7#ifndef BOTAN_PCURVES_ALGOS_H_
8#define BOTAN_PCURVES_ALGOS_H_
10#include <botan/types.h>
11#include <botan/internal/ct_utils.h>
24 { C::fe_invert2(fe) } -> std::same_as<typename C::FieldElement>;
36 return C::fe_invert2(fe) * fe;
49 { C::fe_sqrt(fe) } -> std::same_as<typename C::FieldElement>;
61 auto z = C::fe_sqrt(fe);
64 z.conditional_assign(!correct, C::FieldElement::zero());
75inline constexpr auto to_affine(
const typename C::ProjectivePoint& pt) {
80 const auto z2_inv = C::fe_invert2(pt.z());
81 const auto z3_inv = z2_inv.square() * pt.z();
82 return typename C::AffinePoint(pt.x() * z2_inv, pt.y() * z3_inv);
85 const auto z2_inv = z_inv.square();
86 const auto z3_inv = z_inv * z2_inv;
87 return typename C::AffinePoint(pt.x() * z2_inv, pt.y() * z3_inv);
97 return pt.x() * C::fe_invert2(pt.z());
100 const auto z2_inv = z_inv.square();
101 return pt.x() * z2_inv;
107 using AffinePoint =
typename C::AffinePoint;
109 const size_t N = projective.size();
110 std::vector<AffinePoint> affine;
115 for(
const auto& pt : projective) {
116 any_identity = any_identity || pt.is_identity();
125 if(N <= 2 || any_identity.
as_bool()) {
129 for(
size_t i = 0; i != N; ++i) {
133 std::vector<typename C::FieldElement> c;
143 c.push_back(projective[0].z());
144 for(
size_t i = 1; i != N; ++i) {
145 c.push_back(c[i - 1] * projective[i].z());
150 for(
size_t i = N - 1; i > 0; --i) {
151 const auto& p = projective[i];
153 const auto z_inv = s_inv * c[i - 1];
154 const auto z2_inv = z_inv.square();
155 const auto z3_inv = z_inv * z2_inv;
157 s_inv = s_inv * p.z();
159 affine.push_back(AffinePoint(p.x() * z2_inv, p.y() * z3_inv));
162 const auto z2_inv = s_inv.square();
163 const auto z3_inv = s_inv * z2_inv;
164 affine.push_back(AffinePoint(projective[0].x() * z2_inv, projective[0].y() * z3_inv));
165 std::reverse(affine.begin(), affine.end());
179template <
typename ProjectivePo
int,
typename FieldElement>
180inline constexpr ProjectivePoint
point_add(
const ProjectivePoint& a,
const ProjectivePoint& b) {
181 const auto a_is_identity = a.is_identity();
182 const auto b_is_identity = b.is_identity();
184 const auto Z1Z1 = a.z().square();
185 const auto Z2Z2 = b.z().square();
186 const auto U1 = a.x() * Z2Z2;
187 const auto U2 = b.x() * Z1Z1;
188 const auto S1 = a.y() * b.z() * Z2Z2;
189 const auto S2 = b.y() * a.z() * Z1Z1;
190 const auto H = U2 - U1;
191 const auto r = S2 - S1;
203 if((r.is_zero() && H.is_zero() && !(a_is_identity && b_is_identity)).as_bool()) {
207 const auto HH = H.square();
208 const auto HHH = H * HH;
209 const auto V = U1 * HH;
210 const auto t2 = r.square();
211 const auto t3 = V + V;
212 const auto t4 = t2 - HHH;
214 const auto t5 = V - X3;
215 const auto t6 = S1 * HHH;
216 const auto t7 = r * t5;
218 const auto t8 = b.z() * H;
219 auto Z3 = a.z() * t8;
222 FieldElement::conditional_assign(X3, Y3, Z3, a_is_identity, b.x(), b.y(), b.z());
225 FieldElement::conditional_assign(X3, Y3, Z3, b_is_identity, a.x(), a.y(), a.z());
227 return ProjectivePoint(X3, Y3, Z3);
230template <
typename ProjectivePo
int,
typename AffinePo
int,
typename FieldElement>
232 const AffinePoint& b,
233 const FieldElement& one) {
234 const auto a_is_identity = a.is_identity();
235 const auto b_is_identity = b.is_identity();
243 const auto Z1Z1 = a.z().square();
244 const auto U2 = b.x() * Z1Z1;
245 const auto S2 = b.y() * a.z() * Z1Z1;
246 const auto H = U2 - a.x();
247 const auto r = S2 - a.y();
259 if((r.is_zero() && H.is_zero() && !(a_is_identity && b_is_identity)).as_bool()) {
263 const auto HH = H.square();
264 const auto HHH = H * HH;
265 const auto V = a.x() * HH;
266 const auto t2 = r.square();
267 const auto t3 = V + V;
268 const auto t4 = t2 - HHH;
270 const auto t5 = V - X3;
271 const auto t6 = a.y() * HHH;
272 const auto t7 = r * t5;
277 FieldElement::conditional_assign(X3, Y3, Z3, a_is_identity, b.x(), b.y(), one);
280 FieldElement::conditional_assign(X3, Y3, Z3, b_is_identity, a.x(), a.y(), a.z());
282 return ProjectivePoint(X3, Y3, Z3);
285template <
typename ProjectivePo
int,
typename AffinePo
int,
typename FieldElement>
287 const AffinePoint& b,
289 const FieldElement& one) {
290 const auto a_is_identity = a.is_identity();
291 const auto b_is_identity = b.is_identity();
300 by.conditional_assign(sub, by.negate());
302 const auto Z1Z1 = a.z().square();
303 const auto U2 = b.x() * Z1Z1;
304 const auto S2 = by * a.z() * Z1Z1;
305 const auto H = U2 - a.x();
306 const auto r = S2 - a.y();
318 if((r.is_zero() && H.is_zero() && !(a_is_identity && b_is_identity)).as_bool()) {
322 const auto HH = H.square();
323 const auto HHH = H * HH;
324 const auto V = a.x() * HH;
325 const auto t2 = r.square();
326 const auto t3 = V + V;
327 const auto t4 = t2 - HHH;
329 const auto t5 = V - X3;
330 const auto t6 = a.y() * HHH;
331 const auto t7 = r * t5;
336 FieldElement::conditional_assign(X3, Y3, Z3, a_is_identity, b.x(), by, one);
339 FieldElement::conditional_assign(X3, Y3, Z3, b_is_identity, a.x(), a.y(), a.z());
341 return ProjectivePoint(X3, Y3, Z3);
354template <
typename ProjectivePo
int>
360 const auto z2 = pt.z().square();
361 const auto m = (pt.x() - z2).mul3() * (pt.x() + z2);
364 const auto y2 = pt.y().square();
365 const auto s = pt.x().mul4() * y2;
366 const auto nx = m.square() - s.mul2();
367 const auto ny = m * (s - nx) - y2.square().mul8();
368 const auto nz = pt.y().mul2() * pt.z();
370 return ProjectivePoint(nx, ny, nz);
373template <
typename ProjectivePo
int>
374inline constexpr ProjectivePoint
dbl_a_zero(
const ProjectivePoint& pt) {
377 const auto m = pt.x().square().mul3();
380 const auto y2 = pt.y().square();
381 const auto s = pt.x().mul4() * y2;
382 const auto nx = m.square() - s.mul2();
383 const auto ny = m * (s - nx) - y2.square().mul8();
384 const auto nz = pt.y().mul2() * pt.z();
386 return ProjectivePoint(nx, ny, nz);
389template <
typename ProjectivePo
int,
typename FieldElement>
390inline constexpr ProjectivePoint
dbl_generic(
const ProjectivePoint& pt,
const FieldElement& A) {
392 const auto z2 = pt.z().square();
393 const auto m = pt.x().square().mul3() + A * z2.square();
396 const auto y2 = pt.y().square();
397 const auto s = pt.x().mul4() * y2;
398 const auto nx = m.square() - s.mul2();
399 const auto ny = m * (s - nx) - y2.square().mul8();
400 const auto nz = pt.y().mul2() * pt.z();
402 return ProjectivePoint(nx, ny, nz);
424template <
typename ProjectivePo
int>
425inline constexpr ProjectivePoint
dbl_n_a_minus_3(
const ProjectivePoint& pt,
size_t n) {
427 auto ny = pt.y().mul2();
429 auto w = nz.square().square();
433 const auto ny2 = ny.square();
434 const auto ny4 = ny2.square();
435 const auto t1 = (nx.square() - w).mul3();
436 const auto t2 = nx * ny2;
437 nx = t1.square() - t2.mul2();
439 ny = t1 * (t2 - nx).mul2() - ny4;
446 return ProjectivePoint(nx, ny.div2(), nz);
449template <
typename ProjectivePo
int>
450inline constexpr ProjectivePoint
dbl_n_a_zero(
const ProjectivePoint& pt,
size_t n) {
452 auto ny = pt.y().mul2();
457 const auto ny2 = ny.square();
458 const auto ny4 = ny2.square();
459 const auto t1 = nx.square().mul3();
460 const auto t2 = nx * ny2;
461 nx = t1.square() - t2.mul2();
463 ny = t1 * (t2 - nx).mul2() - ny4;
466 return ProjectivePoint(nx, ny.div2(), nz);
469template <
typename ProjectivePo
int,
typename FieldElement>
470inline constexpr ProjectivePoint
dbl_n_generic(
const ProjectivePoint& pt,
const FieldElement& A,
size_t n) {
472 auto ny = pt.y().mul2();
474 auto w = nz.square().square() * A;
478 const auto ny2 = ny.square();
479 const auto ny4 = ny2.square();
480 const auto t1 = nx.square().mul3() + w;
481 const auto t2 = nx * ny2;
482 nx = t1.square() - t2.mul2();
484 ny = t1 * (t2 - nx).mul2() - ny4;
491 return ProjectivePoint(nx, ny.div2(), nz);
static constexpr Choice no()
constexpr bool as_bool() const
auto to_affine_batch(std::span< const typename C::ProjectivePoint > projective)
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)
constexpr ProjectivePoint dbl_a_zero(const ProjectivePoint &pt)
constexpr auto to_affine(const typename C::ProjectivePoint &pt)
constexpr ProjectivePoint point_add_mixed(const ProjectivePoint &a, const AffinePoint &b, const FieldElement &one)
constexpr ProjectivePoint point_add_or_sub_mixed(const ProjectivePoint &a, const AffinePoint &b, CT::Choice sub, const FieldElement &one)
constexpr auto invert_field_element(const typename C::FieldElement &fe)
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)