Change search
Link to record
Permanent link

Direct link
BETA
Gachkov, Igor
Alternative names
Publications (10 of 18) Show all publications
Gashkov, S. B., Gachkov, I. & Frolov, A. B. (2019). The Complexity of Solving Low Degree Equations over Ring of Integers and Residue Rings. MOSCOW UNIVERSITY MATHEMATICS BULLETIN, 74(1), 5-13
Open this publication in new window or tab >>The Complexity of Solving Low Degree Equations over Ring of Integers and Residue Rings
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
National Category
Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:kau:diva-72005 (URN)10.3103/S0027132219010029 (DOI)000465628800002 ()
Available from: 2019-05-09 Created: 2019-05-09 Last updated: 2019-05-10Bibliographically approved
Gashkov, S. B. & Gashkov, I. (2018). Fast Algorithm of Square Rooting in Some Finite Fields of Odd Characteristic. Moscow University Mathematics Bulletin, 73(5), 176-181
Open this publication in new window or tab >>Fast Algorithm of Square Rooting in Some Finite Fields of Odd Characteristic
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
National Category
Geometry
Research subject
Mathematics
Identifiers
urn:nbn:se:kau:diva-70427 (URN)10.3103/S0027132218050029 (DOI)000450666000002 ()
Available from: 2018-12-06 Created: 2018-12-06 Last updated: 2018-12-13Bibliographically approved
Gachkov, I., Burtsev, A., Khokhlov, R. & Gashkov, I. (2010). Bit parallel circuits for arithmetic operations in composite fields $ GF(2^{nm}) (CMMSE).
Open this publication in new window or tab >>Bit parallel circuits for arithmetic operations in composite fields $ GF(2^{nm}) (CMMSE)
2010 (English)Conference paper, Published paper (Refereed)
National Category
Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:kau:diva-10545 (URN)9788461355105 (ISBN)
Available from: 2012-02-08 Created: 2012-02-08 Last updated: 2013-06-12Bibliographically approved
Gachkov, I. & Gashkov, S. (2010). Some Remarks on Testing Irreducibility of Polynomials and Normality of Bases in Finite Fields. Fundamenta Informaticae, 104(3), 227-238
Open this publication in new window or tab >>Some Remarks on Testing Irreducibility of Polynomials and Normality of Bases in Finite Fields
2010 (English)In: Fundamenta Informaticae, ISSN 0169-2968, E-ISSN 1875-8681, Vol. 104, no 3, p. 227-238Article in journal (Refereed) Published
National Category
Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:kau:diva-10554 (URN)10.3233/FI-2010-346 (DOI)000285459900005 ()
Available from: 2012-02-08 Created: 2012-02-08 Last updated: 2017-12-07Bibliographically approved
Gachkov, I. & Gashkov, S. (2009). Probabilistic algorithm to find a normal basis in special finite fields. Paper presented at Proceedings of the International congerence of computational and mathematical Methods in Science and Engineering , CMMSE 2009 30 June, 1-3 July 2009.. Paper presented at Proceedings of the International congerence of computational and mathematical Methods in Science and Engineering , CMMSE 2009 30 June, 1-3 July 2009..
Open this publication in new window or tab >>Probabilistic algorithm to find a normal basis in special finite fields
2009 (English)Conference paper, Published paper (Refereed)
National Category
Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:kau:diva-9865 (URN)9788461297276 (ISBN)
Conference
Proceedings of the International congerence of computational and mathematical Methods in Science and Engineering , CMMSE 2009 30 June, 1-3 July 2009.
Available from: 2012-02-08 Created: 2012-02-08 Last updated: 2013-06-12Bibliographically approved
Gachkov, I. (2008). Using the package Coding Theory for a search technique for Quasi-perfect Codes.
Open this publication in new window or tab >>Using the package Coding Theory for a search technique for Quasi-perfect Codes
2008 (English)Conference paper, Published paper (Refereed)
National Category
Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:kau:diva-25300 (URN)
Available from: 2013-01-22 Created: 2013-01-22 Last updated: 2013-01-22
Gachkov, I., Ekberg, A. & Taub, D. (2007). A geometric approach to finding new lower bounds of A ( n , d , w ). Designs, Codes and Cryptography v. 43, N 2-3 / June, 2007 pp. 85-91
Open this publication in new window or tab >>A geometric approach to finding new lower bounds of A ( n , d , w )
2007 (English)In: Designs, Codes and Cryptography v. 43, N 2-3 / June, 2007 pp. 85-91Article in journal (Refereed)
National Category
Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:kau:diva-16549 (URN)
Available from: 2013-01-21 Created: 2013-01-21 Last updated: 2013-01-21
Gachkov, I. & Larsson, H. (2007). Improvements on the Juxtaposing theorem. Serdica J. Computing 1 Volume 1, Number 2, pp. 207-212
Open this publication in new window or tab >>Improvements on the Juxtaposing theorem
2007 (English)In: Serdica J. Computing 1 Volume 1, Number 2, pp. 207-212Article in journal (Refereed)
National Category
Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:kau:diva-20236 (URN)
Available from: 2013-01-21 Created: 2013-01-21 Last updated: 2013-01-21
Gachkov, I. & Taub, D. (2007). New Optimal Constant Weight Codes. The electronic journal of combinatorics 14 , no. 1, Note 13, pp.1-6
Open this publication in new window or tab >>New Optimal Constant Weight Codes
2007 (English)In: The electronic journal of combinatorics 14 , no. 1, Note 13, pp.1-6Article in journal (Refereed)
National Category
Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:kau:diva-21781 (URN)
Available from: 2013-01-21 Created: 2013-01-21 Last updated: 2013-01-21
Gachkov, I. (2007). Visualisation of the Mathematical Process: Boolean Algebra and Graph Theory with TI-83/89. Journal of the Korea Society of Mathematical Education Vol.11, No.2, pp. 143-151
Open this publication in new window or tab >>Visualisation of the Mathematical Process: Boolean Algebra and Graph Theory with TI-83/89
2007 (English)In: Journal of the Korea Society of Mathematical Education Vol.11, No.2, pp. 143-151Article in journal (Refereed)
National Category
Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:kau:diva-25569 (URN)
Available from: 2013-01-22 Created: 2013-01-22 Last updated: 2013-01-22
Organisations

Search in DiVA

Show all publications