Минимизируйте остаток в китайской теореме об остатках

Question

У меня есть несколько наборов, содержащих несколько конгруэнций.

Я пытаюсь найти наименьший остаток при применении китайской теоремы об остатках к одному элементу из каждого набора.

Например с 2 комплектами:

Комплект 1:

7x + 1
7x + 3

Набор 2:

11x
11x + 2
11x + 7
11x + 8

Взятие 7x + 1 и 11x дает 77x + 22.
Я иду после наименьшего остатка (в приведенном выше примере 77x + 8) без необходимости проверять все комбинации.

---

Это очень упрощенная версия моей настоящей задачи (~50 комплектов, ~100 сравнений в каждом).

Я застрял на том, как подойти к этой проблеме, любой совет будет принята с благодарностью.

Кроме того, мои извинения, если моя математическая терминология неверна.

Answer 1

Существует алгоритм встречи в середине, который находит наименьший остаток во времени

O(max(|S1|, |S2|) log(max(|S1|, |S2|))).

Сначала используйте китайскую теорему об остатках, чтобы найти множество T1 всех 0 <= t

Т.е. в примере, приведенном в вопросе:

T1 = {22, 66}

T2 = {0, 7, 35, 63}

Теперь вы ищете искомые суммы (t1 + t2) mod n1*n2 для любого t1 в T1 и t2 в T2. Следовательно, наименьший остаток - это либо сумма двух наименьших элементов в T1 и T2, либо двух элементов, которые едва превышают n1*n2. Если вы сортируете наборы T1 и T2, то лучшее решение для второго случая можно найти, отсканировав первый набор от наименьшего до наибольшего элемента и отсканировав наибольший набор от самого большого до наименьшего элемента, т.е. продвинув позицию в T1 всякий раз, когда сумма меньше, чем n1*n2, и уменьшается позиция в T2, когда она больше, чем n1*n2.

Если у вас есть более двух модулей n1 .. nk, то самое быстрое решение, которое я вижу, это разделить модули на два набора, скажем, n1.. nr и nr+1 .. nk найти множество T1, такое что t в T1, если t mod ni в Si для всех 1 <= i <= r и t mod ni == 0 для всех r

Для вашего приложения, то есть 50 модулей и 100 сравнений, этот алгоритм по-прежнему использует около 100^25 шагов, что недопустимо. К сожалению, похоже, что нет полиномиального алгоритма. В частности, известно, что нахождение наименьшего решения x уравнения x^2 == a (mod n), где n - высокосоставное целое число, является NP-полным. Но поиск такого решения может уменьшить вашу проблему. Следовательно, ваша задача должна быть NP-полной в целом, если только у конгруэнции нет какого-то особого свойства, которое можно использовать.

Answer 2

Пусть наборы будут S1, S2, ... Sk, где модуль в каждом наборе равен n1 > n2 > ... > nk, а оставшиеся в Si - a_i1

Вот псевдокод:

Find the target modulus, i.e. n = lcm(n1, n2, ..., nk)

Convert the sets Si into hashtables, so that you can check if a certain element is in the set or not.

for (int b = 0; b < n / n1; b++)
    foreach (int c in [a_11, a_12, a_13, ...])
        //candidate target reminder
        a = b*n1 + c
        works = true;
        foreach (int ni in [n2, n3, ..., nk])
           //test if there is an element in Si, which gives the correct reminder
           //if not then this candidate doesn't work, go to the next
           if( not Si contains (a % ni))
               works = false;
               break
        if (works)
            print "The solution is n*x+a"
            exit

Идея состоит в том, чтобы искать минимум. Если минимум равен a, то a можно представить как a=x*n1+yгде y - некоторый элемент из S1, поэтому я перебираю все возможности в порядке возрастания. Затем для каждого из них я проверяю по другим наборам - содержат ли они соответствие, удовлетворяемое током a. Скажем для второго набора S2: должно существовать конгруэнция из S2, например, p*n2+q, так что a = p*n2+q для некоторого p. Но это означает, что a % n2 = q (так как q это остаток). Т.е.% n2 должно быть в S2.

Сложность алгоритма O (n/n1 * |S1| * k). Вот почему я выбрал n1, чтобы быть самым большим модулем. Но если вы действительно хотите минимизировать сложность, вы должны выбрать множество Si таким образом, чтобы n/ni * |Si| в минимальной.