Nist P256: How to calculate Y public key when knowing X and the LSB bit of Y public key

[NIIBE Yutaka]

Yann Garcia <garcia.yann at gmail.com> wrote:
> My problem is to calculate Y based on previous information.

This page helps:
https://en.wikipedia.org/wiki/Quadratic_residue

> My concerns now is how to get the two possible values of y? In other words,
> how can I calculate sqrt(y^2).

If it exists, according to the page above, when p_plus_1_div_4 has
(p+1)/4, you can calculate it by

	gcry_mpi_powm (y, y_2, p_plus_1_div_4, p)

You can see if it exists or not by Euler's criterion:

   gcry_mpi_powm (eulers_criterion, y_2, p_minus_1_div_2, p)

Here, p_minus_1_div_2 should have (p-1)/2.

When eulers_criterion is 1, it does exist.
When eulers_criterion is p-1 (-1 mod p), it doesn't exist.
--