Add different arithmetic backends for Fp

[Pratyush]

Problem

Right now our Fp struct is a wrapper around BigInt<N>, which itself is a wrapper around [u64; N]. This has numerous undesirable effects:

• arithmetic on architectures without mul with carry/add with carry is pessimized (e.g. on wasm or riscv)
• fields whose bit size is not close to a multiple of 64 are pessimized (e.g. 192 bit fields or 32 bit fields)

Approach 1

An obvious approach to overcome this is to change BigInt<N> as follows:

/// `N` is number of 32-bit limbs.
#[cfg(feature = "u64")]
pub struct BigInt<const N: usize>([u64; N]);

/// `N` is number of 32-bit limbs
#[cfg(feature = "u32")]
pub struct BigInt<const N: usize>([u32; N]);

Unfortunately, this does not work because const generic type parameters are infectious, and must be propagated upwards. This means that we'll end up with Fp that looks like the following:

/// `N` is number of 32-bit limbs when `u32` feature flag is set
/// and is number of 64-bit limbs when `u64` feature flag is set
pub struct Fp<const N: usize>(BigInt<N>);

That is, from a user perspective Fp<N> can suddenly change from representing 64 * N bit fields to 32 * N bit fields. This is an obvious footgun

Approach 2

An alternate approach would be to change Fp as follows:

pub struct Fp<B: BigInteger>(B);

Now we don't expose the number of limbs at the Fp level; it is an implementation detail of B.

This almost works. However, we run into a new issue. The problem is that currently Fp has a number of const fns (e.g.

algebra/ff/src/fields/models/fp/montgomery_backend.rs

Line 730 in afd6188

pub const fn from_sign_and_limbs(is_positive: bool, limbs: &[u64]) -> Self {

) that rely on performing const operations on the underlying BigInt. However, because const fns in traits are unstable and experimental, we cannot call any const fn on the generic type B.

We also cannot get rid of these const fns because they enable useful functionality like the MontFp macro.

Proposed solution

We keep the const fns, but only for specific Bs. That is, we have the following impls:

impl<const N: usize> Fp<BigInt64<N>> {
    pub const fn foo(&self) {
        // logic
    }
}

impl<const N: usize> Fp<BigInt32<N>> {
    pub const fn foo(&self) {
        // logic
    }
}

This allows us to mostly have our cake and eat it too. The only downside is that if somebody implemented their own BigIntXYZ, the resulting Fp wouldn't automatically be supported by MontFp. However they can write a similar impl as above for Fp<BigIntXYZ>, and get MontFp support that way.

This approach also requires us to move some functionality into the MontDerive macros, but that's doable, and also something that the PrimeField macro in the ff crate already tackles.

Of course, this would all be obviated by availability of const fns in traits, but I've been waiting for that feature for years now, and no progress seems to be in sight.

[Pratyush]

cc @mmagician

[mmagician]

I like that.
I suggest we tackle it in stages as much as possible and start with the simple stuff. First step could be moving some of the functionality into the MontDerive macros, which is AFAICS both an independent change, and non breaking.