Square root trait and implementation cleanups

[andrewwhitehead]

Some potential cleanups for the traits and implementation:

• Add a CheckedSquareRoot trait which could be implemented by Int (returning none for negative inputs). This could be a supertrait of SquareRoot.
• Rename the SquareRoot trait for clarity, perhaps UintSquareRoot or FloorSquareRoot.
• [ ] Implement the square root trait(s) for Montgomery forms (this makes FloorSquareRoot a less desirable name).
• Rename Uint::sqrt/sqrt_vartime to isqrt or sqrt_unchecked to reflect the inexact nature of the result (and corresponding trait updates to match).
• Implement square root traits and methods for OddUint for consistency. This would require changing the return type, but it seems reasonable to add an Output type to the trait(s).
• Support nth roots based on algorithm 1.14 from the same source (Brent & Zimmermann, Modern Computer Arithmetic, v0.5.9). Should this be a separate trait?

[andrewwhitehead]

I think it makes sense to make CheckedSquareRoot the primary trait (as in #1083). The other option here would be to maintain SquareRoot but make the result fallible. Montgomery forms could implement this, although the method is also provided by ff::Field.

Uint could implement a FloorSquareRoot trait (my current preferred naming) with floor_sqrt, floor_sqrt_vartime methods. It doesn't seem like Montgomery forms have a need for a method that doesn't return an Option/CtOption. IntegerSquareRoot with isqrt/isqrt_vartime would be an option somewhat aligned with the standard library, but it seems less precise (implies the result could be negative? and doesn't specify the rounding).

I have a vartime implementation of the nth root calculation. It's a bit unclear how to implement that in constant time because a) does it need to be constant time in the exponent? and b) we don't know the number of rounds to perform, although I think it might be the same.