search

mhostetter / galois

A performant NumPy extension for Galois fields and their applications
https://mhostetter.github.io/galois/
MIT License
337 stars 31 forks source link

Cool Library! Looking forward to NTT support #183

Closed brianretford closed 2 years ago

brianretford commented 3 years ago

Feel free to close, just wanted to say this library is cool and almost exactly what I was looking for - we might be interested in adding NTT support if you're not actively working on it

mhostetter commented 3 years ago

@brianretford thanks for the feedback!

I have some NTT stuff that I could push up (probably this weekend). Maybe you could provide a test / review / improvement. I don't personally have an application for the NTT, so it's new to me. I'm an electrical engineer by trade, so I'm still learning some number theory concepts for this project. I'll post back here when I push up the code.

Also, as you use the library, if you could report back on any documentation, API, or feature improvements you find. I'm looking for user feedback as I push toward the first 0.1.0 beta release. Thanks!

brianretford commented 3 years ago

Cool! Yeah NTTs are useful to create polynomials from a set of points (interpolation) - has applications in homomorphic encryption and zero-knowledge proofs - I'll send you a link to the notebook we're making when it's done.

Will do - the docs are great for such a new library, really much better than the docs for anything I've ever made.

mhostetter commented 3 years ago

@brianretford in #184 I added initial NTT/INTT support. It is now merged onto master but not yet on PyPI. You can update your version of galois with

$ pip3 uninstall galois
$ pip3 install git+https://github.com/mhostetter/galois.git

I would appreciate any feedback you have, especially regarding the API. Since I don't have many personal use cases, it's hard to know if the API is convenient for users. The documentation can be found here: https://galois.readthedocs.io/en/latest/api/transforms.html.

Also, note the current implementation is the naive O(N^2) implementation. I compute the prime modulus p, find a primitive N-th root of unity in GF(p), construct the Vandermonde matrix V with that primitive root, and then compute the transform with X = V @ x, which all use this library's vectorized "Galois field arrays". I did this because it was faster to "get out" and tested. It is possible to add the radix-2 Cooley-Tukey algorithm for N = 2^k, which would achieve O(N*log(N)). I would probably need to make a separate Numba function to do this.

And, certainly, if you find any issues / errors please let me know.

mhostetter commented 3 years ago

@brianretford have any thoughts or feedback?

mhostetter commented 2 years ago

I'm closing now due to inactivity. Feel free to re-open with more comments / thoughts, or open additional issues if bugs are found or features requested.

mhostetter commented 2 years ago

@brianretford I'm not sure if you're still interested or still have an application for it, but I just added (#333) the radix-2 Cooley-Tukey FFT to the NTT implementation. It now has O(n*log(n)) complexity instead of O(n^2). It will be released in the next version, v0.0.27, but is available now on master.

Any other feedback (good or bad) or feature requests are always welcome.

brianretford commented 2 years ago

Thanks! Actually just hired someone to work on the educational materials I was looking at (a lot has happened since then...) @pdg744

Also we open-sourced our project – it’s a Zero-knowledge RISC-V virtual machine – https://github.com/risc0/risc0