Algorithms

This section presents algorithmic methods for finite fields. It deals with concrete implementations and describes how some fundamental operations on the elements are performed. and dom number generation, where the speed of the computations is paramount. Therefore we discuss algorithms with a particular attention to efficiency and we address implementation techniques and complexity aspects as often as possible. In many instances, the complexity of the algorithms that we describe depends on the field multiplication method that is implemented. In the following, M(log p) denotes the complexity to multiply two positive integers less than p. Similarly, Mq(n) represents the complexity to multiply two polynomials in Fq[x] of degree less than n. We note that many software tools or libraries implement some of the algorithms that are presented next. A non-exhaustive list includes Magma [2798], Pari [209], Sage [2709], Mathematica [3004], Maple [2002], NTL [2633], GMP [1102], MPFQ [1255], FLINT [1426], and ZEN [576]. Detailed algorithms and complexity analyses can be found in [660, 661, 751, 1227, 1413, 1768, 2080, 2632].