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
The Complexity of Solving Low Degree Equations over Ring of Integers and Residue Rings
Moscow State University, Russia.
Karlstad University, Faculty of Technology and Science, Department of Mathematics.
National Research University, Russia.
2019 (English)In: MOSCOW UNIVERSITY MATHEMATICS BULLETIN, ISSN 0027-1322, Vol. 74, no 1, p. 5-13Article in journal (Refereed) Published
Abstract [en]

It is proved that for an arbitrary polynomial f(x)Zpn[X] of degree d the Boolean complexity of calculation of one its root (if it exists) equals O(dM(n(p))) for a fixed prime p and growing n, where (p) = remvoelog(2)p, and M(n) is the Boolean complexity of multiplication of two binary n-bit numbers. Given the known decomposition of this number into prime factors n = m(1)...m(k), mi=pini, i = 1,..., k, with fixed k and primes p(i), i = 1,..., k, and growing n, the Boolean complexity of calculation of one of solutions to the comparison f(x) = 0 mod n equals O(dM((n))). In particular, the same estimate is obtained for calculation of one root of any given degree in the residue ring Z(m). As a corollary, it is proved that the Boolean complexity of calculation of integer roots of a polynomial f(x) is equal to O-d(M(n)), where f(x)=adxd+ad-1xd-1+...+a0,aiZ , |a(i)| < 2(n), i = 0,..., d.

Place, publisher, year, edition, pages
Cham: Springer, 2019. Vol. 74, no 1, p. 5-13
National Category
Mathematics
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:kau:diva-72005DOI: 10.3103/S0027132219010029ISI: 000465628800002OAI: oai:DiVA.org:kau-72005DiVA, id: diva2:1314633
Available from: 2019-05-09 Created: 2019-05-09 Last updated: 2019-05-10Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Gachkov, Igor

Search in DiVA

By author/editor
Gachkov, Igor
By organisation
Department of Mathematics
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 51 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