feat: bigint + bigint-based primitives

[mrdaybird]

Some algorithms require fields over huge numbers, and primitives defined over these large fields. For example, the Ed25519 digital signature algorithm uses a curve over the prime field defined by prime number $2^{255} - 19$. So, we need a way to represent large numbers and add support for it within primitives in ronkathon.

• [ ] BigInt: Represent arbitrarily large number, say >128-bit.

The structs and traits that should support BigInt:

• [ ] field module:
  • [ ] Finite
  • [ ] FiniteField
  • [ ] PrimeField
  • [ ] GaloisField
  • [ ] BinaryTowers
• [ ] group module:
  • [ ] FiniteGroup
  • [ ] MultiplicativePrimeGroup
• [ ] curve module:
  • [ ] EllipticCurve
  • [ ] AffinePoint
  • [ ] EdwardsCurve

Unresolved Questions:

1. Should these bigint-based primitives replace the existing ones or live separately in another module?
2. Are there other structs/traits that should be added to the above list?

[mrdaybird]

I am working on BigInt and PrimeField at the moment.

[Autoparallel]

@mrdaybird thoughts on:

• removing PrimeField as GaloisField<P,1> for prime P accomplishes the same thing?
• Renaming FiniteGroup to Group
• Removing Finite altogether?
• Removing MultiplicativeFiniteGroup?

I feel that we could simplify things here quite a bit. These may be unrelated to your issue as created, but perhaps it would be better to simplify prior to implementing bigint on more items?

[mrdaybird]

removing PrimeField as GaloisField<P,1> for prime P accomplishes the same thing?

You meanGaloisField<1, P>? But doesn't GaloisField use PrimeField itself?

pub struct GaloisField<const N: usize, const P: usize> {
  pub(crate) coeffs: [PrimeField<P>; N],
}

Also, one practical difference between a PrimeField and field over any non-prime number is that inverse in PrimeField can be calculated as $x^{P-2}$ otherwise we have to use the extended euclidean algorithm or some exotic inverter like safegcd

Same thing with MultiplicativePrimeGroup, it has nice inversion properties, maybe we could leave it there.

Removing finite stuff should be a good idea because computationally everything is finite.

Also, what are your thoughts on this?

Should these bigint-based primitives replace the existing ones or live separately in another module?

[mrdaybird]

@lonerapier I will appreciate your thoughts and suggestions on this as well!

[Autoparallel]

Good catch @mrdaybird, I think we should leave both GaloisField and PrimeField not only for ease, but for the inverse as you called it.

However, with proper specialization in Rust (which I'm not sure it has right now, actually), you could specialize the case of GaloisField<1, P> to have the inverse you describe and for GaloisField<N,P> where N>1 you use something else. It's worth looking into this. If we can hit this kind of specialization, then I'd prefer to consolidate. Every time I think Rust has a feature like this (even if unstable) I usually end up being disappointed 😓

[Autoparallel]

@mrdaybird still interested in this? Would love to remove crypto-bigint dependency as it is preventing updating to Rust 2024 and using newer versions of the toolchain.

Of course, no pressure. I'm also happy to assist if you want to collaborate on a PR.

[mrdaybird]

@Autoparallel sorry for the delay! Will wrap this up over the weekend.

[Autoparallel]

@mrdaybird you're a champ