arkworks-rs / algebra

Libraries for finite field, elliptic curve, and polynomial arithmetic
https://arkworks.rs
Apache License 2.0
601 stars 235 forks source link

GF(2^128) operations #847

Open sjsonucool opened 1 month ago

sjsonucool commented 1 month ago

I just began using Rust programming language, so I apologize in advance in case my queries are too simple or not clearly specified. I need to use operations over extension field GF(2^128) to implement Lagrange interpolation. I see that ark_ff has models for Quadratic Extension fields and I was wondering if I can get some examples on how to initialize GF(2^128) and call the operations performing add, multiply and inverse over this extension field? I would appreciate any help/inputs towards resolving the issue.

burdges commented 1 month ago

Afaik, binary fields need many custom optimizations, both in the field itself and in the algorithms that use them. See https://github.com/AndersTrier/reed-solomon-simd or Binus [DP] SNARK, which both depend upon the exact tower of extensions fields used.

As one simple example, an FFT might've preparation phase for scalar scalar multiplications using log tables, which then even breaks applying arkworks-like traits to binary fields. It's possible later optimizations make that trick irrelevant, but overall this sound messy.