Определение нулевых бит задачи 3-выполнимость, ассоциированной с задачей факторизации

Задача выполнимости булевых формул (SAT или ВЫП) занимает центральное место в теории вычислительной сложности, важнейшем разделе математики. В 1971 году С. Кук доказал, что задача SAT, записанная в конъюнктивной нормальной форме, является NP-полной, т. е. другие задачи, лежащие в классе NP, за полиномиальное время сводятся к задаче SAT [1]. В частности, среди таких задач стоит выделить задачи факторизации, дискретного логарифмирования и логарифмирования на эллиптической кривой [2]. В силу того, что в настоящее время неизвестны эффективные алгоритмы решения данных проблем, вышеупомянутые задачи имеют огромное значение в криптографии.

На вычислительной сложности задачи факторизации основан алгоритм RSA, используемый как для шифрования, так и для цифровой подписи. Дискретное логарифмирование лежит в основе протокола Диффи–Хеллмана, позволяющего выработать двум сторонам общий секретный ключ, используя не защищённый от прослушивания канал связи. Также на данной задаче основана электронная подпись ЭльГамаля и криптосистема Мэсси–Омуры [3].

В настоящее время известно и практикуется сведение данных задач к эквивалентным экземплярам задачи SAT [2]. В частности, задача факторизации сводится к 3-SAT. Таким образом, выполняющий набор для 3-SAT будет соответствовать решению эквивалентной ей задачи факторизации, что позволит, в частности, провести атаку на алгоритм RSA [4]. Проблема заключается в том, что в настоящее время неизвестен полиномиальный алгоритм, обеспечивающий поиск решения задачи SAT в приемлемые временные рамки. Экземпляры задачи SAT небольших размерностей могут быть решены переборными методами, однако с увеличением размерности время решения растёт экспоненциально.

Существует множество подходов к разработке алгоритма поиска решения задачи SAT. Один из них основан на усовершенствовании переборных методов, в частности, алгоритм Дэвиса–Патнема– Логемана–Лавленда (DPLL) [5], являющийся модификацией более раннего алгоритма Дэвиса–Патнема, основанного на методе резолюций.

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

К сожалению, далеко не всегда удаётся получить точное решение, однако существует возможность накопления статистических данных с последующим их использованием. В работе [7] приведены результаты накопления и анализа статистических данных, полученных в результате работы гибридного алгоритма поиска приближённого решения задачи SAT.

В данной статье рассматриваются два эвристических способа определения нулевых бит задачи 3-SAT, ассоциированной с задачей факторизации целых чисел. Первый способ является модификацией одного из компонентов гибридного алгоритма – метода последовательных приближений. Второй метод основан на построении симметричной матрицы с диагональным преобладанием, исходя из информации о дизъюнктах, входящих в 3-КНФ.

Полученная в результате тестирования статистика позволяет составить тест для отдельных битов приближённого решения. Так, если для некоторого бита y i частота совпадения с соответствующим битом точного решения довольно велика, то мы можем утверждать, что в результате выполнения предложенных методов y i принимает верное значение, в противном же случае про бит y_i ничего не известно. К сожалению, в силу особенностей выполнения методов речь может идти только об определении нулевых бит.

1.    Предварительные сведения

В работе [7] описывается гибридный алгоритм, состоящий из двух стадий: сегментного генетического алгоритма и метода последовательных приближений. На стадии работы сегментного генетического алгоритма проводится аналогия с живой природой и поиск решения задачи ВЫПОЛНИМОСТЬ производится в соответствии с законами эволюции. На следующей же стадии происходит переход от задачи SAT к эквивалентной непрерывной функции и запус- кается процесс её минимизации. Рассмотрим эту стадию более подробно.

Пусть имеется булева функция, определённая на множестве булевых векторов у = (у1,..., yN):

M

L *( у ) = л G i ( у ),                                (1)

l = 1

где Gi(у) = vqJу), j=1

у-, если переменная у- входит в i-й дизъюнкт непосредственно yJ, если переменная у-

q*,j⁽ У ) =

входит в i-й дизъюнкт с отрицанием ложь, иначе

Необходимо отметить, что данная булева формула имеет единственный выполняющий набор [5, 6].

Перейдём от 3-КНФ к эквивалентной 3-ДНФ:

M

L ( у ) = L *( у ) = v G , ( у ), l = 1

N

^Gi ⁽ у ) = л q , j ⁽ у ) ^и q ,J у ) = q’^у )• J = 1

| 1, если y j = true x , = 1

1 0, иначе

.

Форме L(у) сопоставим функцию F : [0,1]N ^ R+ следующего вида:

M

F ( x ) = £ C , ( x ), i = 1

N где C i ^{( x} ) = П P i , J ^{( x} ) ^и

J = 1

J если qj' у ) = ^у Pi, J ( x ) = 1 (1 - x J )², если q *- ( у ) = y J .

1,

иначе

Дифференцируем F ( x ), тем самым

получая гради-

ент V F , и приравниваем к нулю все его компоненты.

N

( S П (Pk,i(x)) xJ- keT(J) I=1,I^J

N

- S П Pk,I(x) = 0 (J= 1,...N), keH(J) I=1,I*J в которой T(J) = {ke {1,...M}: pk(x) ^ 1} и H(J) = {k e {1,...M}: pkJx) = (1 - xj)2}.

Приводим полученную систему уравнений (4) к виду

A * x = B * ,

где A * - матрица коэффициентов, B * - столбец свободных членов.

Применяя к системе (5) метод последовательных приближений [8], получаем приближённое решение x * = ( x 1 , x ₂,..., x n ). Стоит отметить, что предложенный метод не всегда находит глобальный минимум F ( x ) из-за наличия точек локального минимума, так как траектория, образованная последовательными приближениями, имеет тенденцию сходиться к ближайшей точке локального минимума [6]. В данном случае сходимость к локальному экстремуму происходит за малое количество итераций (эвристически установлено, что в общем случае число таких итераций равняется 6).

При этом точки локального минимума не являются решением задачи ВЫПОЛНИМОСТЬ. Более того, для SAT, ассоциированной с задачей факторизации, почти все компоненты вектора-приближения оказываются равными 0.

Существуют различные способы преодоления локальных экстремумов, например, инвертирование значений случайно выбранной группы бит, метод смены траектории, рестарт [6]. Все вышеперечисленные методы не всегда преодолевают локальный минимум, поэтому поиск точного решения задачи ВЫПОЛНИМОСТЬ может занимать достаточно большое количество времени.

Более экономным по времени выполнения является остановка «на спуске» в локальный экстремум-ловушку, т.е. за одну итерацию до попадания в «овраг». При этом выдерживается общее направление поиска глобального минимума. Точное решение достигнуто при этом не будет, но, проведя серию испытаний, можно с определённой вероятностью гарантировать точное определение отдельных битов. Эвристически получено, что такая точка в большинстве случаев достигается за 6 итераций.

После проведения серии таких испытаний оказалось, что некоторые биты приближённого решения x * = ( x 1 , x ₂,... x n ) с достаточно высокой частотой (больше либо равной 0,9) совпадают с битами точного решения.

• 2.    Метод последовательных приближений с изменением порядка вычислений переменных Рассмотрим модификацию данного способа с целью повысить число верно определяемых бит.

Возьмём перестановку

• ( 1      2 ... n )

• о = 1                           I

• ( о (1) 0 (2) ... о ( n ) )

Очевидно, что подобная операция не изменит множества решений системы (5). Выше было отмечено, что из-за наличия точек локального минимума и тенденции сходимости метода последовательных приближений к таким точкам не всегда удаётся полу- чить точное решение системы (5). Изменение порядка вычислений переменных также ведёт в «овраг», однако если мы снова остановимся в шаге от итерации, ведущей в локальный минимум, то сможем зафиксировать новую точку, которую можно использовать для получения новых данных о совпадении бит приближённого решения с битами точного решения.

Алгоритм 1.1. Определение частот совпадения бит методом последовательных приближений с изменением порядка вычисления переменных.

Входные данные : M - количество экземпляров задачи ВЫПОЛНИМОСТЬ, для которых будет применяться метод последовательных приближений.

Шаг 1 . Положить i = 1.

Шаг 2 . Задать перестановку о , пользуясь одним из известных алгоритмов [9].

Шаг 3 . Произвести переход от задачи ВЫПОЛНИМОСТЬ к задаче минимизации непрерывной функции [3]. На выходе получается система уравнений (5).

Шаг 4. Изменить порядок вычисления переменных в соответствии с перестановкой о .

Шаг 5 . Решить систему (5) методом последовательных приближений, результатом будет вектор-приближение x* _o = ( x 1 , x ₂,..., x n ).

Шаг 6 . Сравнить вектор x 0 с точным решением x T и сформировать множество

А = { j I x 0 ( j ) = x T ( j )}.

Шаг 7 . Положить i = i + 1. Если i <  M , то произвести переход к шагу 1.

Шаг 8 . Вычислить значения v _k , к = 1.. n следующим образом:

1 M

V = 77 Е ^Ind ( А , ^к )’

Mj=1     j где Ind (Aj, к) =

0, к е A j 1, ^{к G А}

Выходные данные: вектор частот

V = ( V 1 , V 2 ,..., V n ).

Конец алгоритма 1.1.

Логичной представляется мысль по увеличению числа путей обхода переменных.

Алгоритм 1.2 . Определение частот совпадения бит путём метода последовательных приближений с использованием заданного числа путей обхода.

Входные данные : N _n - число перестановок.

Шаг 1 . Положить i = 1.

Шаг 2 . Выполнить действия алгоритма 1.

Шаг 3 . Добавить результат работы алгоритма 1 в множество векторов частот V = { V i }.

Шаг 4 . Положить i = i + 1. Если i <  N _n , то перейти к шагу 3.

Выходные данные : множество векторов частот V = { V , }.

Конец алгоритма 1.2.

Пользуясь результатами работы алгоритма 1.2, модифицируем применение метода последовательных приближений к задаче ВЫПОЛНИМОСТЬ.

Алгоритм 2 . Поиск приближённого решения системы уравнений, эквивалентных задаче ВЫПОЛНИМОСТЬ, с использованием множества векторов частот совпадения бит.

Входные данные: множество векторов частот V = {Vi } , полученное в результате выполнения алго- ритма 1.2.

Шаг 1 . Произвести переход от задачи ВЫПОЛНИМОСТЬ к задаче минимизации непрерывной функции.

Шаг 3. Определить функции

Q ⁰( v , , x , ) =

V i , x i = 0

1 - v , , x i = 1

и Q ‘( V i ., x i ) =

[v,,    xi =11

[ 1 - V i , x i = 0

Шаг 4 . Вычислить значения

1 N n                            I N .

z 0 =    Е Q ⁰ V , x j ) и z 1 =    Е q V , x j ),

N n i = 1                          N n i = 1

где j = 1.. n .

Шаг 5. Сформировать компоненты нового при- ближения xj =

1^0)

• 1 1,    ^Zj > Z j I [ 0, иначе

  j = 1.. n .

  
  

Конец алгоритма 2.

Пояснения к алгоритму 2.

• a)    На шаге 3 вводятся две функции: Q ⁰( V i , x i ) и Q ¹( V _i , x i ). Аргументами у них являются частота совпадения i -го бита v i и значение бита, стоящего на той же позиции i , полученное на шаге 2. В зависимости от значения x i эти функции возвращают либо значение самой частоты v i , либо величину 1 - V i . Объясняется это спецификой задачи ВЫПОЛНИМОСТЬ: к примеру, если значением i -го бита оказалась 1, а частота у него 0, то мы с частотой 1 определяем, что данный бит имеет значение 0 (в силу того, что биты могут принимать только два значения - 0 и 1).

• b)    На шаге 4 функции Q ⁰ ( V i , x i ) и Q ¹ ( V i , x i ) используются для подсчёта средней частоты для каждого бита на основании вектора-приближения x = ( x 1 , x ₂,... x n ). Следует обратить внимание на первый аргумент у данных функций V i j . Запись означает, что из множества векторов частот V = { V i } выбрали вектор v i , соответст

вующий перестановке o i . Индекс j означает, что в векторе частот v i выбран бит под номером j .

• c)    На шаге 5 происходит формирование нового приближения в зависимости от того, какая величина больше: z⁰_j или z¹_j . Это можно назвать «принципом голосования».

3.    Диагональный способ определения частот совпадения бит

Данное приближение можно использовать как стартовое для других методов.

Существует альтернативный способ определения частоты совпадения нулевых бит, основанный на сведении задачи SAT к системе линейных уравнений [10].

Пусть дана КНФ:

M

L ( У ) = л C i ,                                        (6)

l = 1

где C i - дизъюнкции вида v q i , j . Здесь q i , j = y j или q i , j = y j . Отметим, что каждой дизъюнкции можно поставить в соответствие число f_i , равное количеству литералов, принимающих значение ИСТИНА.

В применении к 3-КНФ, ассоциированной с задачей факторизации целых чисел, число f_i может принимать значения 1, 2, 3. Значение 1 может быть в 3 случаях, значение 2 – также в 3 случаях, а значение 3 возможно только в 1 случае. Значение 0 приниматься не может, т. к. рассматриваемая 3-КНФ всегда имеет выполняющий набор, а значит, все дизъюнкты имеют хотя бы один литерал, принимающий значение ИСТИНА.

Математическое ожидание f_i равняется 37 • 1 + 37 • 2 + 37 • 3 = 127 . Это число заключено в интервале (1,5;2) , и ближайшее целое число – 2, поэтому сделаем предположение, что в среднем числа f_i принимают значение 2.

На основании 3-КНФ и чисел f_i построим систему линейных уравнений

Bx = g .                                          (7)

Алгоритм 3. Построение системы линейных уравнений на основе 3-КНФ, эквивалентной задаче факторизации целых чисел.

Входные данные: 3-КНФ, состоящая из N переменных и M дизъюнктов.

Шаг 1 . Инициализировать матрицу B и вектор-столбец g нулями.

Шаг 2. Положить i = 1.

Шаг 3. Положить j = 1.

Шаг 4. Ввести функцию sign ( q_{i , j} ) , отвечающую за знак литерала q_{i , j} . Она принимает значение 1, если литерал q_{i , j} входит в дизъюнкцию C_i без отрицания, и -1 в противном случае.

Шаг 5. Обозначить d 1 = q_i , j .

Шаг 6. Положить к = 1.

Шаг 7. Обозначить d ₂ = q_i , k .

Шаг 8. Добавить к элементу b_{d 1, d 2} матрицы B значение sign ( d ₁) * sign ( d ₂) .

Шаг 9. Добавить к элементу g_{d 1} вектор-столбца g значение sign ( d ₁ )*2 .

Шаг 10. Положить к = к + 1. Если к <  3, то перейти к шагу 7.

Шаг 11. Положить j = j + 1. Если j <  3, то перейти к шагу 4.

Шаг 12. Положить i = i + 1. Если i <  M , то перейти к шагу 3.

Выходные данные: матрица B размером N х N и вектор-столбец g размером N х 1.

Конец алгоритма 3.

Поясним работу алгоритма. В цикле i = 1.. M перебираются все дизъюнкты, входящие в 3-КНФ. Для каждого дизъюнкта рассматриваются всевозможные комбинации литералов по два, учитывая порядок. Всего таких пар 9, и для каждой пары литералов ( d ₁ , d ₂) мы добавляем к элементу формируемой матрицы b_{d 1, d 2} значение sign ( d ₁) * sign ( d ₂) . Таким образом, элемент b_{d 1 , d 2} может либо увеличиться, либо уменьшиться на единицу. Заметим, что диагональные элементы матрицы B всегда будут увеличиваться на единицу, в то время как остальные попеременно увеличиваются и уменьшаются на 1. Также данная матрица является симметричной, что видно из алгоритма построения.

После серии экспериментов было установлено, что матрица B обладает диагональным преобладанием и является разреженной.

Например, для 3-КНФ

• ⁽ У 1 ^v У 2 ^v У 3⁾⁽ У 1 ^v У 3 ^v У 4⁾⁽ У 1 ^v У 2 ^v У 4⁾⁽ У 1 ^v У 2 ^v У 4 )

матрица B имеет следующий вид:

( 4 1 0 - 3 )

• ^{1    3}-1 -2

4.    Численные эксперименты

^{0 - 1 2 1}

(- 3 - 2 1 3 J

Обратим теперь внимание на правую часть g , которую необходимо построить синхронно с матрицей B . Она получается путём сложения чисел f_i . Выше было показано, что в среднем f_i принимают значение 2, поэтому будем строить правую часть, прибавляя и отнимая число 2 одновременно с построением матрицы B .

К полученной системе уравнений применяется метод Гаусса–Зейделя, и полученное вещественное решение x = ( x 1 , x ₂,..., x_N ) преобразуется в булево У = ( У 1 , У ₂,... У_N )следующим образом: если | x_i | < 0,1, то у₁ = ЛОЖЬ , и у₁ = ИСТИНА иначе.

Численные эксперименты показали, что вещественные компоненты, для которых | x_i | ≥ 0,1, с большой частотой (≥ 90%) совпадают с соответствующими булевыми компонентами. В остальных же случаях частота совпадения – около 50 %, и мы ничего не можем утверждать.

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

Цель тестирования заключалась в выявлении нулевых бит с высокой частотой устойчивости. Эксперименты проводились на экземплярах 3-КНФ, эквивалентных задаче факторизации. При этом гарантируется, что все 3-КНФ различны и имеют единственный выполняющий набор.

В табл. 1–4 приведены результаты тестирования метода последовательных приближений с изменением порядка вычисления переменных (алгоритм 2 данной статьи) для 3-КНФ, эквивалентных задаче факторизации числа размерности 100, 200, 300, 400 бит соответственно.

Табл. 1. Результаты работы алгоритма 2 для 3-КНФ, содержащей N=14700 переменных и M=58200 дизъюнктов.

Размер факторизуемого числа – 100 бит

Частота совпадения ν	Число верно определённых нулевых бит N 1, удовлетворяющих заданной частоте	Общее число определённых нулевых бит N 2	Отношение N 1 к N 2
0,85	3476	3822	0,909
0,86	3012	3309	0,91
0,865	2735	3008	0,909
0,866	2382	2618	0,9098
0,867	2382	2618	0,9098
0,868	2382	2618	0,9098
0,869	2382	2618	0,9098
0,87	2382	2618	0,9098
0,875	2043	2246	0,9052
0,88	1674	1844	0,909
0,885	1364	1503	0,9075
0,9	598	646	0,925

Для каждой размерности факторизуемого числа n = pq применялось 100 различных путей обхода. В свою очередь, для каждого пути обхода использовалось 400 случайных постановок задачи SAT, полученной применением качественного генератора случайных чисел.

Как видно из полученных результатов, отношение N ₁ к N ₂ остаётся постоянным при увеличении размерности задачи.

В табл. 5 приведено сравнение алгоритма 2 с результатами обычного метода последовательных приближений.

Отношение N 1 к N 2 растёт с увеличением требуемой частоты устойчивости ν , однако в целом можно говорить о лучших результатах метода последовательных приближений с изменением порядка обхода по сравнению с предыдущим способом.

Табл. 2. Результаты работы алгоритма 2 для 3-КНФ, содержащей N=59400 переменных и M=236400 дизъюнктов. Размер факторизуемого числа – 200 бит

Частота совпадения ν	Число верно определённых нулевых бит N 1, удовлетворяющих заданной частоте	Общее число определённых нулевых бит N 2	Отношение N 1 к N 2
0,85	14158	16056	0,8817
0,86	12506	14195	0,88101
0,865	11435	12991	0,8802
0,866	10195	11584	0,88009
0,867	10195	11584	0,88009
0,868	10195	11584	0,88009
0,869	10195	11584	0,88009
0,87	10195	11584	0,88009
0,875	8876	10089	0,8797
0,88	7512	8539	0,8797
0,885	6167	7027	0,8776
0,9	2677	3075	0,8705

Табл. 3. Результаты работы алгоритма 2 для 3-КНФ, содержащей N=134100 переменных и M=534600. Размер факторизуемого числа – 300 бит

Частота совпадения ν	Число верно определённых нулевых бит N 1, удовлетворяющих заданной частоте	Общее число определённых нулевых бит N 2	Отношение N 1 к N 2
0,85	30738	34801	0,8832
0,86	27139	30744	0,8827
0,865	24755	28025	0,8833
0,866	22105	25018	0,8835
0,867	22105	25018	0,8835
0,868	22105	25018	0,8835
0,869	22105	25018	0,8835
0,87	22105	25018	0,8835
0,875	19276	21834	0,8828
0,88	16433	18596	0,8836
0,885	13494	15277	0,8832
0,9	6215	7042	0,8825

Табл. 4. Результаты работы алгоритма 2 для 3-КНФ, содержащей N=238800 переменных и M=952802. Размер факторизуемого числа – 400 бит

Частота совпадения ν	Число верно определённых нулевых бит N 1, удовлетворяющих заданной частоте	Общее число определённых нулевых бит N 2	Отношение N 1 к N 2
0,85	52346	59222	0,8839
0,86	46051	52118	0,8836
0,865	44245	50074	0,8836
0,866	41363	46807	0,8837
0,867	41363	46807	0,8837
0,868	41363	46807	0,8837
0,869	41363	46807	0,8837
0,87	41363	46807	0,8837
0,875	37390	42340	0,8831
0,88	35249	39907	0,8833
0,885	32307	36713	0,88
0,9	10961	12442	0,881

Табл. 5. Сравнение метода последовательных приближений и алгоритма 2

Частота совпадения ν	Число верных нулевых бит N 1 для обычного метода последовательных приближений	Число верных нулевых бит N 2 для метода последовательных приближений с изменением порядка обхода	Отношение N 1 к N 2
0,85	3697	3893	0,9496
0,86	2931	3086	0,9497
0,87	556	577	0,9636
0,88	556	577	0,9636
0,9	556	577	0,9636
0,95	4	4	1

В табл. 6 приведены результаты тестирования диагонального способа для КНФ, эквивалентных задаче факторизации. Здесь под размерностью задачи подразумевается размер факторизуемого числа n = pq .

Табл. 6. Результаты тестирования для диагонального способа

Размерность задачи, бит	Число предположительно нулевых бит N 1	Число верных нулевых бит N 1	Отношение N 1 к N 2
100	4947	4277	0,8645
200	19894	17136	0,8613
300	44828	38942	0,8686
400	79786	68849	0.8629

Данный способ определяет достаточно большое число верных нулевых бит. Сильной стороной данного способа является то, что отношение N ₂ к N ₁ остаётся постоянным с увеличением размерности задачи.

Стоит отметить, что предложенные методы для различных экземпляров SAT определяют с высокой частотой различные нулевые биты. Другими словами, для нулевых бит приближённого решения, полученного вышерассмотренными способами, мы можем утверждать, что они с высокой частотой совпадают с битами точного решения. Про единичные биты мы ничего сказать не можем: они могут как совпадать с точным решением, так и принимать противоположное значение.

Не менее важным вопросом является определение конкретных бит, которые будут совпадать с точным решением для любого экземпляра задачи SAT. Это можно выявить, объединяя данные, полученные для различных постановок SAT. В табл. 7 приведены данные о «пересечении» множеств нулевых бит для различных экземпляров SAT, ассоциированной с задачей факторизации числа размерностью 100 бит. Частота совпадения равняется 0,9, число верно определённых нулевых бит для каждой отдельно взятой задачи равняется 598.

С увеличением числа экземпляров задачи SAT сокращается число общих верно определённых бит, однако в дальнейшем общие биты можно использовать для элиминации (сокращения) 3-КНФ и последующего применения других методов (например, алгоритма DPLL). Рассмотрим ещё одно эвристическое применение полученных результатов. Обозначим через Θ множество общих бит с высокой частотой совпадения.

Табл. 7. Количество общих верно определённых нулевых бит в зависимости от числа экземпляров задачи SAT

Число экземпляров задачи SAT	Число общих верно определённых нулевых бит
350	476
360	476
370	134
380	92
390	15
400	15

Инвертируем все биты множества Θ (т. е. установим значения в 1). Следующим шагом распределим инвертированные биты в векторе z = (zp...., Zn), z, = 0 Vi = 1..N. (8)

Таким образом формируется вектор z % , у которого на некоторых позициях, начиная с номера i = n...N , стоят единичные биты, остальные же места по-прежнему занимают нули. Установим ещё несколько бит на позициях i = n...N в значение 1, причём выбор позиций осуществляется случайным равномерным образом.

Следующим шагом к вектору применяется метод последовательных приближений. По-прежнему выполняется ограниченное число итераций, но при этом значения бит, выбранных на предыдущем шаге, не будут изменяться. В полученном же приближении нас будут интересовать биты, стоящие на позициях, отвечающих битам сомножителей, т. е. биты с индексами i = 1.. n .

Для иллюстрации эффективности данного подхода были проведены тестовые вычисления с приближениями, сформированными на основании имеющегося точного решения. При этом не были использованы биты множества Θ. В табл. 8 представлены данные по выявлению зависимости числа верных бит сомножителей от числа бит, точно задаваемых в позициях с индексами i = 1.. n . Все значения приведены в процентном соотношении.

Табл. 8. Зависимость числа верных бит сомножителей от числа бит, точно задаваемых в матрице умножения (в процентном соотношении)

Процент точно задаваемых бит, исключая биты сомножителя	Процент верных бит, отвечающих за биты сомножителя
0	58
5	65
10	76
12	84
14	87
16	92
20	100

Оказывается, что при числе верно задаваемых бит, равном 20 % от общей длины вектора z , происходит распознавание бит сомножителей с вероятностью 100 %. Важным фактором в работе данного способа является то, что биты распределяются равномерно на позициях i = 1… n .

На практике же, задавая множество бит Θ, удаётся распознать биты сомножителей с вероятностью 6065 %. Происходит это из-за того, что биты множества Θ располагаются концентрированно, неравномерно.

В дальнейшем планируется увеличение данного процента путём повышения мощности множества бит Θ, которые при этом располагались бы равномерно.

Заключение

В статье описаны два эвристических подхода к поиску выполняющего набора для задачи SAT. Первый из них заключается в расширении известного способа минимизации функции путём изменения порядка обхода переменных. Другой метод основан на создании матрицы с диагональным преобладанием, используя структуру 3-КНФ.

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

Работа выполнена при поддержке РФФИ (проект 12-07-00294-а).