Gas savings

In the FQ2Sqrt function of BN256G2, a square root computation in the base field ${\mathbb{F}}_p$ can be saved. If the number has no imaginary part (i.e., x2 == 0) and the number is not a square, then the second square root computation _sqrt(FIELD_MODULUS - x1) is not necessary as it will return the same value t1 as for the previous square root computation.

In ${\mathbb{F}}_p$, the square root $a$ of $x$ is computed with

$a=x^{\frac{p+1}{4}}\mathrm{mod}p$

and we have this:

$a^2=x^{\frac{p+1}{2}}=x^{\frac{p-1}{2}}x\mathrm{mod}p$

If $a$ is not a square, it means from the Legendre symbol that

$a^{\frac{p-1}{2}}=-1\mathrm{mod}p$

So in ${\mathbb{F}}_p^2$, we have this:

$(i\cdot a{)}^2=-x^{\frac{p-1}{2}}x$

And as explained before, the square root of $x$ in ${\mathbb{F}}_p^2$ is $i\cdot a$ if $a$ is not a square in ${\mathbb{F}}_p$.

Thus, the code can be replaced by the following:

// if x.b is zero
if (x2 == 0) {
    // Fp::squareRoot(t1, x.a)
    (t1, has_root) = _sqrt(x1);

    // if sqrt exists
    if (has_root) {
        return (t1, 0); // y.a = t1, y.b = 0
    } else {
        return (0, t1); // y.a = 0, y.b = t1
    }
}

It saves the gas of computing a second square root in the base field.

Another possible gas-saving measure is in ECTwistMul. There is no need to compute the scalar multiplication in case of the point at infinity; the point at infinity can be returned directly. Similarly, if the scalar is zero, there is no need to compute the multiplication.

Session team implemented the suggested changes for the square root computation in .