-
Notifications
You must be signed in to change notification settings - Fork 223
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Add different arithmetic backends for Fp
#769
Comments
cc @mmagician |
I like that. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Problem
Right now our
Fp
struct is a wrapper aroundBigInt<N>
, which itself is a wrapper around[u64; N]
. This has numerous undesirable effects:Approach 1
An obvious approach to overcome this is to change
BigInt<N>
as follows: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:That is, from a user perspective
Fp<N>
can suddenly change from representing64 * N
bit fields to32 * N
bit fields. This is an obvious footgunApproach 2
An alternate approach would be to change
Fp
as follows:Now we don't expose the number of limbs at the
Fp
level; it is an implementation detail ofB
.This almost works. However, we run into a new issue. The problem is that currently
Fp
has a number ofconst fn
s (e.g.algebra/ff/src/fields/models/fp/montgomery_backend.rs
Line 730 in afd6188
const
operations on the underlyingBigInt
. However, becauseconst fn
s in traits are unstable and experimental, we cannot call anyconst fn
on the generic typeB
.We also cannot get rid of these
const fn
s because they enable useful functionality like the MontFp macro.Proposed solution
We keep the
const fn
s, but only for specificB
s. That is, we have the following impls:This allows us to mostly have our cake and eat it too. The only downside is that if somebody implemented their own
BigIntXYZ
, the resultingFp
wouldn't automatically be supported byMontFp
. However they can write a similarimpl
as above forFp<BigIntXYZ>
, and getMontFp
support that way.This approach also requires us to move some functionality into the
MontDerive
macros, but that's doable, and also something that thePrimeField
macro in theff
crate already tackles.Of course, this would all be obviated by availability of
const fn
s in traits, but I've been waiting for that feature for years now, and no progress seems to be in sight.The text was updated successfully, but these errors were encountered: