search

amiller / viff

Clone of http://viff.dk/
GNU General Public License v3.0
2 stars 2 forks source link

Add a "polynomials" library #2

Open amiller opened 6 years ago

amiller commented 6 years ago

The Viff codebase already has a nice python abstraction for finite fields (viff/field.py) and for matrices over finite fields. Polynomials over finite fields are also generally useful. These are already implicit in secret sharing (e.g., lagrange interpolation) in (viff/shamir.py). To extend Viff to other features, and as a starting point to implement Reed Solomon decoding #1 it would be helpful to have an implementation of polynomials. The main interesting operation is long-division of polynomials.

A good reference is Jeremy Kun's primer on programming with polynomials https://jeremykun.com/2014/03/13/programming-with-finite-fields/

In particular the polynomial.py could probably be adapted to work with Viff's existing field.py abstraction with minimal modifications. Viff's finite fields are wrappers around the gmp library, unlike those that come with Jeremy Kun's primer.

amiller commented 6 years ago

We should at least have the ability to do FFT based interpolation, as long as the order of the finite field we're working in has a large power of 2 as a factor (BLS12-381 is an example).