Algorithms

Christophe Doche*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

Abstract

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

Original languageEnglish
Title of host publicationHandbook of finite fields
EditorsGary L. Mullen, Daniel Panario
PublisherCRC Press, Taylor & Francis Group
Chapter11
Pages345-404
Number of pages60
ISBN (Electronic)9781439873823
ISBN (Print)9781439873786
DOIs
Publication statusPublished - 1 Jan 2013

Publication series

NameDiscrete mathematics and its applications
PublisherCRC Press

Fingerprint Dive into the research topics of 'Algorithms'. Together they form a unique fingerprint.

Cite this