Пусть дано конечное множество S натуральных чисел, такое, что почти все его элементы попарно взаимно просты. Рассматривается алгоритм нахождения всех элементов s Е S, таких, что (s, s') > 1 для некоторого s' Е S, s' = s, который позволяет сводить произвольную систему полиномиальных сравнений к нескольким системам с взаимно простыми модулями.
Скачать электронную версию публикации
Загружен, раз: 247
- Title К решению больших систем сравнений
- Headline К решению больших систем сравнений
- Publesher
Tomsk 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 (Приложение).
Скачать полнотекстовую версию
Полнотекстовая версияЗагружен, раз: 1888