Benchmark suite

[fredrik-johansson]

Currently we have a lot of isolated profiling and example programs, but no automatic way to aggregate performance benchmarks. A unified benchmark suite would be useful to catch performance regressions (and track improvements)! Key functionality to cover:

• Integer primality testing and factoring
• Univariate polynomial arithmetic, GCD, factoring
• Multivariate polynomial arithmetic, GCD, factoring
• Linear algebra (determinants, solving, eigenvalues)
• Algebraic numbers
• Special functions

@thofma Do you have some good problems that we could use?

@defeo Do you have some good benchmark problems for FLINT's finite fields and their embeddings? I don't know enough about the applications to tell what kind of parameters would be interesting to profile for.

[thofma]

I don't have them lying around sorry. Maybe @fieker has some?

[defeo]

Hmmm... GF(p¹²) with

p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab

might just be the most popular field extension in crypto. I don't have code for it, though.

I think @yyyyx4 was battling with finite field extensions recently to implement the SIDH attacks?

[yyyyx4]

Indeed, some interesting finite fields would be the extension fields of degrees $qf$ listed on page 15 of A Direct Key Recovery Attack on SIDH. In all cases discussed there, the base field is $\mathbb F{p^2}$ with $p = 2^{110}\cdot3^{67}-1$. The list contains both small and large degrees, so it should be feasible to extract a subset of useful benchmarking targets. Of course, small characteristics are uninteresting in the attack context.

[fredrik-johansson]

First version added in #1702 but needs more work.