BugTraq.Ru: Факторизация (factoring) и выполнимость (satisfability)

Факторизация (factoring) и выполнимость (satisfability)
lime
Опубликовано: dl, 13.11.04 22:54

Представление.

Факторизация - разложение целого числа на два целых множителя.

Обозначим числа, которыми будем оперировать следующим образом: Z = X*Y.

С самого начала следует определиться с тем, в каком виде следует представить числа. Ответ очевиден - в двоичной. Именно эта система счисления дает желаемые исходные значения логических переменных - нули и единицы.

Заранее договоримся, что исходные числа будем обозначать заглавными буквами, а их разряды - прописными.

Таким образом, исходное выражение Z = X*Y примет вид z₁z₂z₃...z_n = x₁x₂x₃...x_n * y₁y₂y₃...y_n.

Разрядность всех чисел одинакова не случайно. Это единственный способ получить ВСЕ ВОЗМОЖНЫЕ РАЗЛОЖЕНИЯ исходного числа вплоть до тривиального, когда один из сомножителей равен 1. В качестве отступления можно сказать, что в случае, если мы хотим получить все возможный разложения, за исключением тривиального, следует вспомнить, что число 1 - это максимальное число, которое можно записать в двоичном виде одним разрядом. В этом случае исходное выражение примет вид z₁z₂z₃...z_n = x₁x₂x₃...x_n-1 * y₁y₂y₃...y_n-1.

Школа.

Для сведения задачи факторизация к задаче выполнимость следует во-первых разобраться с механизмом произведения двух целых чисел. Для простоты рассуждений и большей наглядности ограничим значения чисел шестью разрядами.


                xxxxxx (x₁x₂x₃x₄x₅x₆)
                yyyyyy (y₁y₂y₃y₄y₅y₆)
           -----------------
                xxxxxx *y₆
               xxxxxx  *y₅
              xxxxxx   *y₄
             xxxxxx    *y₃
            xxxxxx     *y₂
           xxxxxx      *y₁
           -----------------
           00000zzzzzz

В дальнейших рассуждениях будем использовать термины "строка" и "столбец" (по аналогии со школьными). В данном примере индексы разрядов при числах не указаны. Это сделано для того, чтобы "не поехали" те самые "столбцы". Предлагается додумывать их самостоятельно, а для подсказки использовать числа в скобках (справа от множителей).

Как помнится из школы произведение - это множество сложений одного из сомножителей (в нашем случае X), который предварительно умножен на один из разрядов второго сомножителя (y_i) и смещен на соответствующее число разрядов влево.

При суммировании чисел, представленных в двоичной системе действуют следующие правила: число X переписывается в каждой строке в первозданном виде, а разряды числа Y в данном случае являются своеобразной маской для данных строк: если y_i=1, значит X в данной строке записывается "как есть"; если y_i=0, значит значения всех разрядов в данной строке равно 0.

Сведение.

Смысл сведения задачи факторизация к задаче выполнимость заключается в формировании логической формулы, которая будет выполнима тогда и только тогда, когда исходное число - не простое. Т.е. необходимо сформировать такую булеву формулу f(z1, z2, ..., x1, x2, ..., y1, y2, ...), которая будет выполнима, если Z=X*Y. При этом значения переменных найденного выполняющего набора будут являться решением исходной задачи факторизации числа.

Видим, что для реализации произведения логическими средствами следует логически интерпретировать множество сумм с масками, переносы и получаемый результат. Рассмотрим механизм суммирования более детально. Начнем с младших разрядов числа Z. Нам известно значение z₆ (это разряд исходного числа). Оно получается как x₆*y₆ (по построению). Рассматривая все возможные варианты исходных данных и результатов сложения, получаем два правила:
1. Если один из сомножителей равен 0, значит и результат равен 0.
2. Если оба сомножителя равны 1, значит результат равен 1.

Теперь самое время вспомнить задачу, к которой мы собираемся сводить нашу проблему. Задача выполнимость по своей формулировке является множеством ограничений на одновременное появление в выполняющем наборе некоторых значений переменных. Каждый терм формулы задает такое ограничение. Для примера: терм (k₁ or !k₃ or k₇) говорит о том, что никакой выполняющий набор не может содержать одновременно инверсию всех переменных данного терма, т.е. недопустимо !k₁, k₃, !k₇ в одном наборе.

Для сведения сформулированных выше правил произведений к термам формулы необходимо понять, какие значения множителей и результата произведения взаимоисключают друг друга и на этой основе следует сформулировать правила конфликтных ситуаций. В результате получим:
1. Если один из множителей равен 0, то результат не может быть равен 1.
2. Если оба множителя равны 1, то результат не может быть равен 0.

Теперь на основе этих правил запишем явные конфликты с использованием переменных:
1. Запрещены сочетания !x₆ z₆, !y₆ z₆.
2. Запрещены сочетания y₆ x₆ !z₆ .

И в заключение преобразуем каждый выписанный конфликт в терм.
1. (x₆ !z₆), (y₆ !z₆).
2. (!y₆ !x₆ z₆)

К полученным термам остается добавить только значение переменной z₆. Если младший разряд исходного числа имеет значение 1, значит допишем к формуле терм z₆ и !z₆ в противном случае.

Разумеется, для подобного произведения, результат которого известен, нет смысла составлять формулу в подобном виде - она несколько избыточна. Это было сделано для наглядности и понимания. Теперь рассмотрим пример получения термов для второго разряда числа Z.

Сложность заключается в том, что в данном случае мы должны просуммировать два разряда числа X, учитывая их маски. Решая подобную проблему в лоб можно получить довольно громоздкие выражения. Поэтому предлагается следующее. Вводим понятие временной суммы. Это будет некоторая дополнительно введенная переменная, задача которой - хранить временный результат суммирования всех вышележащих разрядов с учетом масок. Будем обозначать такие переменные как t_i.

Итак, имеем (это второй столбец нашей суммы):

               x₅ *y₆
               x₆ *y₅
	      -------
	       z₅
	       p₁

p₁ - это перенос в следующий разряд. Как известно при суммировании такое иногда случается.

1. Вводим переменную t₁. t₁=x₅ * y₆.

2. Вводим переменную t₂. t₂=x₅ * y₅.

3. z₅=t₁ + t₂.

4. p₁=1, если t₁=1 и t₂=1; p₁=0, если t₁=0 или t₂=0

Для первого и второго пунктов термы формируются согласно примеру выше.

Для третьего пункта получим (!t₁ or t₂ or z₅) (t₁ or !t₂ or z₅) (!t₁ or !t₂ or !z₅) (t₁ or t₂ or !z₅)

Для четвертого пункта получим (!t₁ or !t₂ or p₁) (t₁ or !p₁) (t₂ or !p₁).

Для формирования термов для третьего и более старших разрядов действует новое правило: все переносы из предыдущих разрядов рассматриваются в данном столбце как еще одно слагаемое, не имеющее маски. Соответствующим образом строятся термы.

Все множество сформированных термов даст нам логическую формулу, отвечающую тем требованиям, которые мы к ней предъявляли в самом начале, а именно - формула будет выполнима тогда и только тогда, когда исходное число Z - непростое и множество решений данной формулы будет содержать множество разложений исходного числа на множители, которые могут быть сформированы из выполняющего набора подбором соответствующих переменных. Данное следует из построения.

Сложность.

Данное сведение изобилует множеством дополнительно введенных перменных. Делалось это для наглядности и с уверенностью можно сказать, что существует куда более эффективное сведение. В качестве дополнительной информации ниже приводится зависимость размера задачи факторизация и получаемый при этом размер булевой формулы для другого алгоритма.

n Факторизуемое число
vars Количество переменных в формуле
clauses Количество термов в формуле
bits Разрядность факторизуемого числа в двоичном представлении
factors Множители

n vars clauses bits factors

9 35 159 4 3 3
49 70 362 6 7 7
169 117 645 8 13 13
961 176 1008 10 31 31
3721 247 1451 12 61 61
16129 330 1974 14 127 127

3 12 36 2 3
7 17 61 3 7
15 35 159 4 3 5
31 43 204 5 31
63 70 362 6 3 3 7
127 81 427 7 127
255 117 645 8 3 5 17
511 131 730 9 131
1023 176 1008 10 3 11 31

В качестве заключения можно сказать, что различными авторами предложено несколько вариантов подобного сведения. Сложность простых алгоритмов (похожих на предложенный) составляет порядка O(n^2), где n - количество разрядов исходного факторизуемого числа в двоичном представлении. Более изощренные алгоритмы минимизируют сложность до значения O(n^1,5). Показатель степени - константа. Безусловный полином.

lime for bugtraq.ru

обсудить | все отзывы (26)

[12197]