Optimised `sqrt` variants

[mmagician]

Currently there are three sqrt algorithms implemented in arkworks:

For even extension fields:

• Complex method (alg. 8) from https://eprint.iacr.org/2012/685.pdf

For odd extension fields:

• Tonelli-Shanks which works for all fieds no matter the modulus
• Specialized Shanks algorithm for case where modulus is 3 mod 4

To be still implemented are the remaining specialized algorithms for odd extension fields. See Figure 1 here for the algorithm taxonomy.

Odd extension fields:

• 1 mod 16 (Tonelli Shanks)
• 3 mod 4 (Shanks)
• 9 mod 16
• 5 mod 8

Also linking an issue for fields with high 2-adicity: #40, which might require some refactoring to incorporate addition chains.

Preliminary work was done here.

[Pratyush]

@alexander-zw is thinking of working on this, I believe.

[alexander-zw]

Tasks:

1. Port Joseph's PR to master
2. Write general unit tests using small simple fields
3. Update test-curves to use faster algorithms (need to use Sage script), and benchmark compare Tonelli with new ones and with power algorithm
4. Check for other algorithms from the paper that weren't in Joseph's PR
5. Use macro to precompute instead of requiring Sage script & hardcode