Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Designs, Codes and Cryptography
Published in: Designs, Codes and Cryptography 3/2015

01-03-2015

Computing in degree \(2^k\)-extensions of finite fields of odd characteristic

Authors: Javad Doliskani, Éric Schost

Published in: Designs, Codes and Cryptography | Issue 3/2015

Login to get access

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We show how to perform basic operations (arithmetic, square roots, computing isomorphisms) over finite fields of the form \(\mathbb F _{q^{2^k}}\) in essentially linear time.
previous article On the bounds and achievability about the ODPC of over prime fields for increasing message length
next article Classification of self-dual codes of length 50 with an automorphism of odd prime order
Footnotes
1
An algorithm is quasi-linear time in \(n\) if it has complexity \(O(n\log ^kn)\) for a constant \(k\).
 
Literature
1.
Bostan A., Chowdhury M.F.I., van der Hoeven J., Schost É.: Homotopy methods for multiplication modulo triangular sets. J. Symb. Comput. 46(12), 1378–1402 (2011).
2.
Brent R.P., Kung H.T.: Fast algorithms for manipulating formal power series. J. Assoc. Comput. Mach. 25(4), 581–595 (1978).
3.
Cantor D.G., Kaltofen E.: On fast multiplication of polynomials over arbitrary algebras. Acta Inform. 28(7), 693–701 (1991).
4.
Cipolla, M.: Un metodo per la risoluzione della congruenza di secondo grado. Napoli Rend. 9, 153–163 (1903)
5.
De Feo L., Schost É.: Fast arithmetics in Artin–Schreier towers over finite fields. J. Symb. Comput. 47(7), 771–792 (2012).
6.
Doliskani J., Schost É.: Taking roots over high extensions of finite fields. Math. Comput. (to appear) (2012).
7.
Feng W., Nogami Y., Morikawa Y.: A fast square root computation using the Frobenius mapping. In: Information and Communications Security. Lecture Notes in Computer Science, vol. 2836, pp. 1–10. Springer, Heidelberg (2003).
8.
von zur Gathen J., Gerhard J.: Modern Computer Algebra, 2nd edn. Cambridge University Press, Cambridge (2003).
9.
von zur Gathen J., Shoup V.: Computing Frobenius maps and factoring polynomials. Comput. Complex. 2(3):187–224, (1992).
10.
Gaudry P., Schost É.: Genus 2 point counting over prime fields. J. Symb. Comput. 47(4), 368–400 (2012).
11.
Kaltofen E., Shoup V.: Fast polynomial factorization over high algebraic extensions of finite fields. In: ISSAC’97, pp. 184–188. ACM, New York (1997).
12.
Kedlaya K.S., Umans C.: Fast polynomial factorization and modular composition. SIAM J. Comput. 40(6), 1767–1802 (2011).
13.
Lang S.: Algebra, Graduate Texts in Mathematics vol. 211, 3rd edn. Springer, New York (2002).
14.
Schoof R.: Elliptic curves over finite fields and the computation of square roots mod \(p\). Math. Comput. 44, 483–494 (1985).
15.
Shanks D.: Five number-theoretic algorithms. In: Proceedings of the Second Manitoba Conference on Numerical Mathematics, pp. 51–70 (1972).
16.
17.
Shoup V.: Fast construction of irreducible polynomials over finite fields. J. Symb. Comput. 17(5), 371–391 (1994).
18.
Tonelli, A. : Bemerkung über die Auflösung quadratischer Congruenzen. Göttinger Nachrichten, pp. 344–346 (1891).
19.
Wang F., Nogami Y., Morikawa Y.: An efficient square root computation in finite fields \({GF}(p^{2^d})\). IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E88-A(10), 2792–2799 (2005).
Metadata
Title
Computing in degree -extensions of finite fields of odd characteristic
Authors
Javad Doliskani
Éric Schost
Publication date
01-03-2015
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 3/2015
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-013-9875-7

Other articles of this Issue 3/2015

Designs, Codes and Cryptography 3/2015 Go to the issue

OriginalPaper

Secret sharing on the d-dimensional cube

OriginalPaper

On generator matrices and parity check matrices of generalized integer codes

OriginalPaper

Highly nonlinear functions

OriginalPaper

On graphs and codes preserved by edge local complementation

OriginalPaper

Quasi-abelian codes

OriginalPaper

Optimal assignment schemes for general access structures based on linear programming

Premium Partner

    Image Credits