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.
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 |
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 |
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 |