##
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 x^{n} + 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(3^{k})

We factor the polynomial x^{n} + x + w over K=GF(3^{k})
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
x^{n} + 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(2^{1000})

We multiply two random polynomials of increasing degree n over
GF(2^{1000}). 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 |