Geodesic
On constructing circuits for transforming the polynomial and normal bases of finite fields from one to the other
Diskretnaya Matematika, Tome 19 (2007) no. 3, pp. 89-101.

Voir la notice de l'article provenant de la source Math-Net.Ru

It is shown that the transformations of normal and polynomial bases of the field $GF(p^n)$ from one to the other can be performed by a circuit over $GF(p)$ with complexity $O(n^{1.806})$ and depth $O(\log n)$. 
@article{DM_2007_19_3_a7,
     author = {I. S. Sergeev},
     title = {On constructing circuits for transforming the polynomial and normal bases of finite fields from one to the other},
     journal = {Diskretnaya Matematika},
     pages = {89--101},
     publisher = {mathdoc},
     volume = {19},
     number = {3},
     year = {2007},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2007_19_3_a7/}
}
TY  - JOUR
AU  - I. S. Sergeev
TI  - On constructing circuits for transforming the polynomial and normal bases of finite fields from one to the other
JO  - Diskretnaya Matematika
PY  - 2007
SP  - 89
EP  - 101
VL  - 19
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2007_19_3_a7/
LA  - ru
ID  - DM_2007_19_3_a7
ER  - 
%0 Journal Article
%A I. S. Sergeev
%T On constructing circuits for transforming the polynomial and normal bases of finite fields from one to the other
%J Diskretnaya Matematika
%D 2007
%P 89-101
%V 19
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2007_19_3_a7/
%G ru
%F DM_2007_19_3_a7
I. S. Sergeev. On constructing circuits for transforming the polynomial and normal bases of finite fields from one to the other. Diskretnaya Matematika, Tome 19 (2007) no. 3, pp. 89-101. http://geodesic.mathdoc.fr/item/DM_2007_19_3_a7/

[1] Lidl R., Niderreiter Kh., Konechnye polya, Mir, Moskva, 1988 | Zbl

[2] Jungnickel D., Finite fields: structure and arithmetics, Wissenschaftsverlag, Mannheim, 1995 | MR

[3] von zur Gathen J., Gerhard J., Modern computer algebra, Cambridge Univ. Press, Cambridge, 1999 | MR

[4] Bolotov A. A., Gashkov S. B., “O bystrom umnozhenii v normalnykh bazisakh konechnykh polei”, Diskretnaya matematika, 13:3 (2001), 3–31 | MR | Zbl

[5] Feisel S., von zur Gathen J., Shokrollahi M. A., “Normal bases via general Gauss periods”, Math. Comput., 68:225 (1999), 271–290 | DOI | MR | Zbl

[6] Brent R., Kung H., “Fast algorithms for manipulating formal power series”, J. ACM, 25:4 (1978), 581–595 | DOI | MR | Zbl

[7] Huang X., Pan V., “Fast rectangular matrix multiplication and applications”, J. Complexity, 14 (1998), 257–299 | DOI | MR | Zbl

[8] Lupanov O. B., Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izd-vo MGU, Moskva, 1984

[9] Kaltofen E., Shoup V., “Subquadratic-time factoring of polynomials over finite fields”, Math. Comput., 67:223 (1998), 1179–1197 | DOI | MR | Zbl

[10] Bini D., Pan V., Polynomial and matrix computations, Vol. 1, Birkhäuser, Boston, 1994 | MR | Zbl

[11] von zur Gathen J., Shoup V., “Computing Frobenius maps and factoring polynomials”, Comput. Complexity, 2 (1992), 187–224 | DOI | MR | Zbl

[12] von zur Gathen J., Giesbrecht M., “Constructing normal bases in finite fields”, Symb. Comp., 10 (1990), 547–570 | DOI | MR | Zbl