Probabilistic Construction of Normal Basis.
(Note)
Gudmund S. Frandsen1 2 version August 10, 1998
Abstract
LetFq be the finite field withqelements. A normal basis polynomial f ∈ Fq[x] of degreen is an irreducible polynomial, whose roots form a (normal) basis for the field extensionFqn :Fq. We show that a normal basis polynomial of degree n can be found in expected time O(n2+²· log(q) +n3+²), when an arithmetic operation and the generation of a random constant in the fieldFq cost unit time.
Given some basis B = {α1, α2, ..., αn} for the field extension Fqn : Fq together with an algorithm for multiplying two elements in the B- representation in timeO(nβ), we can find a normal basis for this extension and express it in terms ofB in expected timeO(n1+β+²·log(q) +n3+²).
CR Categories: F.2.1.
1991Mathematics Subject Classification: Primary 11Y16; Secondary 11T30.
Related Work.
[BDS90] give a probabilistic construction of a normal basis for Fqn : Fq for restricted values of q and n. They use that the ground field Fq can have at mostn(n−1) elementsafor which
g(a) = f(a)
(a−α)f0(α) ∈Fqn
is not a normal basis element, when f is an arbitrary but fixed irreducible polynomial of degreenoverFq andαis a root off [Art48, implicit in proof of theorem 28].
Hence, a randoma∈ Fq leads to a normal basis elementg(a)∈Fqn with probability≥ 12whenq >2n(n−1). By our lemma 1 (last part) an arbitraryb∈ Fqnis a normal basis element with probability≥12, under the same restriction.
Hence, our construction may also be used in the restricted case without loss of efficiency.
Deterministic constructions can be found in [BDS90, Len91].
1This research was supported by the ESPRIT II Basic Research Actions Program of the EC under contract No. 3075 (project ALCOM).
2Department of Computer Science, Aarhus University, Ny Munkegade, 8000 Aarhus C, Denmark.gsfrandsen@daimi.aau.dk
1
Lemma 1.
Let N denote the number of normal basis polynomials of degree n over Fq. Then
N≥qn· 1
n·(1−1
q)· 1 (1 + logq(n))e Under the restrictionq≥2n(n−1), a stronger inequality holds:
N ≥qn· 1 n· 1
2 Proof.
If f(x) ∈Fq[x] and the complete factorisation off(x) isf(x) =Qt
i=1fi(x)ei (the irreducible factorsfi(x), fj(x) are distinct, wheni6=j), then define Φ(f(x)) = qnQt
i=1(1−qni1 ), whereni is the degree of fi, andnis the degree off. The relevance of this concept comes fromN =n1Φ(xn−1) (See [LiNi83]).
To get a lower bound for Φ(f(x)), we observe that for a fixednthe minimal value occurs, whenf(x) is the product of all distinct irreducible factors of degree 1,2,3, ..., k (and some of degree k+ 1). Noticing, that xqk −x factors into distinct irreducible factors, each of which have degree at mostk, it follows that k ≤logq(n). Since every irreducible polynomial of degreeni divides xqni −x, there are at most qnin−1
i distinct factors of degree ni in f(x) (except for the q distinct degree 1 polynomials). Using that
(1− 1
qni)qni−1ni ≥(1 e)ni1 we find the lower bound
Φ(f(x)) ≥ qn(1−1 q)(1
e)1+12+13+···+1k+k+11
≥ qn(1−1 q)(1
e)1+log(k+1)
= qn(1−1 q) 1
(k+ 1)e
≥ qn(1−1
q) 1
(1 + logq(n))e which imply the first part of the lemma.
In the remaining part of the proof, we assume thatq≥2n(n−1). Forn= 1, we find that
Φ(f(x))≥qn(1−1
q)≥qn1 2
2
Forn= 2, we know thatq≥4 and we get the bound Φ(f(x))≥qn·(1−1
q)2≥qn(3
4)2≥qn1 2 Forn≥3, we have thatn≤(q−1)/2 and we get
Φ(f(x))≥qn·(1−1
q)q−12 ≥qn 1
√e ≥qn1 2
2
Theorem 2.
Given some basisB ={α1, α2, ..., αn}for the field extensionFqn :Fq together with an algorithm for multiplying two elements in theB representation in time O(nβ), we can find a normal basis for this extension and express it in terms of B in expected timeO(n1+β+²·log(q) +n3+²).
Proof.
By lemma 1, a fraction Ω(1+log(n)1 ) of the elements in Fqn generate normal bases. Hence, we expect to have to check O(log(n)) random elements in the span ofB before finding one that generates a normal basis.
Assumeα=Pn
i=1ciαi,ci∈Fq, then we may compute the representation of αqi in terms ofB for alliin timeO(n1+βlog(q)), and hence computeαqj for all j in timeO(n3). We know that{α, αq, αq2, ..., αqn−1} are linearly independent if and only if det(dij)6= 0, wheredij∈Fq is defined byαqi=Pn
j=1dijαi. Hence, we can check an arbitraryα∈span(B) for the normal basis property in time O(n1+βlog(q) +n3) from which the theorem follows.
2
Theorem 3.
A normal basis polynomial of degreen overFq can be found in expected time O(n2+²·log(q) +n3+²).
Proof.
There are Θ(qnn) irreducible polynomials of degreenoverFq. Hence, by lemma 1, we expect to have to checkO(log(n)) irreducible polynomials before finding a normal basis polynomial. A random irreducible polynomialf(x) can be found in expected timeO(n2+²·log(q)) (see [Ben81]).
3
Ifαis a root off(x), thenB={1, α, α2, ..., αn−1}is a polynomial basis for Fqn:Fq, and we can multiply any two elements in theB-representation in time O(n1+²). Using the proof of theorem 2, we can check that{α, αq, ..., αqn−1}form a normal basis in timeO(n2+²log(q) +n3) from which the theorem follows.
2
References
[Art48] Artin, E.,Galois Theory (Second Edition).Notre Dame Mathemat- ical Lectures. Notre Dame, Indiana, 1948.
[BDS90] Bach, E., Driscoll, J. and Shallit, J., Factor Refinement.Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms (1990), pp. 201-211.
[Ben81] Ben-Or, M., Probabilistic Algorithms in Finite Fields.Proceedings of the 22nd Annual IEEE Symposium on Foundations of Computer Science(1981), pp. 394-398.
[Len91] Lenstra, Jr., H. W., Finding Isomorphisms Between Finite Fields.
Mathematics of Computation56 (1991), pp. 329-347.
[LiNi83] Lidl, R. and Niederreiter, H.,Finite Fields.Encyclopedia of Math- ematics and its Applications 20, Addison Wesley, 1983.
4
