Add benchmarks.

[afck]

Our implementation still uses naive and probably slow algorithms in several places, especially for polynomials and commitments, and we should look into optimizing them. Whether #13 leads anywhere or not, the first step is adding benchmarks. I'm mainly thinking of polynomial multiplication and interpolation, but the more we cover, the better.

[fhaynes]

Hey everyone!
I started looking through the code. Looks like the remaining operations on polynomials could use benchmarks, with the exception of multiplication. I think those should be quite simple.

Beyond that, it looks like the BivarPoly trait could be benchmarked without much trouble. I'll have to read a bit more to see how to properly benchmark commitments.

Sound good? The crypto domain is a bit outside my normal Rust work, so if I suggest/say something ridiculous, please tell me. =)

[c0gent]

Sounds good :)

[fhaynes]

Link to PR: #33
Ping me over there if changes are needed, assuming this ever finishes compiling...

[afck]

Hi @fhaynes, thank you for taking on this issue!

Having benchmarks for addition and subtraction certainly makes sense. However, I don't think they have much room for optimization since they don't involve any complicated computations. I think the main bottlenecks at the moment are the two methods that involve the (not yet optimized) single-value polynomial interpolation function: PublicKeySet::combine_signature and PublicKeySet::decrypt.

(And maybe there are other CPU intensive methods left unbenched, too, but I currently can't think of any.)

[fhaynes]

Sure. PR here: #35

[ErichDonGubler]

Since the (rebased) PR was merged by @afck, should this issue be closed?

[afck]

Yes, thank you for the reminder!