A Fast Algorithm to Determine Normal Polynomial over Finite Fields
Chih-Hua Chien, Trieu-Kien Truong, Yaotsu Chang and Chih-Hsuan Chen
Abstract--Normal basis in finite fields has proved to be very useful for fast arithmetic computations. The elements in a normal basis are exactly the roots of a normal polynomial. Hence a normal polynomial is just another way of describing a normal basis. In this paper, we give some computational results of normal polynomial up to degree according to the fast algorithm from Chang et al. [1].
Keywords: normal basis, normal polynomial, finite field
Ⅰ. INTRODUCTION
Efficient computations in finite fields and their architectures are important in many applications, including coding theory, computer algebra systems and public-key cryptosystems(e.g. elliptic curve cryptosystems). Although all finite fields of the same cardinality are isomorphic, their arithmetic efficiency depends greatly on the choice of bases for field element representations. Consider a basis representation of the field elements, addition operation is relatively inexpensive, whereas the multiplication is usually considered the most important finite field arithmetic operation and one of the most complex and time-consuming operations. Therefore, some different basis representation for elements of Galois field are needed. Among them, the most popular bases representation are the canonical, normal and dual bases. Normal basis is an important representation and used in many ways, such as multiplication representation and inverse representation.
Normal basis was first introduced without proof by Eisenstein [2] in 1850, and Schönemann [3] gave its proof later in 1850 for the case GF(p), where p is prime. In 1888, Hensel [4] proved for all arbitrary finite fields the exact numbers of normal elements in the extensions over finite fields. Perlis [5] proved that when n is a power of a prime p, an irreducible polynomial of degree n is normal if and only if its trace is non-zero. Later in 1986, Pei etal. [6] proved that when and 2 is a primitive root modulo , an irreducible polynomial of degree n over GF(p) is normal if and only if its trace is non-zero
The elements in a normal basis are exactly the roots of a normal polynomial. Hence a normal polynomial is just another way of describing a normal basis. In this paper, we give some computational results of normal polynomial up to degree according to the fast algorithm from Chang etal.[1].
This paper is organized as follows: Some mathematical background is introduced in section 2. Section 3 shows how the fast algorithm determines the normal polynomials. Finally, some conclusions and results are given in section 4. Finally, table 1 shows the normal polynomials with non-zero trace up to degree and the flowchart of the fast algorithm is given at the end of this paper.
Ⅱ. MATHEMATICAL BACKGROUND
Let p be a prime number and be an integer. The finite field E = GF(pm) of order pm can be viewed as a vector space of dimension m over F = GF(p). A basis of the form is called a normal basis, and is called a normal element of E over F. A monic, irreducible polynomial F[x] of degree m is called a normal polynomial if it is the minimal polynomial of some normal element.
LetαE be a root of a monic, irreducible polynomial of degree m.The elements areall roots of and
= =. The sum of all roots of is called the trace of , or the trace ofαand can be denoted by tr(f) or tr(), respectively.
The existence of a normal basis over F is equivalent to the existence of a normal polynomial in F[x]. If F[x] is a normal polynomial over F, it is obvious that tr(f) is not zero. To introduce the fast algorithm, we need to derive the p-polynomialand the definitionas follows.
Defintion2.1 A polynomial of the form is called a p-polynomial over F=GF(p). Two forms of p-polynomial will be used throughout this paper, namely,
, and
Defintion 2.2 The polynomial corresponding with the polynomial is called the linearized p-associate of in F[x], denoted by . Conversely, is called conventional p-associate of the p-polynomial in F[x].
Some information about the factor of is given in the following proposition.
Proposition 2.3 (Chang etal. [1]) Let be an monic irreducible polynomial of degree d and a divisor of degree nwith . Then one has the following:
(i) If , is divided by .
(ii) If , then is divided by if and only if p divides .
Proposition 2.4 Let be an irreducible polynomial of degree n. If , then is not divided by .
The following Proposition is well-known for factorizing a polynomial and its linearized p-associate in .
Proposition 2.5 (Schwarz[13]) Let be an n-th degree irreducible polynomial of non-zero trace. Then is not normal over F if and only if divides for some , where Mi(x) is a maximal factor of xn-1.
The following corollaries are used in judging a normal polynomial of degree n with zero trace.
Corollary 2.6 (Perlis[5]) Let for some integer k and be an irreducible polynomial over GF(p). Then is a normal polynomial if and only if .
Corollary 2.7 (Pei, Wang, Omura [6]) Let and 2 is a primitive root modulo . Let be an irreducible polynomial over F. Then is a normal polynomial if and only if .
Ⅲ. FAST ALGORITHM
The fast algorithm makes it easy to distinguish if a polynomial is normal or not.
Theorem 3.1 Let n be a positive integer and for some positive integer . Usually, we let . Suppose and . A monic, irreducible polynomial of degree n with is a normal polynomial if is not divided by for .
Proof: Since , by Proposition 2.4, we have is not divided by . Therefore, if is not divided by for , then from Proposition 2.5follows that is normal polynomial over F.
Fast Algorithm:
Step 1:Given an irreducible polynomial with degree n.
Step 2: The trace of f must not be zero otherwise f is not normal.
Step 3: If , must be a normal polynomial.
Step4: If and 2 is a primitive root modulo , must be a normal polynomial.
Step 5: Factor . Let and then find for .
Step 6: Compute q-associate for .
Step 7: If is not divided by for , then is a normal polynomial. Otherwise, is not normal.
Example 3.2 Consider when , we have and , . Therefore, . The irreducible polynomial of deg()=6 with are , , , and . Among these five polynomials, only is divided by and therefore is the only one polynomial that is not a normal polynomial with degree 6.
Ⅳ. CONCLUSION
Since a normal polynomial is just another wayof describing a normal basis,we derive the fast algorithm to distinguish if a polynomial is normal or not. Some computational results ofnormal polynomialswith nonzero traceup to degree are given in the Table1.
As one could see, when , the only irreducible but not normal polynomial is . To simplify the result, we write it as . When , only two irreducible but not normal polynomials are 241 and 253. When , there are three irreducible but not normal polynomials, which are 1807, 1821 and 1891. As for or more, there are 137 or more irreducible but not normal polynomials.We do not list the result here.
REFERENCES
[1]Y. Chang, T.K.Truong, and I.S. Reed, "Normal Bases over GF(q)," Journal of Algebra, vol.241, pp.89-101, 2001.07.
[2] G. Eisentein, Galoissche Theorie und Darstellungstheorie, Math. Ann. 107 (1993), 140-144..
[3] T. Schönemann, Über einige von Herry Dr. Eisenstein aufgestellte Lehrsätze, Irreduzible Congruenzen betreffend, J. ReineAngew. Math. 40(1850). 185-187.
[4] K. Hensel, Über die Darstellung der Zahlen eines Gattungsbereiches für einen beliebigen Primdivisor, J. ReineAngew. Math 103(1888), 230-237.
[5] S. Perlis, Normal bases of cyclic fields of prime power degree, DukeMath. J. 9(1942),507-517.
[6] D. Pei, C. Wang and J. Omura, Normal bases of finite field GF(2m), IEEETrans. Inform. Theory 32(1986), 285-287.
[7] P. K. S. Wah and M. Z. Wang, “Realization and application of the Massey-Omura lock” in Proc. Int. ZurichSeminar, Mar. 1984, pp. 175-182.
[8] C. C. Wang, T. K. Truong, H. M. Shao, L. J. Deutsch, J. K. Omura and I. S. Reed, “VLSI architecture for computing multiplications and inverse in GF(2m)”, IEEETrans. Comput., vol. C-34, pp. 709-717, 1985.
[9] D. Y. Pei, C. C. Wang and J. K. Omura, “Normal basis of finite field GF(2m),”IEEETrans. Inform. Theory,vol. IT-21, pp. 285-287, 1986
[10] I. Onyszchuk, R. Mullin, and S. Vanstorne, “Computational method and apparatus for finite field multiplication,” U. S. Patent 4 745 568, 1988.
[11] D. W. Ash, I. F. Blake, and S. A. Vanstone, “Low complexity normal bases,” Discr. Appl. Math., vol. 25, pp. 191-210, 1989.
[12] C. C. Wang and D. Y. Pei, “A VLSI design for computing exponentiations in GF(2m) and its applications to generate pseudorandom number sequences,” IEEE Trans. Comput., vol. 39, pp. 258-262, 1990. .
[13] S. Schwarz, “Contruction of Normal Bases in Cyclic Extensions of a Field,”CzechslovakMath. J., 38(1988), pp. 291-312.
[14] F. J. MacWilliams & N. J. A. Slone, The Theory Of Error-Correcting Codes. New York: North-Holland, 1977
[15]Chang, Y., P. Shiue and W. S. Chou, "On the number of primitive polynomials over finite fields," Finite Fields and their Applications, vol.11, pp.156-163, 2005.01
Irreducible polynomial / Normal polynomialn=2 / 1 / 1
n=3 / 1 / 1
n=4 / 2 / 2
n=5 / 3 / 3
n=6 / 5 / 4
n=7 / 9 / 7
n=8 / 16 / 16
n=9 / 28 / 28
n=10 / 51 / 48
n=11 / 93 / 93
n=12 / 170 / 170
n=13 / 315 / 315
n=14 / 585 / 469
n=15 / 1091 / 1035
n=16 / 2048 / 2048
n=17 / 3855 / 3825
n=18 / 7280 / 5376
n=19 / 13797 / 13797
Table 1
Flowchart of Fast Algorithms