Function ff::helpers::sqrt_ratio_generic

source ·
pub fn sqrt_ratio_generic<F: PrimeField>(num: &F, div: &F) -> (Choice, F)
Expand description

Computes:

  • $(\textsf{true}, \sqrt{\textsf{num}/\textsf{div}})$, if $\textsf{num}$ and $\textsf{div}$ are nonzero and $\textsf{num}/\textsf{div}$ is a square in the field;
  • $(\textsf{true}, 0)$, if $\textsf{num}$ is zero;
  • $(\textsf{false}, 0)$, if $\textsf{num}$ is nonzero and $\textsf{div}$ is zero;
  • $(\textsf{false}, \sqrt{G_S \cdot \textsf{num}/\textsf{div}})$, if $\textsf{num}$ and $\textsf{div}$ are nonzero and $\textsf{num}/\textsf{div}$ is a nonsquare in the field;

where $G_S$ is a non-square.

For this method, $G_S$ is currently PrimeField::ROOT_OF_UNITY, a generator of the order $2^S$ subgroup. Users of this crate should not rely on this generator being fixed; it may be changed in future crate versions to simplify the implementation of the SSWU hash-to-curve algorithm.

The choice of root from sqrt is unspecified.

§Implementing Field::sqrt_ratio

This function can be used to implement Field::sqrt_ratio for fields that also implement PrimeField. If doing so, the default implementation of Field::sqrt MUST be overridden, or else both functions will recurse in a cycle until a stack overflow occurs.