Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Fast Algorithm of Square Rooting in Some Finite Fields of Odd Characteristic
Moscow State University, Russia.
Karlstad University, Faculty of Health, Science and Technology (starting 2013), Department of Mathematics and Computer Science (from 2013).
2018 (English)In: Moscow University Mathematics Bulletin, ISSN 0027-1322, Vol. 73, no 5, p. 176-181Article in journal (Refereed) Published
Abstract [en]

It was proved that the complexity of square root computation in the Galois field GF(3 (s) ), s = 2 (k) r, 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 of 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 binomial 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 grow 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).

Place, publisher, year, edition, pages
Cham: Springer, 2018. Vol. 73, no 5, p. 176-181
National Category
Geometry
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:kau:diva-70427DOI: 10.3103/S0027132218050029ISI: 000450666000002OAI: oai:DiVA.org:kau-70427DiVA, id: diva2:1268598
Available from: 2018-12-06 Created: 2018-12-06 Last updated: 2018-12-13Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Gashkov, Igor

Search in DiVA

By author/editor
Gashkov, Igor
By organisation
Department of Mathematics and Computer Science (from 2013)
Geometry

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 53 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf