Algorithms for Finite Field Arithmetic
Author: 
Eric SchostAuthors Info & Claims
Abstract
We review several algorithms to construct finite fields and perform operations such as field embedding. Following previous work by notably Shoup, de Smit and Lenstra or Couveignes and Lercier, as well as results obtained with De Feo and Doliskani, we distinguish between algorithms that build "towers" of finite fields, with degrees of the form l, l2, l3,... and algorithms for composita. We show in particular how techniques that originate from algorithms for computing with triangular sets can be useful in such a context.
References
[1]
L. M. Adleman and H. W. Lenstra. Finding irreducible polynomials over finite fields. In STOC'86, pages 350--355, New York, NY, USA, 1986. ACM.
[2]
P. Aubry, D. Lazard, and M. Moreno Maza. On the theories of triangular sets. J. Symb. Comput., 28(1,2):45--124, 1999.
[3]
I. F. Blake, G. Seroussi, and N. P. Smart. Elliptic curves in cryptography. Cambridge University Press, New York, NY, USA, 1999.
[4]
W. Bosma, J. Cannon, and A. Steel. Lattices of compatibly embedded finite fields. J. Symb. Comput., 24(3-4):351--369, 1997.
[5]
A. Bostan, M. F. I. Chowdhury, J. van der Hoeven, and É. Schost. Homotopy techniques for multiplication modulo triangular sets. J. Symb. Comput., 46(12):1378--1402, 2011.
[6]
A. Bostan, P. Flajolet, B. Salvy, and É. Schost. Fast computation of special resultants. J. Symb. Comput., 41(1):1--29, 2006.
[7]
A. Bostan, L. González-Vega, H. Perdry, and É. Schost. From Newton sums to coefficients: complexity issues in characteristic p. In MEGA'05, 2005.
[8]
A. Bostan, G. Lecerf, and É. Schost. Tellegen's principle into practice. In ISSAC'03, pages 37--44. ACM, 2003.
[9]
J. V. Brawley and L. Carlitz. Irreducibles and the composed product for polynomials over a finite field. Discrete Math., 65(2):115--139, 1987.
[10]
R. P. Brent and H.-T. Kung. Fast algorithms for manipulating formal power series. Journal of the ACM, 25(4):581--595, 1978.
[11]
D. G. Cantor. On arithmetical algorithms over finite fields. J. Combin. Theory Ser. A, 50(2):285--300, 1989.
[12]
D. V. Chudnovsky and G. V. Chudnovsky. Computational problems in arithmetic of linear differential equations. Some Diophantine applications. In Number theory (New York, 1985/1988), volume 1383 of Lecture Notes in Math., pages 12--49. Springer, Berlin, 1989.
[13]
J.-M. Couveignes. Computing $\ell$-isogenies using the p-torsion. In ANTS-II, pages 59--65, London, UK, 1996. Springer-Verlag.
[14]
J.-M. Couveignes. Isomorphisms between Artin-Schreier towers. Math. Comp., 69(232):1625--1631, 2000.
[15]
J.-M. Couveignes and R. Lercier. Fast construction of irreducible polynomials over finite fields. Israel J. Math., 194(1):77--105, 2013.
[16]
L. De Feo, J. Doliskani, and É. Schost. Fast algorithms for l-adic towers over finite fields. In ISSAC'13, pages 165--172. ACM, 2013.
[17]
L. De Feo, J. Doliskani, and É. Schost. Fast arithmetic for the algebraic closure of finite fields. In ISSAC '14, pages 122--129. ACM, 2014.
[18]
L. De Feo and É. Schost. Fast arithmetics in Artin-Schreier towers over finite fields. J. Symb. Comput., 47(7):771--792, 2012.
[19]
L. De Feo. Fast algorithms for computing isogenies between ordinary elliptic curves in small characteristic. Journal of Number Theory, 131(5):873--893, May 2011.
[20]
B. de Smit and H. W. Lenstra. Standard models for finite fields: the definition, 2008.
[21]
B. de Smit and H. W. Lenstra. Standard models of finite fields. In G. Mullen and D. Panario, editors, Handbook of Finite Fields. CRC Press, 2013.
[22]
J. Doliskani and É. Schost. Computing in degree 2k-extensions of finite fields of odd characteristic. Des. Codes Cryptogr., to appear.
[23]
J. von zur Gathen. Irreducible polynomials over finite fields. In Foundations of Software Technology and Theoretical Computer Science, volume 241 of Lecture Notes in Computer Science, pages 252--262. Springer Berlin Heidelberg, 1986.
[24]
J. von zur Gathen and V. Shoup. Computing Frobenius maps and factoring polynomials. Comput. Complexity, 2:187--224, 1992.
[25]
P. Gaudry and É. Schost. Point-counting in genus 2 over prime fields. J. Symb. Comput., 47(4):368--400, 2012.
[26]
X. Huang and V. Y. Pan. Fast rectangular matrix multiplication and applications. Journal of Complexity, 14(2):257--299, 1998.
[27]
M. Kalkbrener. A generalized Euclidean algorithm for computing triangular representations of algebraic varieties. J. Symb. Comput., 15:143--167, 1993.
[28]
E. Kaltofen and V. Shoup. Subquadratic-time factoring of polynomials over finite fields. Math. Comp., 67(223):1179--1197, 1998.
[29]
E. Kaltofen and V. Shoup. Fast polynomial factorization over high algebraic extensions of finite fields. In ISSAC'97, pages 184--188. ACM, 1997.
[30]
K. S. Kedlaya and C. Umans. Fast polynomial factorization and modular composition. SICOMP, 40(6):1767--1802, 2011.
[31]
S. Lang. Algebra. Springer, 3rd edition, January 2002.
[32]
D. Lazard. A new method for solvong algebraic systems of positive dimension. Disc. Appl. Math., 33:147--160, 1991.
[33]
D. Lazard. Solving zero-dimensional algebraic systems. J. Symb. Comput., 13:147--160, 1992.
[34]
F. Le Gall. Powers of tensors and fast matrix multiplication. In ISSAC'14, pages 296--303. ACM, 2014.
[35]
R. Lebreton. Relaxed Hensel lifting of triangular sets. J. Symb. Comput., 68, Part 2:230--258, 2015.
[36]
H. W. Lenstra. Factoring integers with elliptic curves. Annals of Mathematics, 126:649--673, 1987.
[37]
X. Li, M. Moreno Maza, and É. Schost. Fast arithmetic for triangular sets: from theory to practice. In ISSAC'07, pages 269--276. ACM, 2007.
[38]
M. Moreno Maza. On triangular decompositions of algebraic varieties. Technical Report TR 4/99, NAG Ltd, Oxford, UK, 1999. http://www.csd.uwo.ca/moreno/.
[39]
C. Pascal and É. Schost. Change of order for bivariate triangular sets. In ISSAC'06, pages 277--284. ACM, 2006.
[40]
A. Poteaux and É. Schost. Modular composition modulo triangular sets and applications. Comput. Complexity, 22(3):463--516, 2013.
[41]
A. Poteaux and É. Schost. On the complexity of computing with zero-dimensional triangular sets. J. Symb. Comput., 50:110--138, 2013.
[42]
J. F. Ritt. Differential Algebra. Dover Publications, 1966.
[43]
A. Rostovtsev and A. Stolbunov. Public-key cryptosystem based on isogenies. Cryptology ePrint Archive, Report 2006/145, April 2006.
[44]
A. Scheerhorn. Trace- and norm-compatible extensions of finite fields. Appl. Algebra Engrg. Comm. Comput., 3(3):199--209, 1992.
[45]
R. Schoof. Elliptic curves over finite fields and the computation of square roots mod(p\). Math. Comp., 44(170):483--494, 1985.
[46]
E. S. Selmer. Linear recurrence relations over finite fields. Department of Mathematics, University of Bergen, 1966.
[47]
V. Shoup. New algorithms for finding irreducible polynomials over finite fields. Math. Comp., 54:435--447, 1990.
[48]
V. Shoup. Fast construction of irreducible polynomials over finite fields. J. Symb. Comput., 17(5):371--391, 1994.
[49]
V. Shoup. A new polynomial factorization algorithm and its implementation. J. Symb. Comput., 20(4):363--397, 1995.
[50]
I. E. Shparlinski. Finding irreducible and primitive polynomials. Appl. Algebra Engrg. Comm. Comput., 4(4):263--268, 1993.
[51]
E. Teske. An elliptic curve trapdoor system. Journal of Cryptology, 19(1):115--133, January 2006.
[52]
W. T. Wu. On zeros of algebraic equations -- an application of Ritt principle. Kexue Tongbao, 31:1--5, 1986.
Index Terms
- Algorithms for Finite Field Arithmetic
Recommendations
Enumeration of self-reciprocal irreducible monic polynomials with prescribed leading coefficients over a finite field
AbstractA polynomial is called self-reciprocal (or palindromic) if the sequence of its coefficients is palindromic. In this paper we enumerate self-reciprocal irreducible monic polynomials over a finite field with prescribed leading ...
Counting irreducible polynomials with prescribed coefficients over a finite field
AbstractWe continue our study on counting irreducible polynomials over a finite field with prescribed coefficients. We set up a general combinatorial framework using generating functions with coefficients from a group algebra which is ...
A note on the number of irreducible polynomials over finite fields
Analysis, combinatorics and computingA formula in terms of the Möbius function for the number of monic irreducible polynomials of a given degree over a finite field is well-known. In this note, a lower bound for that number is provided.
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2015
374 pages
ISBN:9781450334358
DOI:10.1145/2755996
- Conference Chair:
- Daniel Robertz,
- General Chair:
- Steve Linton,
- Program Chair:
- Kazuhiro Yokoyama
Copyright © 2015 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 24 June 2015
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Conference
ISSAC'15
Sponsor:
ISSAC'15: International Symposium on Symbolic and Algebraic Computation
July 6 - 9, 2015
Bath, United Kingdom
Acceptance Rates
ISSAC '15 Paper Acceptance Rate 43 of 71 submissions, 61%;
Overall Acceptance Rate 395 of 838 submissions, 47%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 145Total Downloads
- Downloads (Last 12 months)3
- Downloads (Last 6 weeks)0
Reflects downloads up to 14 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in