Magma V2.14 Finite Field Computations Timings

Allan Steel (October 2007)


Magma V2.14 (released in October 2007) has many improvements for computations with finite fields and polynomials over finite fields. The following tables show a comparison with the previous release V2.13.

All timings are for an 2.8GHz Opteron processor running Fedora Core 6 Linux. I will expand this as I get time.


Factoring very sparse polynomials over GF(2)

We factor the polynomial xn + x + 1 over GF(2) for various values of n.

 n   #Factors   V2.13   V2.14   Speedup 
10000 8 0.4 0.1 4.0
20000 8 2.1 0.3 7.0
50000 10 14.9 1.0 14.9
100000 14 162.1 3.8 42.7
150000 12 388.9 9.2 42.3
200000 14 699.2 20.0 35.0


Factoring very sparse polynomials over GF(3k)

We factor the polynomial xn + x + w over K=GF(3k) for various values of k and n, where w is the default generator of K. We use w as the constant to force computations over K proper, since xn + x + 1 is comparatively trivial to factor over such fields. Prime values of k are chosen, since these are the hardest extension fields to work with (there is no subfield to be taken advantage of).

 k   n   #Factors   V2.13   V2.14   Speedup 
103 100 7 9.5 1.0 9.5
103 200 3 35.7 4.9 7.3
211 100 3 35.2 3.3 10.7
211 200 9 126.1 15.5 8.1
1009 10 2 30.5 1.5 20.3
1009 20 3 103.6 5.3 19.6
1009 50 2 386.9 23.8 16.3


Multiplying polynomials over GF(21000)

We multiply two random polynomials of increasing degree n over GF(21000). Since V2.14 uses the Cantor algorithm, the timings for it do not grow smoothly.

 n   V2.13   V2.14   Speedup 
1000 2.0 0.14 14.3
2000 5.0 0.27 18.5
5000 17.1 1.2 14.2
10000 38.0 2.5 15.2
15000 44.8 2.6 17.2
20000 63.1 5.5 11.4
30000 106.55 5.6 19.0