k256/arithmetic/

projective.rs

//! Projective points

#![allow(clippy::op_ref)]

use super::{AffinePoint, CURVE_EQUATION_B_SINGLE, FieldElement, Scalar};
use crate::{CompressedPoint, PublicKey, Sec1Point, Secp256k1};
use core::{
    iter::Sum,
    ops::{Add, AddAssign, Neg, Sub, SubAssign},
};
use elliptic_curve::{
    BatchNormalize, CurveGroup, Error, Generate, Result,
    array::{Array, ArraySize},
    ctutils,
    group::{
        CurveAffine, Group, GroupEncoding,
        cofactor::CofactorGroup,
        prime::{PrimeCurve, PrimeGroup},
    },
    ops::{BatchInvert, Double},
    point::NonIdentity,
    rand_core::{TryCryptoRng, TryRng},
    sec1::{FromSec1Point, ToSec1Point},
    subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption},
    zeroize::DefaultIsZeroes,
};

#[cfg(feature = "alloc")]
use alloc::vec::Vec;

#[rustfmt::skip]
const ENDOMORPHISM_BETA: FieldElement = FieldElement::from_bytes_unchecked(&[
    0x7a, 0xe9, 0x6a, 0x2b, 0x65, 0x7c, 0x07, 0x10,
    0x6e, 0x64, 0x47, 0x9e, 0xac, 0x34, 0x34, 0xe9,
    0x9c, 0xf0, 0x49, 0x75, 0x12, 0xf5, 0x89, 0x95,
    0xc1, 0x39, 0x6c, 0x28, 0x71, 0x95, 0x01, 0xee,
]);

/// A point on the secp256k1 curve in projective coordinates.
#[derive(Clone, Copy, Debug)]
pub struct ProjectivePoint {
    x: FieldElement,
    y: FieldElement,
    pub(super) z: FieldElement,
}

impl ProjectivePoint {
    /// Additive identity of the group: the point at infinity.
    pub const IDENTITY: Self = Self {
        x: FieldElement::ZERO,
        y: FieldElement::ONE,
        z: FieldElement::ZERO,
    };

    /// Base point of secp256k1.
    pub const GENERATOR: Self = Self {
        x: AffinePoint::GENERATOR.x,
        y: AffinePoint::GENERATOR.y,
        z: FieldElement::ONE,
    };

    /// Returns the affine representation of this point.
    #[must_use]
    pub fn to_affine(&self) -> AffinePoint {
        self.z
            .invert()
            .map(|zinv| self.to_affine_internal(zinv))
            .unwrap_or_else(|| AffinePoint::IDENTITY)
    }

    pub(super) fn to_affine_internal(self, zinv: FieldElement) -> AffinePoint {
        let x = self.x * &zinv;
        let y = self.y * &zinv;
        AffinePoint::new(x.normalize(), y.normalize())
    }

    /// Returns `-self`.
    #[inline]
    fn neg(&self) -> ProjectivePoint {
        ProjectivePoint {
            x: self.x,
            y: self.y.negate(1).normalize_weak(),
            z: self.z,
        }
    }

    /// Returns `self + other`.
    #[inline]
    fn add(&self, other: &ProjectivePoint) -> ProjectivePoint {
        let mut ret = *self;
        ret.add_assign(other);
        ret
    }

    /// Assign `self + other` to `self`.
    fn add_assign(&mut self, other: &ProjectivePoint) {
        // We implement the complete addition formula from Renes-Costello-Batina 2015
        // (https://eprint.iacr.org/2015/1060 Algorithm 7).

        let xx = self.x * &other.x;
        let yy = self.y * &other.y;
        let zz = self.z * &other.z;

        let n_xx_yy = (xx + &yy).negate(2);
        let n_yy_zz = (yy + &zz).negate(2);
        let n_xx_zz = (xx + &zz).negate(2);
        let xy_pairs = ((self.x + &self.y) * &(other.x + &other.y)) + &n_xx_yy;
        let yz_pairs = ((self.y + &self.z) * &(other.y + &other.z)) + &n_yy_zz;
        let xz_pairs = ((self.x + &self.z) * &(other.x + &other.z)) + &n_xx_zz;

        let bzz = zz.mul_single(CURVE_EQUATION_B_SINGLE);
        let bzz3 = (bzz.double() + &bzz).normalize_weak();

        let yy_m_bzz3 = yy + &bzz3.negate(1);
        let yy_p_bzz3 = yy + &bzz3;

        let byz = &yz_pairs
            .mul_single(CURVE_EQUATION_B_SINGLE)
            .normalize_weak();
        let byz3 = (byz.double() + byz).normalize_weak();

        let xx3 = xx.double() + &xx;
        let bxx9 = (xx3.double() + &xx3)
            .normalize_weak()
            .mul_single(CURVE_EQUATION_B_SINGLE)
            .normalize_weak();

        self.x = ((xy_pairs * &yy_m_bzz3) + &(byz3 * &xz_pairs).negate(1)).normalize_weak(); // m1
        self.y = ((yy_p_bzz3 * &yy_m_bzz3) + &(bxx9 * &xz_pairs)).normalize_weak();
        self.z = ((yz_pairs * &yy_p_bzz3) + &(xx3 * &xy_pairs)).normalize_weak();
    }

    /// Returns `self + other`.
    #[inline]
    fn add_mixed(&self, other: &AffinePoint) -> ProjectivePoint {
        let mut ret = *self;
        ret.add_assign_mixed(other);
        ret
    }

    /// Assign `self + other` to `self`.
    fn add_assign_mixed(&mut self, other: &AffinePoint) {
        // We implement the complete addition formula from Renes-Costello-Batina 2015
        // (https://eprint.iacr.org/2015/1060 Algorithm 8).

        let xx = self.x * &other.x;
        let yy = self.y * &other.y;
        let xy_pairs = ((self.x + &self.y) * &(other.x + &other.y)) + &(xx + &yy).negate(2);
        let yz_pairs = (other.y * &self.z) + &self.y;
        let xz_pairs = (other.x * &self.z) + &self.x;

        let bzz = &self.z.mul_single(CURVE_EQUATION_B_SINGLE);
        let bzz3 = (bzz.double() + bzz).normalize_weak();

        let yy_m_bzz3 = yy + &bzz3.negate(1);
        let yy_p_bzz3 = yy + &bzz3;

        let byz = &yz_pairs
            .mul_single(CURVE_EQUATION_B_SINGLE)
            .normalize_weak();
        let byz3 = (byz.double() + byz).normalize_weak();

        let xx3 = xx.double() + &xx;
        let bxx9 = &(xx3.double() + &xx3)
            .normalize_weak()
            .mul_single(CURVE_EQUATION_B_SINGLE)
            .normalize_weak();

        let x = ((xy_pairs * &yy_m_bzz3) + &(byz3 * &xz_pairs).negate(1)).normalize_weak();
        let y = ((yy_p_bzz3 * &yy_m_bzz3) + &(bxx9 * &xz_pairs)).normalize_weak();
        let z = ((yz_pairs * &yy_p_bzz3) + &(xx3 * &xy_pairs)).normalize_weak();

        self.x.conditional_assign(&x, !other.is_identity());
        self.y.conditional_assign(&y, !other.is_identity());
        self.z.conditional_assign(&z, !other.is_identity());
    }

    /// Doubles this point.
    #[inline]
    #[must_use]
    pub fn double(&self) -> ProjectivePoint {
        let mut ret = *self;
        ret.double_in_place();
        ret
    }

    /// Doubles this point in-place.
    #[inline]
    pub fn double_in_place(&mut self) {
        // We implement the complete addition formula from Renes-Costello-Batina 2015
        // (https://eprint.iacr.org/2015/1060 Algorithm 9).

        let yy = self.y.square();
        let zz = self.z.square();
        let xy2 = (self.x * &self.y).double();

        let bzz = &zz.mul_single(CURVE_EQUATION_B_SINGLE);
        let bzz3 = (bzz.double() + bzz).normalize_weak();
        let bzz9 = (bzz3.double() + &bzz3).normalize_weak();

        let yy_m_bzz9 = yy + &bzz9.negate(1);
        let yy_p_bzz3 = yy + &bzz3;

        let yy_zz = yy * &zz;
        let yy_zz8 = yy_zz.double().double().double();
        let t = (yy_zz8.double() + &yy_zz8)
            .normalize_weak()
            .mul_single(CURVE_EQUATION_B_SINGLE);

        self.x = xy2 * &yy_m_bzz9;
        self.z = ((yy * &self.y) * &self.z)
            .double()
            .double()
            .double()
            .normalize_weak();
        self.y = ((yy_m_bzz9 * &yy_p_bzz3) + &t).normalize_weak();
    }

    /// Returns `self - other`.
    fn sub(&self, other: &ProjectivePoint) -> ProjectivePoint {
        self.add(&other.neg())
    }

    /// Assign `self - other` to `self`.
    fn sub_assign(&mut self, other: &ProjectivePoint) {
        self.add_assign(&other.neg());
    }

    /// Returns `self - other`.
    fn sub_mixed(&self, other: &AffinePoint) -> ProjectivePoint {
        self.add_mixed(&other.neg())
    }

    /// Assign `self - other` to `self`.
    fn sub_assign_mixed(&mut self, other: &AffinePoint) {
        self.add_assign_mixed(&other.neg());
    }

    /// Calculates SECP256k1 endomorphism: `self * lambda`.
    #[must_use]
    pub fn endomorphism(&self) -> Self {
        Self {
            x: self.x * &ENDOMORPHISM_BETA,
            y: self.y,
            z: self.z,
        }
    }

    /// Check whether `self` is equal to an affine point.
    ///
    /// This is a lot faster than first converting `self` to an `AffinePoint` and then doing the
    /// comparison. It is a little bit faster than converting `other` to a `ProjectivePoint` first.
    #[must_use]
    pub fn eq_affine(&self, other: &AffinePoint) -> Choice {
        // For understanding of this algorithm see Projective equality comment. It's the same except
        // that we know z = 1 for rhs and we have to check identity as a separate case.
        let both_identity = self.is_identity() & other.is_identity();
        let rhs_identity = other.is_identity();
        let rhs_x = &other.x * &self.z;
        let x_eq = rhs_x.negate(1).add(&self.x).normalizes_to_zero();

        let rhs_y = &other.y * &self.z;
        let y_eq = rhs_y.negate(1).add(&self.y).normalizes_to_zero();

        both_identity | (!rhs_identity & x_eq & y_eq)
    }
}

impl Double for ProjectivePoint {
    #[inline]
    fn double(&self) -> Self {
        self.double()
    }

    #[inline]
    fn double_in_place(&mut self) {
        self.double_in_place();
    }
}

impl From<AffinePoint> for ProjectivePoint {
    fn from(p: AffinePoint) -> Self {
        let projective = ProjectivePoint {
            x: p.x,
            y: p.y,
            z: FieldElement::ONE,
        };
        Self::conditional_select(&projective, &Self::IDENTITY, p.is_identity())
    }
}

impl Generate for ProjectivePoint {
    fn try_generate_from_rng<R: TryCryptoRng + ?Sized>(
        rng: &mut R,
    ) -> core::result::Result<Self, R::Error> {
        AffinePoint::try_generate_from_rng(rng).map(Into::into)
    }
}

impl<const N: usize> BatchNormalize<[ProjectivePoint; N]> for ProjectivePoint {
    type Output = [AffinePoint; N];

    #[inline]
    fn batch_normalize(points: &[Self; N]) -> [AffinePoint; N] {
        let mut zs = [FieldElement::ZERO; N];
        let mut scratch = [FieldElement::ZERO; N];
        let mut affine_points = [AffinePoint::IDENTITY; N];
        batch_normalize(points, &mut zs, &mut scratch, &mut affine_points);
        affine_points
    }

    #[inline]
    fn batch_normalize_vartime(points: &[Self; N]) -> [AffinePoint; N] {
        let mut zs = [FieldElement::ZERO; N];
        let mut scratch = [FieldElement::ZERO; N];
        let mut affine_points = [AffinePoint::IDENTITY; N];
        batch_normalize_vartime(points, &mut zs, &mut scratch, &mut affine_points);
        affine_points
    }
}

impl<U: ArraySize> BatchNormalize<Array<ProjectivePoint, U>> for ProjectivePoint {
    type Output = Array<AffinePoint, U>;

    #[inline]
    fn batch_normalize(points: &Array<Self, U>) -> Array<AffinePoint, U> {
        let mut zs = Array::<FieldElement, U>::default();
        let mut scratch = Array::<FieldElement, U>::default();
        let mut affine_points = Array::<AffinePoint, U>::default();
        batch_normalize(points, &mut zs, &mut scratch, &mut affine_points);
        affine_points
    }

    #[inline]
    fn batch_normalize_vartime(points: &Array<Self, U>) -> Array<AffinePoint, U> {
        let mut zs = Array::<FieldElement, U>::default();
        let mut scratch = Array::<FieldElement, U>::default();
        let mut affine_points = Array::<AffinePoint, U>::default();
        batch_normalize_vartime(points, &mut zs, &mut scratch, &mut affine_points);
        affine_points
    }
}

#[cfg(feature = "alloc")]
impl BatchNormalize<[ProjectivePoint]> for ProjectivePoint {
    type Output = Vec<AffinePoint>;

    #[inline]
    fn batch_normalize(points: &[Self]) -> Vec<AffinePoint> {
        let mut zs = vec![FieldElement::ZERO; points.len()];
        let mut scratch = vec![FieldElement::ZERO; points.len()];
        let mut affine_points = vec![AffinePoint::IDENTITY; points.len()];
        batch_normalize(points, &mut zs, &mut scratch, &mut affine_points);
        affine_points
    }

    #[inline]
    fn batch_normalize_vartime(points: &[Self]) -> Vec<AffinePoint> {
        let mut zs = vec![FieldElement::ZERO; points.len()];
        let mut scratch = vec![FieldElement::ZERO; points.len()];
        let mut affine_points = vec![AffinePoint::IDENTITY; points.len()];
        batch_normalize_vartime(points, &mut zs, &mut scratch, &mut affine_points);
        affine_points
    }
}

fn batch_normalize(
    points: &[ProjectivePoint],
    zs: &mut [FieldElement],
    scratch: &mut [FieldElement],
    out: &mut [AffinePoint],
) {
    debug_assert_eq!(points.len(), zs.len());
    debug_assert_eq!(points.len(), scratch.len());
    debug_assert_eq!(points.len(), out.len());

    for (z, point) in zs.iter_mut().zip(points) {
        *z = point.z;
    }

    // Zero `zs` (identity) are handled explicitly below, so the `Choice` here is informational only
    let _ = FieldElement::batch_invert_in_place(zs, scratch);

    for i in 0..out.len() {
        out[i] = AffinePoint::conditional_select(
            &points[i].to_affine_internal(zs[i]),
            &AffinePoint::IDENTITY,
            points[i].z.normalizes_to_zero(),
        );
    }
}

fn batch_normalize_vartime(
    points: &[ProjectivePoint],
    zs: &mut [FieldElement],
    scratch: &mut [FieldElement],
    out: &mut [AffinePoint],
) {
    debug_assert_eq!(points.len(), zs.len());
    debug_assert_eq!(points.len(), scratch.len());
    debug_assert_eq!(points.len(), out.len());

    for (z, point) in zs.iter_mut().zip(points) {
        *z = point.z;
    }

    // Zero `zs` (identity) are handled explicitly below, so the `Choice` here is informational only
    let _ = FieldElement::batch_invert_in_place_vartime(zs, scratch);

    for i in 0..out.len() {
        out[i] = if bool::from(points[i].z.normalizes_to_zero()) {
            AffinePoint::IDENTITY
        } else {
            points[i].to_affine_internal(zs[i])
        };
    }
}

impl From<&AffinePoint> for ProjectivePoint {
    fn from(p: &AffinePoint) -> Self {
        Self::from(*p)
    }
}

impl From<NonIdentity<ProjectivePoint>> for ProjectivePoint {
    fn from(p: NonIdentity<ProjectivePoint>) -> Self {
        p.to_point()
    }
}

impl From<ProjectivePoint> for AffinePoint {
    fn from(p: ProjectivePoint) -> AffinePoint {
        p.to_affine()
    }
}

impl From<&ProjectivePoint> for AffinePoint {
    fn from(p: &ProjectivePoint) -> AffinePoint {
        p.to_affine()
    }
}

impl FromSec1Point<Secp256k1> for ProjectivePoint {
    fn from_sec1_point(p: &Sec1Point) -> ctutils::CtOption<Self> {
        AffinePoint::from_sec1_point(p).map(ProjectivePoint::from)
    }
}

impl ToSec1Point<Secp256k1> for ProjectivePoint {
    fn to_sec1_point(&self, compress: bool) -> Sec1Point {
        self.to_affine().to_sec1_point(compress)
    }
}

impl ConditionallySelectable for ProjectivePoint {
    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
        ProjectivePoint {
            x: FieldElement::conditional_select(&a.x, &b.x, choice),
            y: FieldElement::conditional_select(&a.y, &b.y, choice),
            z: FieldElement::conditional_select(&a.z, &b.z, choice),
        }
    }
}

impl ConstantTimeEq for ProjectivePoint {
    fn ct_eq(&self, other: &Self) -> Choice {
        // If both points are not equal to infinity then they are in the form:
        //
        // lhs: (x₁z₁, y₁z₁, z₁), rhs: (x₂z₂, y₂z₂, z₂) where z₁ ≠ 0 and z₂ ≠ 0.
        // we want to know if x₁ == x₂ and y₁ == y₂
        // So we multiply the x and y by the opposing z to get:
        // lhs: (x₁z₁z₂, y₁z₁z₂) rhs: (x₂z₁z₂, y₂z₁z₂)
        // and check lhs == rhs which implies x₁ == x₂ and y₁ == y₂.
        //
        // If one point is infinity it is always in the form (0, y, 0). Note that the above
        // algorithm still works here. If They are both infinity then they'll both evaluate to (0,0).
        // If for example the first point is infinity then the above will evaluate to (z₂ * 0, z₂ *
        // y₂) = (0, z₂y₂) for the first point and (0 * x₂z₂, 0 * y₂z₂) = (0, 0) for the second.
        //
        // Since z₂y₂ will never be 0 they will not be equal in this case either.
        let lhs_x = self.x * &other.z;
        let rhs_x = other.x * &self.z;
        let x_eq = rhs_x.negate(1).add(&lhs_x).normalizes_to_zero();

        let lhs_y = self.y * &other.z;
        let rhs_y = other.y * &self.z;
        let y_eq = rhs_y.negate(1).add(&lhs_y).normalizes_to_zero();
        x_eq & y_eq
    }
}

impl ctutils::CtEq for ProjectivePoint {
    fn ct_eq(&self, other: &Self) -> ctutils::Choice {
        ConstantTimeEq::ct_eq(self, other).into()
    }
}

impl ctutils::CtSelect for ProjectivePoint {
    fn ct_select(&self, other: &Self, choice: ctutils::Choice) -> Self {
        ConditionallySelectable::conditional_select(self, other, choice.into())
    }
}

impl Default for ProjectivePoint {
    fn default() -> Self {
        Self::IDENTITY
    }
}

impl DefaultIsZeroes for ProjectivePoint {}

impl Eq for ProjectivePoint {}

impl PartialEq for ProjectivePoint {
    fn eq(&self, other: &Self) -> bool {
        self.ct_eq(other).into()
    }
}

impl PartialEq<AffinePoint> for ProjectivePoint {
    fn eq(&self, other: &AffinePoint) -> bool {
        self.eq_affine(other).into()
    }
}

impl PartialEq<ProjectivePoint> for AffinePoint {
    fn eq(&self, other: &ProjectivePoint) -> bool {
        other.eq_affine(self).into()
    }
}

//
// `group` trait impls
//

/// secp256k1 has a cofactor of 1.
impl CofactorGroup for ProjectivePoint {
    type Subgroup = Self;

    fn clear_cofactor(&self) -> Self::Subgroup {
        *self
    }

    fn into_subgroup(self) -> CtOption<Self::Subgroup> {
        CtOption::new(self, Choice::from(1))
    }

    fn is_torsion_free(&self) -> Choice {
        Choice::from(1)
    }
}

impl CurveGroup for ProjectivePoint {
    type Affine = AffinePoint;

    fn to_affine(&self) -> AffinePoint {
        ProjectivePoint::to_affine(self)
    }

    #[cfg(feature = "alloc")]
    #[inline]
    fn batch_normalize(projective: &[Self], affine: &mut [Self::Affine]) {
        assert_eq!(projective.len(), affine.len());
        let mut zs = vec![FieldElement::ZERO; projective.len()];
        let mut scratch = vec![FieldElement::ZERO; projective.len()];
        batch_normalize(projective, &mut zs, &mut scratch, affine);
    }
}

impl Group for ProjectivePoint {
    type Scalar = Scalar;

    fn try_random<R: TryRng + ?Sized>(rng: &mut R) -> core::result::Result<Self, R::Error> {
        AffinePoint::try_random(rng).map(Self::from)
    }

    fn identity() -> Self {
        Self::IDENTITY
    }

    fn generator() -> Self {
        Self::GENERATOR
    }

    fn is_identity(&self) -> Choice {
        self.z.normalizes_to_zero()
    }

    #[inline]
    fn double(&self) -> Self {
        Self::double(self)
    }

    #[inline]
    fn mul_by_generator(k: &Scalar) -> Self {
        Self::mul_by_generator(k)
    }
}

impl GroupEncoding for ProjectivePoint {
    type Repr = CompressedPoint;

    fn from_bytes(bytes: &Self::Repr) -> CtOption<Self> {
        <AffinePoint as GroupEncoding>::from_bytes(bytes).map(Into::into)
    }

    fn from_bytes_unchecked(bytes: &Self::Repr) -> CtOption<Self> {
        // No unchecked conversion possible for compressed points
        Self::from_bytes(bytes)
    }

    fn to_bytes(&self) -> Self::Repr {
        self.to_affine().to_bytes()
    }
}

impl PrimeCurve for ProjectivePoint {}
impl PrimeGroup for ProjectivePoint {}

//
// `core::ops` trait impls
//

impl Add<&ProjectivePoint> for &ProjectivePoint {
    type Output = ProjectivePoint;

    #[inline]
    fn add(self, rhs: &ProjectivePoint) -> ProjectivePoint {
        ProjectivePoint::add(self, rhs)
    }
}

impl Add<ProjectivePoint> for ProjectivePoint {
    type Output = ProjectivePoint;

    #[inline]
    fn add(self, rhs: ProjectivePoint) -> ProjectivePoint {
        ProjectivePoint::add(&self, &rhs)
    }
}

impl Add<&ProjectivePoint> for ProjectivePoint {
    type Output = ProjectivePoint;

    #[inline]
    fn add(self, rhs: &ProjectivePoint) -> ProjectivePoint {
        ProjectivePoint::add(&self, rhs)
    }
}

impl AddAssign<ProjectivePoint> for ProjectivePoint {
    #[inline]
    fn add_assign(&mut self, rhs: ProjectivePoint) {
        ProjectivePoint::add_assign(self, &rhs);
    }
}

impl AddAssign<&ProjectivePoint> for ProjectivePoint {
    #[inline]
    fn add_assign(&mut self, rhs: &ProjectivePoint) {
        ProjectivePoint::add_assign(self, rhs);
    }
}

impl Add<AffinePoint> for ProjectivePoint {
    type Output = ProjectivePoint;

    #[inline]
    fn add(self, rhs: AffinePoint) -> ProjectivePoint {
        ProjectivePoint::add_mixed(&self, &rhs)
    }
}

impl Add<&AffinePoint> for &ProjectivePoint {
    type Output = ProjectivePoint;

    #[inline]
    fn add(self, rhs: &AffinePoint) -> ProjectivePoint {
        ProjectivePoint::add_mixed(self, rhs)
    }
}

impl Add<&AffinePoint> for ProjectivePoint {
    type Output = ProjectivePoint;

    #[inline]
    fn add(self, rhs: &AffinePoint) -> ProjectivePoint {
        ProjectivePoint::add_mixed(&self, rhs)
    }
}

impl AddAssign<AffinePoint> for ProjectivePoint {
    #[inline]
    fn add_assign(&mut self, rhs: AffinePoint) {
        ProjectivePoint::add_assign_mixed(self, &rhs);
    }
}

impl AddAssign<&AffinePoint> for ProjectivePoint {
    #[inline]
    fn add_assign(&mut self, rhs: &AffinePoint) {
        ProjectivePoint::add_assign_mixed(self, rhs);
    }
}

impl Sum for ProjectivePoint {
    #[inline]
    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
        iter.fold(ProjectivePoint::IDENTITY, |a, b| a + b)
    }
}

impl<'a> Sum<&'a ProjectivePoint> for ProjectivePoint {
    #[inline]
    fn sum<I: Iterator<Item = &'a ProjectivePoint>>(iter: I) -> Self {
        iter.cloned().sum()
    }
}

impl Sub<ProjectivePoint> for ProjectivePoint {
    type Output = ProjectivePoint;

    #[inline]
    fn sub(self, rhs: ProjectivePoint) -> ProjectivePoint {
        ProjectivePoint::sub(&self, &rhs)
    }
}

impl Sub<&ProjectivePoint> for &ProjectivePoint {
    type Output = ProjectivePoint;

    #[inline]
    fn sub(self, rhs: &ProjectivePoint) -> ProjectivePoint {
        ProjectivePoint::sub(self, rhs)
    }
}

impl Sub<&ProjectivePoint> for ProjectivePoint {
    type Output = ProjectivePoint;

    #[inline]
    fn sub(self, rhs: &ProjectivePoint) -> ProjectivePoint {
        ProjectivePoint::sub(&self, rhs)
    }
}

impl SubAssign<ProjectivePoint> for ProjectivePoint {
    #[inline]
    fn sub_assign(&mut self, rhs: ProjectivePoint) {
        ProjectivePoint::sub_assign(self, &rhs);
    }
}

impl SubAssign<&ProjectivePoint> for ProjectivePoint {
    #[inline]
    fn sub_assign(&mut self, rhs: &ProjectivePoint) {
        ProjectivePoint::sub_assign(self, rhs);
    }
}

impl Sub<AffinePoint> for ProjectivePoint {
    type Output = ProjectivePoint;

    #[inline]
    fn sub(self, rhs: AffinePoint) -> ProjectivePoint {
        ProjectivePoint::sub_mixed(&self, &rhs)
    }
}

impl Sub<&AffinePoint> for &ProjectivePoint {
    type Output = ProjectivePoint;

    #[inline]
    fn sub(self, rhs: &AffinePoint) -> ProjectivePoint {
        ProjectivePoint::sub_mixed(self, rhs)
    }
}

impl Sub<&AffinePoint> for ProjectivePoint {
    type Output = ProjectivePoint;

    #[inline]
    fn sub(self, rhs: &AffinePoint) -> ProjectivePoint {
        ProjectivePoint::sub_mixed(&self, rhs)
    }
}

impl SubAssign<AffinePoint> for ProjectivePoint {
    #[inline]
    fn sub_assign(&mut self, rhs: AffinePoint) {
        ProjectivePoint::sub_assign_mixed(self, &rhs);
    }
}

impl SubAssign<&AffinePoint> for ProjectivePoint {
    #[inline]
    fn sub_assign(&mut self, rhs: &AffinePoint) {
        ProjectivePoint::sub_assign_mixed(self, rhs);
    }
}

impl Neg for ProjectivePoint {
    type Output = ProjectivePoint;

    #[inline]
    fn neg(self) -> ProjectivePoint {
        ProjectivePoint::neg(&self)
    }
}

impl Neg for &ProjectivePoint {
    type Output = ProjectivePoint;

    #[inline]
    fn neg(self) -> ProjectivePoint {
        ProjectivePoint::neg(self)
    }
}

impl From<PublicKey> for ProjectivePoint {
    fn from(public_key: PublicKey) -> ProjectivePoint {
        AffinePoint::from(public_key).into()
    }
}

impl From<&PublicKey> for ProjectivePoint {
    fn from(public_key: &PublicKey) -> ProjectivePoint {
        AffinePoint::from(public_key).into()
    }
}

/// The constant-time alternative is available at [`NonIdentity::new()`].
impl TryFrom<ProjectivePoint> for NonIdentity<ProjectivePoint> {
    type Error = Error;

    fn try_from(point: ProjectivePoint) -> Result<Self> {
        NonIdentity::new(point).into_option().ok_or(Error)
    }
}

impl TryFrom<ProjectivePoint> for PublicKey {
    type Error = Error;

    fn try_from(point: ProjectivePoint) -> Result<PublicKey> {
        AffinePoint::from(point).try_into()
    }
}

impl TryFrom<&ProjectivePoint> for PublicKey {
    type Error = Error;

    fn try_from(point: &ProjectivePoint) -> Result<PublicKey> {
        AffinePoint::from(point).try_into()
    }
}

#[cfg(test)]
mod tests {
    use super::{AffinePoint, ProjectivePoint};
    use crate::{
        Scalar,
        test_vectors::group::{ADD_TEST_VECTORS, MUL_TEST_VECTORS},
    };
    use elliptic_curve::group::{CurveAffine, ff::PrimeField};

    #[cfg(all(feature = "alloc", feature = "getrandom"))]
    use alloc::vec::Vec;
    #[cfg(feature = "getrandom")]
    use elliptic_curve::{BatchNormalize, CurveGroup, Generate};

    #[test]
    fn affine_to_projective() {
        let basepoint_affine = AffinePoint::GENERATOR;
        let basepoint_projective = ProjectivePoint::GENERATOR;

        assert_eq!(
            ProjectivePoint::from(basepoint_affine),
            basepoint_projective,
        );
        assert_eq!(basepoint_projective.to_affine(), basepoint_affine);
        assert!(!bool::from(basepoint_projective.to_affine().is_identity()));

        assert!(bool::from(
            ProjectivePoint::IDENTITY.to_affine().is_identity()
        ));
    }

    #[test]
    #[cfg(feature = "getrandom")]
    fn batch_normalize_array() {
        let k = Scalar::generate();
        let l = Scalar::generate();
        let g = ProjectivePoint::mul_by_generator(&k);
        let h = ProjectivePoint::mul_by_generator(&l);

        let mut res = [AffinePoint::IDENTITY; 2];
        let expected = [g.to_affine(), h.to_affine()];
        assert_eq!(
            <ProjectivePoint as BatchNormalize<_>>::batch_normalize(&[g, h]),
            expected
        );

        <ProjectivePoint as CurveGroup>::batch_normalize(&[g, h], &mut res);
        assert_eq!(res, expected);

        let mut res = [AffinePoint::IDENTITY; 3];
        let non_normalized_identity = ProjectivePoint::IDENTITY * Scalar::generate();
        let expected = [g.to_affine(), AffinePoint::IDENTITY, AffinePoint::IDENTITY];
        assert_eq!(
            <ProjectivePoint as BatchNormalize<_>>::batch_normalize(&[
                g,
                ProjectivePoint::IDENTITY,
                non_normalized_identity,
            ]),
            expected
        );

        <ProjectivePoint as CurveGroup>::batch_normalize(
            &[g, ProjectivePoint::IDENTITY, non_normalized_identity],
            &mut res,
        );
        assert_eq!(res, expected);
    }

    #[test]
    #[cfg(all(feature = "alloc", feature = "getrandom"))]
    fn batch_normalize_slice() {
        let k: Scalar = Scalar::generate();
        let l: Scalar = Scalar::generate();
        let g = ProjectivePoint::mul_by_generator(&k);
        let h = ProjectivePoint::mul_by_generator(&l);

        let expected = vec![g.to_affine(), h.to_affine()];
        let scalars = vec![g, h];
        let mut res: Vec<_> =
            <ProjectivePoint as BatchNormalize<_>>::batch_normalize(scalars.as_slice());
        assert_eq!(res, expected);

        <ProjectivePoint as CurveGroup>::batch_normalize(&[g, h], res.as_mut());
        assert_eq!(res.to_vec(), expected);

        let expected = vec![g.to_affine(), AffinePoint::IDENTITY];
        let scalars = vec![g, ProjectivePoint::IDENTITY];
        res = <ProjectivePoint as BatchNormalize<_>>::batch_normalize(scalars.as_slice());

        assert_eq!(res, expected);

        <ProjectivePoint as CurveGroup>::batch_normalize(
            &[g, ProjectivePoint::IDENTITY],
            res.as_mut(),
        );
        assert_eq!(res.to_vec(), expected);
    }

    #[test]
    fn projective_identity_addition() {
        let identity = ProjectivePoint::IDENTITY;
        let generator = ProjectivePoint::GENERATOR;

        assert_eq!(identity + &generator, generator);
        assert_eq!(generator + &identity, generator);
    }

    #[test]
    fn projective_mixed_addition() {
        let identity = ProjectivePoint::IDENTITY;
        let basepoint_affine = AffinePoint::GENERATOR;
        let basepoint_projective = ProjectivePoint::GENERATOR;

        assert_eq!(identity + &basepoint_affine, basepoint_projective);
        assert_eq!(
            basepoint_projective + &basepoint_affine,
            basepoint_projective + &basepoint_projective
        );
    }

    #[test]
    fn test_vector_repeated_add() {
        let generator = ProjectivePoint::GENERATOR;
        let mut p = generator;

        for i in 0..ADD_TEST_VECTORS.len() {
            let affine = p.to_affine();

            let (expected_x, expected_y) = ADD_TEST_VECTORS[i];
            assert_eq!(affine.x.to_bytes(), expected_x);
            assert_eq!(affine.y.to_bytes(), expected_y);

            p += &generator;
        }
    }

    #[test]
    fn test_vector_repeated_add_mixed() {
        let generator = AffinePoint::GENERATOR;
        let mut p = ProjectivePoint::GENERATOR;

        for i in 0..ADD_TEST_VECTORS.len() {
            let affine = p.to_affine();

            let (expected_x, expected_y) = ADD_TEST_VECTORS[i];
            assert_eq!(affine.x.to_bytes(), expected_x);
            assert_eq!(affine.y.to_bytes(), expected_y);

            p += &generator;
        }
    }

    #[test]
    fn test_vector_add_mixed_identity() {
        let generator = ProjectivePoint::GENERATOR;
        let p0 = generator + ProjectivePoint::IDENTITY;
        let p1 = generator + AffinePoint::IDENTITY;
        assert_eq!(p0, p1);
    }

    #[test]
    fn test_vector_double_generator() {
        let generator = ProjectivePoint::GENERATOR;
        let mut p = generator;

        for i in 0..2 {
            let affine = p.to_affine();

            let (expected_x, expected_y) = ADD_TEST_VECTORS[i];
            assert_eq!(affine.x.to_bytes(), expected_x);
            assert_eq!(affine.y.to_bytes(), expected_y);

            p = p.double();
        }
    }

    #[test]
    fn projective_add_vs_double() {
        let generator = ProjectivePoint::GENERATOR;

        let r1 = generator + &generator;
        let r2 = generator.double();
        assert_eq!(r1, r2);

        let r1 = (generator + &generator) + &(generator + &generator);
        let r2 = generator.double().double();
        assert_eq!(r1, r2);
    }

    #[test]
    fn projective_add_and_sub() {
        let basepoint_affine = AffinePoint::GENERATOR;
        let basepoint_projective = ProjectivePoint::GENERATOR;

        assert_eq!(
            (basepoint_projective + &basepoint_projective) - &basepoint_projective,
            basepoint_projective
        );
        assert_eq!(
            (basepoint_projective + &basepoint_affine) - &basepoint_affine,
            basepoint_projective
        );
    }

    #[test]
    fn projective_double_and_sub() {
        let generator = ProjectivePoint::GENERATOR;
        assert_eq!(generator.double() - &generator, generator);
    }

    #[test]
    #[allow(clippy::cast_possible_truncation, reason = "test")]
    fn test_vector_scalar_mult() {
        let generator = ProjectivePoint::GENERATOR;

        for (k, coords) in ADD_TEST_VECTORS
            .iter()
            .enumerate()
            .map(|(k, coords)| (Scalar::from(k as u32 + 1), *coords))
            .chain(
                MUL_TEST_VECTORS
                    .iter()
                    .cloned()
                    .map(|(k, x, y)| (Scalar::from_repr(k.into()).unwrap(), (x, y))),
            )
        {
            let res = (generator * &k).to_affine();
            assert_eq!(res.x.to_bytes(), coords.0);
            assert_eq!(res.y.to_bytes(), coords.1);
        }
    }

    #[test]
    fn projective_equality() {
        use core::ops::Neg;
        assert_ne!(ProjectivePoint::GENERATOR, ProjectivePoint::IDENTITY);
        assert_ne!(ProjectivePoint::IDENTITY, ProjectivePoint::GENERATOR);
        assert_eq!(ProjectivePoint::IDENTITY, ProjectivePoint::IDENTITY);
        assert_eq!(ProjectivePoint::IDENTITY.neg(), ProjectivePoint::IDENTITY);
        assert_eq!(ProjectivePoint::GENERATOR, ProjectivePoint::GENERATOR);
        assert_ne!(ProjectivePoint::GENERATOR, ProjectivePoint::GENERATOR.neg());

        assert_ne!(ProjectivePoint::GENERATOR, AffinePoint::IDENTITY);
        assert_ne!(ProjectivePoint::IDENTITY, AffinePoint::GENERATOR);
        assert_eq!(ProjectivePoint::IDENTITY, AffinePoint::IDENTITY);
        assert_eq!(ProjectivePoint::IDENTITY.neg(), AffinePoint::IDENTITY);
        assert_eq!(ProjectivePoint::GENERATOR, AffinePoint::GENERATOR);
        assert_ne!(ProjectivePoint::GENERATOR.neg(), AffinePoint::GENERATOR);
        assert_eq!(
            ProjectivePoint::GENERATOR.neg(),
            AffinePoint::GENERATOR.neg()
        );
    }
}