Closed JoeyBF closed 2 weeks ago
@hoodmane do you want more time to review this or are we good to merge?
I'm going to try to do a more detailed review.
No worries, I know it's a substantial change
One question I'm still pondering: it is better to implement arithmetic operations on the fields or the elements?
On one hand, implementing them on fields means that the elements themselves can be very lightweight, since the field will be responsible for knowing how to handle them. However, we're now required to keep a copy of the field around, and always write, say, fq.add(a,b)
instead of just a + b
. On the other hand, implementing the operations on elements requires them to keep track of their field, but is much better for ergonomics.
I'm thinking the second approach is better. It solves the problem of ergonomics, which will make it simpler to just treat elements as things that we can manipulate algebraically. It will require us to use something like FpElement
instead of u32
for Fp::Element
, which might require some significant changes to the code, that will also allow us to ensure that an element is reduced mod p at the type level.
It might seem drastic to keep a copy of the field for every single element, but P2
, P3
, P5
, and P7
are all ZSTs, and Fp<P>
is just a thin wrapper, so there's no memory overhead for those primes. If odd-primes
is disabled, even ValidPrime
is a ZST. At larger primes, I think it's reasonable to take the hit on memory usage, since we're not as worried about performance as for the smaller primes.
I agree it's nice to be able to write a + b
. If I understand correctly you're thinking of something like:
FieldElement<FieldType> {
field: FieldType
data: FieldType::ElementData
}
And then your point is for most of the fields we are calculating, field
is zero sized so there's no overhead just a compile-time tag. For the fields that aren't zero-sized it doubles the amount of stuff we carry around, but they are already slow anyways?
Yeah that's the idea. Basically tagging every element with its field. So SmallFq::Element
would still be SmallFqElement
, but the latter would go from just being a bare Option<u32>
to
struct SmallFqElement<P> {
field: SmallFq<P>,
data: Option<u32>,
}
which would double the memory usage. That would also mean that we would change Fp::Element
from u32
to some struct FpElement
with the shape
struct FpElement<P> {
field: Fp<P>,
data: u32
}
but as you say the extra field
attribute would be zero-sized in the cases where we care most about performance.
I'm not sure if we want to change our FpVector
API to take in FpElement
s and have the caller handle the scalars, or just convert from u32
s internally. I'll have to start implementing the changes and see what works best.
Closing in favor of #159
This adds support for prime-power fields of order
<2^16
. We construct the multiplication table for the fieldF_(p^d)
by identifying it withF_p[a]/P
, whereP
is the appropriate Conway polynomial. Since there aren't that many fields of that order that aren't prime, I just hardcoded the Conway polynomials in a separate file.The
FqVectorP
struct (previouslyFpVectorP
) takes in a generic field instead of a prime, and all the managing of the internals of a limb is delegated to the underlying field.Note that right now we only have a monomorphized
FpVector
, where the field is prime. This allows us to useu32
s in our API. I suspect that the better move would be to have a dedicatedFpElement
struct that would be a wrapper around au32
, but would ensure that it belongs in the right range at compile time. I have started experimenting with this, but it gets really unwieldy to constantly create field elements instead of just passing regular numbers (in thealgebra
crate for example).Implementing larger fields would not be impossible, but it would require more mucking around with Conway polynomials (that are only known for finitely many
q
s), and switching to a different representation for storing field elements and multiplication tables.