Feature wishlist tracking ticket

This is a ticket for tracking desired new features for crypto-bigint and which algorithms should be used in order to implement particular features.

Unless otherwise stated, these features are implied to be for the UInt type.

• signed integers (#700)
• addition/subtraction
• multiplication algorithms
  • "schoolbook"
  • Karatsuba
• sqrt
• modular arithmetic
  • add
  • subtract
  • multiply
  • negate
  • modulus
  • pow
  • sqrt
  • inversions
• bitwise operations (request other ops in comments)
  • shift
  • rotate
  • XOR
• fields mod n (i.e. wrapper newtypes for UInt)
• constant-time division
  • by 2 (useful for elliptic-curve crates)
  • arbitrary
• subtle comparisons
  • ConstantTimeEq
  • ConstantTimeGreater
  • ConstantTimeLess
• CRT (algorithms listed below)
  • Smooth RSA-CRT
  • https://eprint.iacr.org/2020/1507 (note: appears to be covered by patents)
• LCM
• GCD (algorithms listed below)
  • safegcd (a.k.a. Bernstein-Yang)
  • safegcd-bounds (#634)
• RNG
  • random < n
  • better random < n
  • random prime (use crypto-primes instead)
• Hardware acceleration / assembly (see also #572)
  • x86/x86_64
    • ADX
    • MULX
    • AVX2
  • ARM
    • NEON

NOTE: for prime number support, see the crypto-primes crate

This is a tracking ticket rather than a single implementation task, and it names no source files or tests. Start by reviewing the unchecked items and their linked algorithm references or related issues. Work is done only after one specific feature is selected, scoped, implemented, and covered by the project’s tests.