On design of circuits of logarithmic depth for inversion in finite fields

S. B. Gashkov ; I. S. Sergeev

Diskretnaya Matematika, Tome 20 (2008) no. 4, pp. 8-28.

Résumé

We suggest a method of realisation of inversion over the standard bases of finite fields $GF(p^n)$ by means of circuits over $GF(p)$ of complexity $O(\varepsilon^{-1}n^{w+\varepsilon})$ and depth $O(\varepsilon^{-1}\log n)$, where $\varepsilon>0$, and $w1.667$ is the exponent of multiplication of $\sqrt n\times\sqrt n$ and $\sqrt n\times n$ matrices. Inversion over Gaussian normal bases is realised by a circuit of complexity $O(\varepsilon^{-b}n^{1+c\varepsilon|\log\varepsilon|})$ and depth $O(\varepsilon^{-1}\log n)$, where $b,c$ are constants.

Bibliographie

[1] Litov B., Davida G., “$O(\log n)$ parallel time finite field inversion”, Lecture Notes Computer Sci., 319, 1988, 74–80 | MR

[2] Von zur Gathen J., “Inversion in finite fields using logarithmic depth”, J. Symb. Comput., 9 (1990), 175–183 | DOI | MR | Zbl

[3] Lupanov O. B., Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, MGU, Moskva, 1984

[4] Bolotov A. A., Gashkov S. B., Frolov A. B., Chasovskikh A. A., Elementarnoe vvedenie v ellipticheskuyu kriptografiyu: protokoly kriptografii na ellipticheskikh krivykh, KomKniga, Moskva, 2006

[5] Bailey D., Paar C., “Efficient arithmetic in finite extensions with application in elliptic curve cryptography”, J. Cryptology, 14 (2001), 156–173 | MR

[6] Barreto P., Kim H., Lynn B., Scott M., “Efficient algorithms for pairing-based cryptosystems”, Lecture Notes Computer Sci., 2442, 2002, 354–368 | MR | Zbl

[7] Itoh T., Tsujii S., “A fast algorithm for computing multivariate inverses in $GF(2^n)$ using normal basis”, Inform. Comput., 78 (1988), 171–177 | DOI | MR | Zbl

[8] Bolotov A. A., Gashkov S. B., Frolov A. B., Chasovskikh A. A., Elementarnoe vvedenie v ellipticheskuyu kriptografiyu: algebraicheskie i algoritmicheskie osnovy, KomKniga, Moskva, 2006

[9] Knut D., Iskusstvo programmirovaniya, T. 2, Vilyams, Moskva, 2004

[10] Gashkov S. B., Sergeev I. S., “O primenenii metoda additivnykh tsepochek k invertirovaniyu v konechnykh polyakh”, Diskretnaya matematika, 18:4 (2006), 56–72 | MR | Zbl

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

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

[13] Sergeev I. S., “O postroenii skhem dlya perekhoda mezhdu polinomialnymi i normalnymi bazisami konechnykh polei”, Diskretnaya matematika, 19:3 (2007), 89–101 | MR | Zbl

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

[15] Von zur Gathen J., Gerland J., Modern computer algebra, Cambridge Univ. Press, Cambridge, 1999

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

[17] Beame P., Cook S., Hoover H., “Log depth circuits for division and related problems”, SIAM J. Comput., 15 (1986), 994–1003 | DOI | MR | Zbl

[18] Sergeev I. S., “Ob invertirovanii v konechnykh polyakh kharakteristiki 2 s logarifmicheskoi glubinoi”, Vestnik MGU. Seriya 1. Matematika. Mekhanika, 62:5 (2007), 29–33 | MR

[19] Eberly W., “Very fast parallel polynomial arithmetic”, SIAM J. Comput., 18 (1989), 955–976 | DOI | MR | Zbl

[20] Cantor D., Kaltofen E., “On fast multiplication of polynomials over arbitrary algebras”, Acta Inf., 28 (1991), 693–701 | DOI | MR | Zbl

[21] Noden P., Kitte L., Algebraicheskaya algoritmika, Mir, Moskva, 1999

[22] Lupanov O. B., “O ventilnykh i kontaktno-ventilnykh skhemakh”, Doklady AN SSSR, 111 (1956), 1171–1174 | MR | Zbl

[23] Karatsuba A. A., Ofman Yu. P., “Umnozhenie mnogoznachnykh chisel na avtomatakh”, Doklady AN SSSR, 145 (1962), 293–294

[24] Khrapchenko V. M., “Ob asimptoticheskoi otsenke vremeni slozheniya parallelnogo summatora”, Problemy kibernetiki, 19 (1967), 107–120

[25] Toom A. L., “O slozhnosti skhemy iz funktsionalnykh elementov, realizuyuschei umnozhenie tselykh chisel”, Doklady AN SSSR, 150 (1963), 496–498 | MR | Zbl

[26] Cantor D., “On arithmetical algorithms over finite fields”, J. Comb. Theory, A50 (1989), 285–300 | DOI | MR

[27] Von zur Gathen J., Gerhard J., “Arithmetic and factorization of polynomials over $\mathbf F_2$”, Proc. ISSAC' 96, ACM Press, New York, 1996, 1–9 | Zbl

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

[29] Massey J., Omura J., Apparatus for finite fields computation, US Patent Application, No 457627, 1986

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

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

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

[33] Gao S., von zur Gathen J., Panario D., “Gauss periods and fast exponentiation in finite fields”, Lecture Notes Computer Sci., 911, 1995, 311–322 | Zbl

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

[35] Von zur Gathen J., Nöcker M., “Fast arithmetic with general Gauss periods”, Theor. Comput. Sci., 315 (2004), 419–452 | DOI | MR | Zbl