On solving big systems of congruences | Applied Discrete Mathematics. Supplement. 2013. № 6.

HomeIssuesOn solving big systems of congruences | Applied Discrete Mathematics. Supplement. 2013. № 6.

On solving big systems of congruences

Let S be a finite set of positive integers such that almost all its elements are pairwise coprime. An algorithm is presented for finding all elements s E S, such that (s,s') > 1 for an element s' E S, s' = s. The algorithm allows to reduce any system of polynomial congruences to a number of systems with coprime moduli.

Download file
Counter downloads: 291

Keywords

взаимно простая база, наибольший общий делитель, дерево наибольших общих делителей, НОД слиянием, coprime base, gcd, merge gcd, gcd tree

Authors

NameOrganizationE-mail
Zhukov K. DLaboratory of Theory of Probability and its Applications (Moscow)
Rybakov A. S.Laboratory of Theory of Probability and its Applications (Moscow)
Всего: 2

References

Bach E., Miller G, and Shallit J. Factor refinement // J. Algorithms. 1993. No. 15. P. 199-222.
Smedley T. J Detecting algebraic dependencies between unnested radicals: extended abstract // Proc. Intern. Symp. on Symbolic and Algebraic Computation. Tokyo, Japan, 1990. P. 292-293.
Luneburg H. On a little but useful algorithm // AAECC'85. LNCS. 1986. V.229. P. 296-301.
Bernstein D. J. Factoring into coprimes in essentially linear time // J. Algorithms. 2005. No. 54(1). P. 1-30.
Bernstein D. J. Scaled reminder trees // http://cr.yp.to/papers.html#scaledmod
On solving big systems of congruences | Applied Discrete Mathematics. Supplement. 2013. № 6.

On solving big systems of congruences | Applied Discrete Mathematics. Supplement. 2013. № 6.