Geodesic
On solving big systems of congruences
Prikladnaya Diskretnaya Matematika. Supplement, no. 6 (2013), pp. 116-118.

Voir la notice de l'article provenant de la source Math-Net.Ru

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\in S$, such that $(s,s')>1$ for an element $s'\in S$, $s'\ne s$. The algorithm allows to reduce any system of polynomial congruences to a number of systems with coprime moduli.
Keywords: coprime base, gcd, merge gcd, gcd tree. 
@article{PDMA_2013_6_a51,
     author = {K. D. Zhukov and A. S. Rybakov},
     title = {On solving big systems of congruences},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {116--118},
     publisher = {mathdoc},
     number = {6},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2013_6_a51/}
}
TY  - JOUR
AU  - K. D. Zhukov
AU  - A. S. Rybakov
TI  - On solving big systems of congruences
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2013
SP  - 116
EP  - 118
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2013_6_a51/
LA  - ru
ID  - PDMA_2013_6_a51
ER  - 
%0 Journal Article
%A K. D. Zhukov
%A A. S. Rybakov
%T On solving big systems of congruences
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2013
%P 116-118
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2013_6_a51/
%G ru
%F PDMA_2013_6_a51
K. D. Zhukov; A. S. Rybakov. On solving big systems of congruences. Prikladnaya Diskretnaya Matematika. Supplement, no. 6 (2013), pp. 116-118. http://geodesic.mathdoc.fr/item/PDMA_2013_6_a51/

[1] Bach E., Miller G., Shallit J., “Factor refinement”, J. Algorithms, 1993, no. 15, 199–222 | DOI | MR | Zbl

[2] Smedley T. J., “Detecting algebraic dependencies between unnested radicals: extended abstract”, Proc. Intern. Symp. on Symbolic and Algebraic Computation (Tokyo, Japan, 1990), 292–293

[3] Luneburg H., “On a little but useful algorithm”, AAECC'85, LNCS, 229, 1986, 296–301 | MR | Zbl

[4] Bernstein D. J., “Factoring into coprimes in essentially linear time”, J. Algorithms, 54:1 (2005), 1–30 | DOI | MR | Zbl

[5] Bernstein D. J., Scaled reminder trees, http://cr.yp.to/papers.html#scaledmod