К решению больших систем сравнений | Прикладная дискретная математика. 2013. № 6 (Приложение).

Пусть дано конечное множество S натуральных чисел, такое, что почти все его элементы попарно взаимно просты. Рассматривается алгоритм нахождения всех элементов s Е S, таких, что (s, s') > 1 для некоторого s' Е S, s' = s, который позволяет сводить произвольную систему полиномиальных сравнений к нескольким системам с взаимно простыми модулями.
  • Title К решению больших систем сравнений
  • Headline К решению больших систем сравнений
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 6 (Приложение)
  • Date:
  • DOI
Ключевые слова
взаимно простая база, наибольший общий делитель, дерево наибольших общих делителей, НОД слиянием, coprime base, gcd, merge gcd, gcd tree
Авторы
Ссылки
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
 К решению больших систем сравнений | Прикладная дискретная математика. 2013. № 6 (Приложение).
К решению больших систем сравнений | Прикладная дискретная математика. 2013. № 6 (Приложение).