Geodesic
On the construction of a primitive normal basis in a finite field
Sbornik. Mathematics, Tome 67 (1990) no. 2, pp. 527-533 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Let $n$ be a natural number, $q$ a prime power, and $\theta$ a primitive element of the field $GF(q^n)$. This paper shows that there exist absolute constants $c_1,c_2>0$ such that for $N\geqslant\max(\exp\exp(c_1\ln^2n),c_2n\ln q)$ the set of elements $\theta^k$, $k=1,\dots,N$, includes at least one which generates a primitive normal basis of $GF(q^n)$ over $GF(q)$. For fixed $n$, this gives a polynomial time algorithm in $\ln q$ which, given an arbitrary primitive element $\theta\in GF(q^n)$, finds an element which generates a primitive normal basis for $GF(q^n)$ over $GF(q)$. Bibliography: 17 titles. 
@article{SM_1990_67_2_a10,
     author = {S. A. Stepanov and I. E. Shparlinski},
     title = {On the construction of a~primitive normal basis in a~finite field},
     journal = {Sbornik. Mathematics},
     pages = {527--533},
     year = {1990},
     volume = {67},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_1990_67_2_a10/}
}
TY  - JOUR
AU  - S. A. Stepanov
AU  - I. E. Shparlinski
TI  - On the construction of a primitive normal basis in a finite field
JO  - Sbornik. Mathematics
PY  - 1990
SP  - 527
EP  - 533
VL  - 67
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/SM_1990_67_2_a10/
LA  - en
ID  - SM_1990_67_2_a10
ER  - 
%0 Journal Article
%A S. A. Stepanov
%A I. E. Shparlinski
%T On the construction of a primitive normal basis in a finite field
%J Sbornik. Mathematics
%D 1990
%P 527-533
%V 67
%N 2
%U http://geodesic.mathdoc.fr/item/SM_1990_67_2_a10/
%G en
%F SM_1990_67_2_a10
S. A. Stepanov; I. E. Shparlinski. On the construction of a primitive normal basis in a finite field. Sbornik. Mathematics, Tome 67 (1990) no. 2, pp. 527-533. http://geodesic.mathdoc.fr/item/SM_1990_67_2_a10/

[1] Mak-Vilyame F. Dzh., Sloen N. Dzh. A., Teoriya kodov, ispravlyayuschikh oshibki, Svyaz, M., 1979

[2] Lidl R., Niederreiter H., Finite fields, Addison-Wesley, London, 1983 | MR | Zbl

[3] Carlitz L., “Primitive roots in a finite field”, Trans. Amer. Math. Soc., 73 (1952), 373–382 | DOI | MR | Zbl

[4] Carlitz L., “Some problem involving primitive roots in a finite field”, Proc. Nat. Acad. Sci. USA, 38 (1952), 314–318 | DOI | MR | Zbl

[5] Davenport H., “Bases for finite fields”, J. Lond. Math. Soc., 43 (1968), 21–39 | DOI | MR | Zbl

[6] Lenstra H. W., Shoof R. J., “Primitive normal bases for finite fields”, Math. Compui, 48:177 (1987), 217–231 | DOI | MR | Zbl

[7] Vinogradov I. M., “Sur la distribution des residues et des non residues des puissances”, Zhurn. fiz.-mat. o-va pri Permsk. un-te, 1 (1918), 94–98

[8] Vinogradov I. M., “O naimenshem pervoobraznom korne”, DAN SSSR, 1930, no. 1, 7–11 | Zbl

[9] Hua Loo-keng., “On the least primitive root of a prirne”, Bull. Amer. Math. Soc., 48 (1942), 726–730 | DOI | MR | Zbl

[10] Erdos F., “On the least primitive root of a prime $p$”, Bull Amer. Math. Soc., 51 (1945), 131–132 | DOI | MR

[11] Wang Yuan., “On the least primitive root of a prime”, Acta Math. Sinica, 9. (1959), 432–441 | MR | Zbl

[12] Burgess D. A., “On character sums and primitive root”, Proc. Lond. Math. Soc., 3 (1962), 179–192 | DOI | MR

[13] Burgess D. A., Elliot P. D. T. A., “The average of the least primitive root”, Mathematika, 15 (1968), 39–50 | MR | Zbl

[14] Dixon D. J., “Asymptoticaly fast factorization of integers”, Math. Comp., 36 (1981), 255–260 | DOI | MR | Zbl

[15] Stepanov S. A., Shparlinskii I. E., “O postroenii normalnogo bazisa konechnogo polya”, Acta Arithm., 49 (1987), 189–192 | MR | Zbl

[16] Shparlinskii I. E., Arifmeticheskie svoistva rekurrentnykh posledovatelnostei i ikh nekotorye prilozheniya, Dis. ... kand. fiz.-matem. nauk, MGPI im. V. I. Lenina, 1980

[17] Postnikov A. G., Vvedenie v analiticheskuyu teoriyu chisel, Nauka, M., 1971 | MR