On solving big systems of congruences.pdf Определение 1. Пусть S — конечное подмножество натуральных чисел. Взаимно простой базой для S называется конечное подмножество натуральных чисел B, такое, что любое число из S представляется в виде произведения элементов из B и любые два элемента множества B взаимно просты. Взаимно простые базы используются в ряде приложений, например при решении систем сравнений в целых числах [1]. Пусть задана система полиномиальных сравнений вида fi(x) = 0 (mod a^), i = = 0,1,...,m — 1, где x — набор переменных. Построим для множества чисел {a0,... , am-1} взаимно простую базу {b0,... , br-1}. Для каждого элемента bj нужно последовательно составить системы сравнений по модулям bJ, где l = 1, 2,... , tj, а tj — максимальное, для которого найдётся a^, делящееся на bjJ. В эти системы войдут те уравнения fi(x) = 0, для которых число ai делится на bJ. Поднимая по лемме Гензеля решения от системы к системе, получим множество решений по модулю bjJ. Найдя такие решения для каждого bj, применим китайскую теорему об остатках, чтобы получить решения вида x mod П bjJ. Каждое такое решение будет решением исходной j системы. Построение взаимно простой базы применяется и в других приложениях, например в задачах нахождения алгебраических зависимостей среди радикалов [2], вычисления нормальных базисов в расширениях полей [3] и др. [4]. В работе [4] Д. Бернштейн предложил алгоритм построения взаимно простой базы с некоторыми дополнительными свойствами, называемой естественной взаимно простой базой. Ниже предлагается подход к построению взаимно простой базы для специального случая. Подход эффективен, когда заранее известно, что нетривиальная часть взаимно простой базы (элементы, отличные от 1 и не содержащиеся в S) достаточно мала. Метод состоит в том, чтобы быстро отбросить элементы s Е S, такие, что (s, s') = 1 для любого s' Е S, s' = s. Для остальных чисел можно применить известные алгоритмы построения взаимно простой базы. С помощью известного алгоритма вычисления НОД слиянием можно проверить, являются ли все элементы множества S взаимно простыми. Данный алгоритм заключается в вычислении наибольших общих делителей в дереве произведений элементов множества S. С помощью небольшой модификации можно получить алгоритм 1 для выявления элементов s Е S, имеющих нетривиальный НОД с некоторым элементом из S \ {s}. Везде далее через lg обозначен логарифм по основанию 2. Алгоритм 1 Вход: S = {a0,... , am-1} —множество различных n-битовых натуральных чисел (для упрощения m — степень двойки) Выход: T — подмножество S, такое, что для любого s Е T и для некоторого s' Е S, s' = s, выполняется условие (s, s') > 1. 1: Для всех i = 0,... ,m - 1 ai ^ ai. 2: Для всех i = 1, 2,..., lg m 3: Для всех j = 0,1,..., 2lg m-i - 1 4: d ^ (a'2j ,a'2j+1). 5: Если d = 1, то 6: Для всех l = j 2i,j 2i + 1,..., (j + 1)2i - 1 7: Если (d, ai) = 1, то T ^ T U{ai}; 8: aj ^ a2j ' a2j+1. 9: Вывести T Важное свойство алгоритма 1 заключается в том, что в памяти нужно хранить только текущий уровень дерева, а не всё дерево. Отсюда следует, что алгоритму 1 требуется O(mn) битов памяти. Трудоёмкость алгоритма складывается из трудоёмкости вычисления дерева наибольших общих делителей (O(mn lg m lg2 (n^/m) lglg(mn)) битовых операций) и трудоёмкости всех вызовов цикла в строках 6 и 7 (O(kmnlgmx х lg(kn) lglg(kn)) битовых операций, где k = |T|). Несложно видеть, что при k < lg2(mn) трудоёмкость описанного алгоритма не превосходит оценки трудоёмкости алгоритма Бернштейна в O(mn lg m lg (nm) lglg(mn)) битовых операций. Известен ещё один подход к выявлению множества T, вытекающий из работы [5]. m- 1 Вычисляется произведение U = П ai с помощью дерева произведений. Затем вычисi=0 ляются величины bi = U mod a2, i = 0,... ,m-1, с помощью дерева остатков. На выход подаются те числа ai, для которых (bi/ai,ai) = 1. Трудоёмкость построения деревьев произведений и остатков оценивается в O(mn lg m lg(nm) lglg(mn)) битовых операций. При этом построение дерева остатков требует O(mnlgm) битов памяти, что в lgm раз больше, чем требуемая память для алгоритма 1.

Скачать электронную версию публикации