Geodesic
On fast multiplication in normal bases of finite fields
Diskretnaya Matematika, Tome 13 (2001) no. 3, pp. 3-31.

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

We estimate the complexity of transition from normal bases to standard ones and discuss the related problems of effective realization of arithmetic operations in finite fields of high dimensionality. The work was supported by the Russian Foundation for Basic Research, grant 99–01–01175, the Program of support of leading scientific schools, grant 00–15–96103, the Program ‘Universities of Russia,’ and by the Federal program ‘Integration,’ joint project A0110. 
@article{DM_2001_13_3_a0,
     author = {A. A. Bolotov and S. B. Gashkov},
     title = {On fast multiplication in normal bases of finite fields},
     journal = {Diskretnaya Matematika},
     pages = {3--31},
     publisher = {mathdoc},
     volume = {13},
     number = {3},
     year = {2001},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2001_13_3_a0/}
}
TY  - JOUR
AU  - A. A. Bolotov
AU  - S. B. Gashkov
TI  - On fast multiplication in normal bases of finite fields
JO  - Diskretnaya Matematika
PY  - 2001
SP  - 3
EP  - 31
VL  - 13
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2001_13_3_a0/
LA  - ru
ID  - DM_2001_13_3_a0
ER  - 
%0 Journal Article
%A A. A. Bolotov
%A S. B. Gashkov
%T On fast multiplication in normal bases of finite fields
%J Diskretnaya Matematika
%D 2001
%P 3-31
%V 13
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2001_13_3_a0/
%G ru
%F DM_2001_13_3_a0
A. A. Bolotov; S. B. Gashkov. On fast multiplication in normal bases of finite fields. Diskretnaya Matematika, Tome 13 (2001) no. 3, pp. 3-31. http://geodesic.mathdoc.fr/item/DM_2001_13_3_a0/

[1] Beplekemp E., Algebpaicheskaya teopiya kodipovaniya, Mip, Moskva, 1971

[2] Bolotov A. A., Gashkov S. B., Frolov A. B., Chasovskikh A. B., Algoritmicheskie osnovy ellipticheskoi kriptografii, Izd-vo MEI, Moskva, 2000

[3] Gashkov S. B. Chubarikov V. N., Arifmetika. Algoritmy. Slozhnost vychislenii, Vysshaya shkola, Moskva, 2000

[4] Knut D., Iskusstvo programmirovaniya na EVM, t. 2, Mip, Moskva, 1977

[5] Lidl R., Hideppaitep G., Konechnye polya, Mip, Moskva 1988

[6] Jungnickel D., Finite fields: structure and arithmetics, B. I.-Wissenschaftsverlag, Mannheim, 1993 | MR | Zbl

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

[8] Bolotov A. A., Gashkov S. B., Frolov A. B., Chasovskikh A. B., “O metodakh realizatsii umnozheniya mnogochlenov nad konechnymi polyami”, Vestnik MEI, 2000, no. 3, 33–40

[9] Bolotov A. A., Gashkov S. B., Frolov A. B., Chasovskikh A. B., “O metodakh implementatsii arifmeticheskikh operatsii v konechnykh polyakh”, Vestnik MEI, 2000, no. 4, 24–32

[10] Bolotov A. A., Gashkov S. B., Frolov A. B., Chasovskikh A. B., “Programmnye i skhemnye metody umnozheniya mnogochlenov dlya ellipticheskoi kriptografii”, Izvestiya RAN. Teoriya i sistemy upravleniya, 2000, no. 5, 66–75 | MR

[11] Bolotov A. A., Gashkov S. B., Khokhlov R. A., “O slozhnosti algoritmov postroeniya neprivodimykh trekhchlenov i pyatichlenov nad konechnymi polyami”, Intellektualnye sistemy, 4:3-4 (1999), 12–34

[12] Konovaltsev I. V., “Ob odnom algoritme resheniya lineinykh uravnenii v konechnykh polyakh”, Probl. kibern., 19 (1967), 269–274

[13] Ash D. W., Blake I. F., Vanstone S. A., “Low complexity normal bases”, Discrete Appl. Math., 25 (1989), 191–210 | DOI | MR | Zbl

[14] Gao S., Lenstra H. W., “Optimal normal bases”, Design, Codes and Cryptography, 2 (1992), 315–323 | DOI | MR | Zbl

[15] Gao S., Vanstone S. A., “On orders of optimal normal basis generators”, Math. Comput., 64 (1995), 1227–1233 | DOI | MR | Zbl

[16] Gao S., von zur Gathen J., Panario D., “Gauss periods: orders and cryptografical applications”, Math. Comput., 67 (1998), 343–352 | DOI | MR | Zbl

[17] Gashkov S., Kochergin V., “On addition chains of vectors, gate circuits, and the complexity of computation of power”, Syberian Adv. Math., 4 (1994), 1–16 | MR

[18] von zur Gathen J., Giesbrecht M., “Constructing normal bases in finite fields”, J. Symbolic Comput., 10 (1990), 547–579 | DOI | MR

[19] Mullin R. C., Onyszchuk I. M., Vanstone S. A., Wilson R. M., “Optimal normal bases in $\mathit{GF}(p^{n})$”, Discrete Appl. Math., 22 (1988/89), 149–161 | DOI | MR

[20] Schönhage A., “Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2”, Acta Informatica, 7 (1977), 395–398 | DOI | MR | Zbl

[21] Seguin J. E., “Low complexity normal bases”, Discrete Appl. Math., 28 (1990), 309–312 | DOI | MR | Zbl

[22] Semaev I. A., “Konstruktsiya neprivodimykh polinomov nad konechnymi polyami s lineino nezavisimymi kornyami”, Matem. sb., 135(177):4 (1988), 520–532 | MR | Zbl

[23] Sidelnikov V. M., “O normalnykh bazisakh konechnogo polya”, Matem. sb., 133:4 (1987), 497–507 | MR