zbMATH — the first resource for mathematics

Low complexity normal bases. (English) Zbl 0712.11073
A normal basis in a finite field is a basis of conjugate elements in the field. The complexity of the normal basis is defined to be the number of nonzero terms in certain bilinear form obtained from multiplication of elements. The authors investigate low complexity normal bases and give a construction for such bases.
Reviewer: J.Liang

11T30 Structure theory for finite fields and commutative rings (number-theoretic aspects)
12E20 Finite fields (field-theoretic aspects)
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
11Y16 Number-theoretic algorithms; complexity
Full Text: DOI
[1] Ash, D.W.; Blake, I.F.; Vanstone, S.A., On the construction of low complexity normal bases, ()
[2] Berlekamp, E.R., Bit serial Reed-Solomon encoders, IEEE trans. inform. theory, 28, 869-874, (1982) · Zbl 0492.94016
[3] Carlitz, L., Primitive roots in a finite field, Trans. amer. math. soc., 73, 373-382, (1952) · Zbl 0048.27302
[4] Chor, B.; Rivest, R.L., A knapsack type public key cryptosystem, (), 54-65
[5] Davenport, H., Bases for finite fields, J. lond. math. soc., 43, 21-39, (1968) · Zbl 0159.33901
[6] Diffie, W.; Hellman, M.E., New directions in cryptography, IEEE trans. inform. theory, 22, 6, 644-654, (1976) · Zbl 0435.94018
[7] El Gamal, T., A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE trans. inform. theory, 31, 4, 469-472, (1985) · Zbl 0571.94014
[8] Imamura, K., On self-complementary bases of GF(qn) over GF(q), Trans. IECE Japan, 12, 717-721, (1983)
[9] Lenstra, H.W.; Schoof, R.J., Primative normal bases for finite fields, (1985), Preprint
[10] MacWilliams, F.J.; Sloane, N.J.A., The theory of error correcting codes, (1977), North-Holland Amsterdam · Zbl 0369.94008
[11] J.L. Massey and J.K. Omura, Computational method and apparatus for finite field arithmetic, patent application (to appear).
[12] Morii, M.; Imamura, K., A theorem that GF(24m) has no self-complementary normal bases over GF(2) for odd m, Trans. IECE Japan, 67, 655-656, (1984)
[13] R.C. Mullin, I.M. Onyszchuk and S.A. Vanstone, Optimal normal bases in GF(pn) (to appear). · Zbl 0661.12007
[14] Pohlig, S.C.; Hellman, M.E., An improved algorithm for computing logarithms over GF(p) and its cryptographic significance, IEEE trans. inform. theory, 24, 1, 106-110, (1978) · Zbl 0375.68023
[15] Seroussi, G.; Lempel, A., Factorizations of symmetric matrices and trace orthogonal bases in finite fields, SIAM J. comput., 9, 758-767, (1980) · Zbl 0451.15012
[16] Seroussi, G.; Lempel, A., On symmetric representations of finite fields, SIAM J. algebraic discrete methods, 4, 14-21, (1983) · Zbl 0506.15006
[17] Bach, E.; Shallit, J., Factoring with cyclotomic polynomials, (), 443-450
[18] Wang, C.C., Exponentiation in finite fields, ()
[19] Washington, L.C., Cyclotomic fields, (1980), Springer New York
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.