[RFC] Being generic over a modulo instead of a size

[elichai]

If we think from an algebraic eyes, it would be very nice to enforce typing over F_q for some q, meaning that the type will be FieldElement<q>, then q can be use to choose the size of the underlying array and generate arithmetic that work on that field specifically (and then using specialization we could provide efficient implementation for common fields).

This allows you to easily separate variables from different fields and makes field conversions very explicit and obvious, which should increase resilience in complex algorithms that do convert between fields (ie in a MPC protocol where you use Paillier encryption over a field element in an EC group, when you convert between the fields you'll realize you probably need to attach some range proof and dlog proof).

Would love to hear any thoughts on this :)

[newpavlov]

I think that we should build such types on top of "simple" bigints as wrappers. But, unfortunately, we probably will be blocked on insufficient power of const generics for the near future.

[tarcieri]

Yes, it'd be great if we could make the modulus a const generic parameter, unfortunately you can only use const N: usize on stable

[elichai]

Even on nightly, I tried using a string to represent the moduli and very fast gotten into a compiler bug: rust-lang/rust#90455

But maybe being generic over a constant Uint could work in the future, having a const generic that is generic over a const generic seem currently impossible even in nightly (struct FieldElement<const N: usize, const P: Uint<{N}>>)

[tarcieri]

I think we can close this as being implemented by what the latest prereleases call ConstMontyForm:

https://docs.rs/crypto-bigint/0.6.0-pre.12/crypto_bigint/modular/struct.ConstMontyForm.html

Though it doesn't use adt_const_params to be const generic around a modulus, it supports an impl_modulus! macro which defines a set of ConstMontyParams at compile time, and the ConstMontyForm type is generic around a modulus specified by those params.

So it's still a type-safe way of expressing field elements whose modulus is known at compile time.