HomeIssuesOn solving big systems of congruences

On solving big systems of congruences | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 6 (Приложение).

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: 249
  • Title On solving big systems of congruences
  • Headline On solving big systems of congruences
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 6 (Приложение)
  • Date:
  • DOI
Keywords
взаимно простая база, наибольший общий делитель, дерево наибольших общих делителей, НОД слиянием, coprime base, gcd, merge gcd, gcd tree
Authors
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 | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 6 (Приложение).
On solving big systems of congruences | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 6 (Приложение).
Download full-text version
Counter downloads: 1893
Download file