search

zkcrypto / ff

Traits and utilities for working with finite fields.
Apache License 2.0
236 stars 101 forks source link

ff_derive fails with no sqrt for p = 5 (mod 8) and p = 9 (mod 16) #84

Open bgillesp opened 2 years ago

bgillesp commented 2 years ago

The ff_derive derived PrimeField implementation fails to derive a sqrt function for primes p = 5 (mod 8) and p = 9 (mod 16), resulting in a compile-time error for these cases. According to the introduction of IACR Preprint 2012/685 (the cited reference for the algorithms used for the p = 3 (mod 4) and p = 1 (mod 16) cases), efficient algorithms do exist for computing square roots over these primes; however, these algorithms are not currently implemented here.

In Issue #33, this limitation is noted explicitly, so it may be that the desired use cases for this library don't require full coverage of odd primes. I just wanted to check whether this is an intentional omission for maintainability, or if it's simply a feature that hasn't been added yet. If it's the latter and maintainers are interested, I might be able to assemble a pull request.

str4d commented 1 year ago

This is just a feature no one has requested before. If someone wants to provide square root helpers for the uncovered cases, I'd be happy to review a PR. #93 adds helper methods for Tonelli-Shanks and for a generic sqrt_ratio; we could also have similar helper methods for other primes, and then use them in ff_derive.

daira commented 1 year ago

Tonelli–Shanks works for these primes, so why don't we just use that? The performance loss is relatively small I think.