Other possible sqrt-related operations

[str4d]

We removed the SqrtField trait in ff 0.7.0, as all fields that we intend the Field trait to apply to support a sqrt operation (ff_derive is able to derive implementations for p = 3 (mod 4) and p = 1 (mod 16)). More precisely, SqrtField was a separate trait because Field was previously implemented on the pairing::bls12_381::{Fq6, Fq12} extension fields of BLS12-381, which didn't have square-root operations; these are not part of the bls12_381 crate's public API.

In #6, @hdevalence had separately suggested adding several sqrt-related operations to the then-existing SqrtField trait:

pub trait SqrtField: FiniteField {
    /// Computes sqrt(u/v)
    fn sqrt_ratio(u: &Self, v: &Self) -> Self;

    /// Computes 1/sqrt(self)
    fn invsqrt(&self) -> Self {
        Self::sqrt_ratio(&Self::one(), self)
    }

    /// Computes sqrt(self)
    fn sqrt(&self) -> Self {
        Self::sqrt_ratio(self, &Self::one())
    }
}

If these would be sufficiently widely-useful, they could be added to the Field trait. If not, we could consider re-introducing the SqrtField trait.

[daira]

zcash/halo2#120 implements a generalization of sqrt_ratio based on https://ristretto.group/formulas/invsqrt.html for the Pasta curves. That implementation is more efficient than the existing Tonelli–Shanks-based one in ff, for fields that it supports (currently, those with a 2-adicity of 32, but that could easily be extended).

[str4d]

#33 adds the sqrt_ratio and sqrt_alt APIs that basically cover this issue.

[daira]

I think you mean #93.