Succinct prime field representation for small `p`

[konn]

Currently, a prime field F p is represented by Integer; but we can use Int instead for small enough prime ps. This branch implements a type-level hack to allow such a conditional representation choice.

[konn]

TODO: benchmarking

[konn]

After some optimisation, we get to the point that the simple benchmark outperforms the old implementation; it is almost twice as fast!

Tables (mean-time)

Precise data is available at bench-results/prime-field-simple. Bold figure is faster.

Simple "the reciprocal of half the characteristic" benchmarks

Field	Integer	Succinct	Note
𝔽2	238.5 ns	154.3 ns
𝔽5	441.3 ns	333.5 ns
𝔽59	446.8 ns	338.7 ns
𝔽12379	459.4 ns	336.0 ns
𝔽3037000507	453.2 ns	478.1 ns	big prime; for a comparison for performance regression

Product of units: 1 * 2 * ... * (p - 1)

Note: Logarithmic Graph.

Field	Integer	Succinct
𝔽2	34.56 ns	11.45 ns
𝔽5	123.7 ns	52.13 ns
𝔽59	1.908 μs	706.9 ns
𝔽12379	407.4 μs	154.1 μs

The sum of prefix-products of units: 1 + 1*2 + 1*2*3 + ... + 1*2*...*(p - 1)

Note: Logarithmic Graph.

Field	Integer	Succinct
𝔽2	60.09 ns	8.827 ns
𝔽5	405.8 ns	144.0 ns
𝔽59	56.48 μs	19.74 μs
𝔽6197	1.024 s	602.3 ms

[konn]

Summary of simple factorisation benchmarks

It seems that the new implementation of prime fields has performance degression when factoring polynomials of characteristic 2. The only difference between char 2 and odd seems the calculation of trace polynomial modulo a principal ideal. It indicates that some operations used in the computation are not fully optimised.

Factorising irreducible polynomials

Factoring a product of polynomials of degree one

Factoring randomly generated polynomial (seed fixed)