TY - CHAP

T1 - Algorithms

AU - Doche, Christophe

PY - 2013/1/1

Y1 - 2013/1/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=85054653040&partnerID=8YFLogxK

U2 - 10.1201/b15006

DO - 10.1201/b15006

M3 - Chapter

AN - SCOPUS:85054653040

SN - 9781439873786

T3 - Discrete mathematics and its applications

SP - 345

EP - 404

BT - Handbook of finite fields

A2 - Mullen, Gary L.

A2 - Panario, Daniel

PB - CRC Press, Taylor & Francis Group

ER -