Fast algorithm of square rooting in some odd characteгistic finite field

S. B. Gashkov ; I. B. Gashkov

Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 5 (2018), pp. 8-14

Résumé

It was proved that the complexity of square root computation in the Galois field $GF(3^s),$ $s=2^kr,$ is equal to $O(M(2^k)M(r)k+M(r)\log_2 r)+2^k kr^{1+o(1)},$ where $M(n)$ is the complexity of multiplication of polynomials of degree $n$ over fields with characteristics $3.$ The complexity of multiplication and division in the field $GF(3^s)$ is equal to $O(M(2^k)M(r))$ and $O(M(2^k)M(r))+r^{1+o(1)}$, respectively. If the basis in the field $GF(3^r)$ is determined by an irreducible binom over $GF(3)$ or is an optimal normal basis, then the summands $2^k kr^{1+o(1)}$ and $r^{1+o(1)}$ can be omitted. For $M(n)$ one may take $n\log_2 n\psi(n) $, where $\psi(n)$ grows slower than any iteration of the logarithm. If $k$ grows and $r$ is fixed, than all the estimates presented here have the form $O_r(M(s)\log_2 s)=s (\log_2 s)^2\psi(s).$

Bibliographie

[1] Tonelli A., “Bemerkung uber die Aulosung quadratischer Congruenzen”, Goettinger Nachr., 1891, 344–346 | Zbl

[2] Bolotov A.A., Gashkov S.B., Frolov A.B., Chasovskikh A.A., Elementarnoe vvedenie v ellipticheskuyu kriptografiyu. Algebraicheskie i algoritmicheskie osnovy, URSS, M., 2012

[3] Bach E., “Explicit bounds for primality testing and related problems”, Math. Comp., 22 (1989), 355–380 | MR

[4] Bach E., “A note to square roots in finite fields”, IEEE Trans. Inform. Theory, 36 (1990), 1494–1498 | DOI | MR | Zbl

[5] Fuerer M., “Faster integer multiplication”, SIAM J. Comput., 39:3 (2009), 979–1005 | DOI | MR | Zbl

[6] Harvey D., van der Hoeven J., Lecerf G., Faster polynomial multiplication over finite fields, 12 Jul 2014, arXiv: 1407.3361 [cs.CC] | MR

[7] Gashkov S.B., Sergeev I.S., “O slozhnosti i glubine bulevykh skhem dlya umnozheniya i invertirovaniya v konechnykh polyakh kharakteristiki dva”, Diskretn. matem., 25:1 (2013), 3–32 | DOI | Zbl

[8] Bernstein D.J., “Batch binary Edwards”, Advances in Cryptology. CRYPTO, 2009, 317–336 | MR | Zbl

[9] Bernstein D.J., Chuengsatiansup C., Lange T., “Curve 41417: Karatsuba revisited”, Cryptographic hardware and embedded systems. CHES, 2014, 316–334 | Zbl

[10] Gashkov S.B., Sergeev I.S., “O slozhnosti i glubine bulevykh skhem dlya umnozheniya i invertirovaniya v nekotorykh polyakh $GF(2^n)$”, Vestn. Mosk. un-ta. Matem. Mekhan., 2009, no. 4, 3–7 | MR | Zbl

[11] Gashkov S.B., Sergeev I.S., “O primenenii metoda addittivnykh tsepochek dlya invertirovaniya v konechnykh polyakh”, Diskretn. matem., 18:4 (2006), 56–72 | DOI | MR | Zbl

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

[13] Gashkov S.B., Sergeev I.S., “Slozhnost vychislenii v konechnykh polyakh”, Fund. i prikl. matem., 17:4 (2012), 95–131

[14] Kedlaya K. S., Umans C., “Fast polynomial factorization and modular composition”, SIAM J. Comput., 40:6 (2011), 1767–1802 | DOI | MR | Zbl

[15] Gashkov I.B., Sidelnikov V.M., “Lineinye troichnye kvazisovershennye kody, ispravlyayuschie dve oshibki”, Problemy peredachi informatsii, 22:4 (1986), 43–48 | MR | Zbl

[16] Dodunekov S.M., Nilson Ya., “O dekodirovanii nekotorykh zamechatelnykh troichnykh kodov”, Problemy peredachi informatsii, 31:2 (1995), 36–43 | MR | Zbl