Change search

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
Mathematics
Mathematics
##### Identifiers
ISI: 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

Publisher's full text

Gachkov, Igor

#### Search in DiVA

Gachkov, Igor
##### By organisation
Department of Mathematics
Mathematics

doi
urn-nbn

#### Altmetric score

doi
urn-nbn
Total: 51 hits

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