Минимизируйте остаток в китайской теореме об остатках - PullRequest
Новая
       16

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

4 голосов
/ 28 июня 2011

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

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

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

Комплект 1:

7x + 1
7x + 3

Комплект 2:

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

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

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

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

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

Ответы [ 2 ]

2 голосов
/ 30 июня 2011

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

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

Сначала используйте китайскую теорему об остатках, чтобы найти множество T1 всех 0 <= t <n1 * n2, удовлетворяющих t mod n1 в S1 и t mod n2 == 0 и множество T2 всех 0 <= u <n1 * n2, удовлетворяющих t mod n1 == 0 и t mod n2 в S2. </p>

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

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 <i <= k. Т2 определяется соответственно. Сложность зависит от распределения модулей, но обычно должна составлять примерно квадратный корень из числа возможностей. Существует алгоритм Шропеля и Шамира, который может сэкономить память, но не уменьшает сложность времени. </p>

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

1 голос
/ 28 июня 2011

Пусть наборы будут 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 | в минимальных.

...