Implement faster square-roots for prime fields that have high two-adicity

[Pratyush]

See https://eprint.iacr.org/2020/1407

[Pratyush]

cc @kobigurk

[ValarDragon]

One question before implementing this is how should we be handling precomputation results for Square root algorithms. Different square root algorithms will need different precomputations

[Pratyush]

Does this new algorithm need precomputation? For the time being we can keep it simple, because the existing square-root algorithm doesn't require precomputation

[ValarDragon]

The table methods with better efficiency do. The minimal-precomputation one in that paper precomputes log(n) powers of g, which is fine to just compute on the fly as a first impl

[ValarDragon]

@daira has a really helpful sage prototype for this square root algorithm (with the table optimizations) for the pasta curves!

• sqrt: https://github.com/zcash/pasta/blob/master/squareroottab.sage
• addition chain: https://github.com/zcash/pasta/blob/master/addchain_sqrt.py

This will probably be a very helpful reference when going to implement it here

[daira]

The table-based variant does need precomputation, yes.

[daira]

The current square root implementation (https://github.com/arkworks-rs/algebra/blob/master/ff/src/fields/arithmetic.rs#L225-L280) could be improved in two ways that are orthogonal to the improvements in the new algorithm:

• The powering by (m-1)/2 can be done using a field-specific addition chain. I suggest adding a trait with a default implementation that fields can override.
• It's inefficient to compute the Legendre symbol separately in order to tell whether the input is square. Instead compute a potential square root using a "garbage-in, garbage-out" algorithm (Tonelli–Shanks or the new algorithm will both work for this) and then if the square of that result is not the input, then the input was not a square.