Avoid computing square roots where possible in hash_to_curve

[huitseeker]

The (S)SWU hash_to_curve methods (RFC), introduced in #47 for grumpkin (see also #70 for secp256k1), simply require finding if an element is a quadratic residue in several places in the computation.

This is currently implemented as foo.sqrt().is_some(), which resolves to a square root computation.

I suspect it may be faster to implement a real Legendre symbol there, see e.g. Arkworks:
https://github.com/arkworks-rs/algebra/blob/13fd33e33c1186b2757e3fd3948b6eee16ee9e4b/ff/src/fields/mod.rs#L256-L260

[mratsim]

For (S)SWU methods you can fuse square root, legendre symbol and sqrt(u/v).

For SVDW method you can optimize the 2 legendre symbols + 3 sqrt in the specs to

• either 2 legendre and 1 sqrt
• or 3 fused legendre+sqrt

https://github.com/mratsim/constantine/pull/190/files#diff-5f77dfe5a8625615eb2e4e4d504159b5daa4841864de9161cab1da73e68cb2ebR80-R85

You can accelerate Legendre symbol about 7x using either Pornin or Bernstein-Yang GCD as described here: mratsim/constantine#199

We have a Bernstein-Yang inversion currently being developed for Halo2 which is 8.5x faster than the current implementation (taikoxyz#2)