zbMATH — the first resource for mathematics

Elliptic periods for finite fields. (English) Zbl 1216.11106
Summary: We construct two new families of bases for finite field extensions. Bases in the first family, the so-called elliptic bases, are not quite normal bases, but they allow very fast Frobenius exponentiation while preserving sparse multiplication formulas. Bases in the second family, the so-called normal elliptic bases are normal bases and allow fast (quasi-linear) arithmetic. We prove that all extensions admit models of this kind.

11T30 Structure theory for finite fields and commutative rings (number-theoretic aspects)
12E20 Finite fields (field-theoretic aspects)
Full Text: DOI arXiv
[1] L.M. Adleman, H.W. Lenstra, Finding irreducible polynomials over finite fields, in: Proceedings of the 18th Annual ACM Symposium on the Theory of Computing, 1986, pp. 350-355
[2] Ash, D.W.; Blake, I.F.; Vanstone, S.A., Low complexity normal basis, Discrete appl. math., 25, 3, 191-210, (1989) · Zbl 0712.11073
[3] Ballet, S., An improvement of the construction of the D.V. and G.V. chudnovsky algorithm for multiplication in finite fields, Theoret. comput. sci., 352, 293-305, (2006) · Zbl 1099.11073
[4] Canon, J.; Bosma, W.; Fieker, C.; Steel, A., Handbook of magma functions, (2008), Sydney, version 2.14
[5] Cantor, D.G.; Kaltofen, E., On fast multiplication of polynomials over arbitrary algebras, Acta inform., 28, 693-701, (1991) · Zbl 0766.68055
[6] Chaumine, J., Complexité bilinéaire de la multiplication dans des petits corps finis, C. R. acad. sci. Paris ser. I, 343, (2006) · Zbl 1140.11033
[7] M. Christopoulou, T. Garefalakis, D. Panario, D. Thomson, The trace of an optimal normal element and low complexity normal bases, Des. Codes Cryptogr. (2008), in press · Zbl 1196.12001
[8] Chudnovsky, D.V.; Chudnovsky, G.V., Algebraic complexities and algebraic curves over finite fields, J. complexity, 4, 285-316, (1988) · Zbl 0668.68040
[9] Couveignes, J.-M.; Lercier, R., Galois invariant smoothness basis, (), 154-179
[10] S. Gao, Normal basis over finite fields, PhD thesis, Waterloo University, 1993
[11] Gao, S.; Lenstra, H.W., Optimal normal basis, Des. codes cryptogr., 2, 315-323, (1992) · Zbl 0770.11055
[12] Gao, S.; von zur Gathen, J.; Panario, D.; Shoup, V., Algorithms for exponentiation in finite fields, J. symbolic comput., 29, 6, 879-889, (2000) · Zbl 0997.11112
[13] von zur Gathen, J.; Nöcker, M., Computing special powers in finite fields, Math. comp., 73, 247, 1499-1523, (2004) · Zbl 1081.68125
[14] Itoh, T.; Tsujii, S., A fast algorithm for computing multiplicative inverses in \(\mathit{GF}(2^m)\) using normal basis, Inform. and comput., 78, 171-177, (1988) · Zbl 0672.68015
[15] Iwaniec, H., On the problem of Jacobsthal, Demonstratio math., 11, 225-231, (1978) · Zbl 0378.10029
[16] Mullin, R.C.; Onyszchuk, I.M.; Vanstone, S.A.; Wilson, R.M., Optimal normal basis in \(\mathit{GF}(p^n)\), Discrete appl. math., 22, 149-161, (1989) · Zbl 0661.12007
[17] Schönhage, A., Schnelle multiplikation von polynomen über Körpen der characteristik 2, Acta inform., 7, 395-398, (1977) · Zbl 0362.65011
[18] Schönhage, A.; Strassen, V., Schnelle multiplikation grosser zahlen, Computing, 7, 281-292, (1971) · Zbl 0223.68007
[19] Shokrollahi, M.A., Optimal algorithms for multiplication in certain finite fields using algebraic curves, SIAM J. comput., 21, 6, 1193-1198, (1992) · Zbl 0778.11075
[20] Silverman, J., The arithmetic of elliptic curves, (1986), Springer · Zbl 0585.14026
[21] Wan, Z.-X.; Zhou, K., On the complexity of the dual basis of a type I optimal normal basis, Finite fields appl., 13, 411-417, (2007) · Zbl 1176.11067
[22] Wassermann, A., Zur arithmetik in endlichen Körpern, Bayreuth. math. schr., 44, 147-251, (1993) · Zbl 0786.11069
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.