Further coverage of UintLike

[xuganyu96]

This PR is a continuation of #36 (and thus is a halfway point to #34), though it is still WIP.

36 in its current state will not compile. There are many unimplemented!(). Some of the API's from crypto-bigint has also changed.

This PR improves on #36 by:

• [x] Completing the implementation of jacobi_small and gcd_small, which includes transitioning hazmat::jacobi and hazmat::gcd to be implemented using <T: UintLike> instead of Uint<L>
• [x] Implement random_bits correctly
• [x] Try implement UintLike for BoxedUint
• [x] Write test cases and bench marks for prime generation using BoxedUint

As of ba9d3c5633020e7b50e5569e6ddb8e831fbd3d2c the crate will compile, but not all tests will pass:

[xuganyu96]

Now all tests pass.

[tarcieri]

Related: https://github.com/RustCrypto/crypto-bigint/pull/425

[xuganyu96]

I made an attempt to implement UintLike for BoxedUint and UintModLike for BoxedResidue. There are a few missing implementations that will need to be merged into RustCrypto/crypto-bigint

• [x] BoxedUint::bit_vartime (trivial implementation)
• [x] BoxedUint::trailing_ones (trivial implementation)
• [x] BoxedUint::sqrt_vartime, which is non-trivial
  • [x] Needs cmp_vartime?
  • [x] Needs wrapping_div_vartime?
  • [x] Needs is_nonzero?
• [x] BoxedUint::shr_vartime, which is already implemented, but behaves differently from Uint::shr_vartime
• [x] BoxedUint::shl_vartime, same as BoxedUint::shr_vartime
• [x] BoxedUint::div_rem_limb_with_reciprocal and BoxedUint::div_rem_limb
  • [x] both makes call to div_rem_limb_with_reciprocal
  • [x] div_rem_limb_with_reciprocal makes call to shl_limb
  • [x] div2by1 can be reused from src/uint/div_limb.rs
  • [x] BoxedUint needs to be instantiated from an array of Limb
• [x] BoxedResidue::div_by_2

[xuganyu96]

There seems to be a bug with BoxedResidue::square (see https://github.com/RustCrypto/crypto-bigint/issues/441). This can be temporarily side-stepped by calling retrieving and re-instantiating the BoxedResidue, although it is certainly not the ideal solution.

At least for now, it is possible to run generate_prime and generate_safe_prime with BoxedUint. Two simple tests have been added to presets.rs to demonstrate the progress.

[xuganyu96]

@fjarri @tarcieri Missing arithmetic operations for BoxedUint have been implemented: https://github.com/RustCrypto/crypto-bigint/pull/436. Prime generation for BoxedUint is tested in presets.rs.

There are a two awkward API's. T::one() and T:zero() both need to be replaced with T::one_with_precision() and T::zero_with_precision, which is a bit weird for stack-allocated Uint; also, many T::from(u32) must be immediately followed by a widen(bits_precision), which is also weird for stack-allocated Uint.

Also, the main public API generate_prime and generate_safe_prime need to accommodate the new argument bits_precision. I think with some clear explanation in the documentation, the user should be able to understand, but maybe we can do better. I am open to ideas (maybe we can make generate_prime into a macro?)

Thank you!

[xuganyu96]

Closing this PR to consolidate work on #36