Вкладені логічні вирази

Привіт. У цій статті я розповім, як можна дуже сильно заморочити. Як кілька думок можуть захопити голову на роки, і навіть вплинути на життя. Я розповім, як складати і множити числа, як обчислити md5, а може і шукати числа з гіпотези Ейлера.

Ми будемо всі операції проводити в логічних бітах, тільки ми не будемо їх обчислювати. Ми будемо оперувати тільки логічними змінними, тремтячи від обчислювальної складності і смакуючи нескінченне очікування. У цьому світі відчуваєш себе безпорадним, коли насилу вдається помножити пару десяти-бітових чисел.

Глава 1. Додавання
Отже, поїхали. Почнемо зі складання. Числа ми представляємо у вигляді послідовності бітів

$inline${a0,a1,a2,a3...}, $inline$
$inline${b0,b1,b2,b3,...}, $inline$
$inline${x0,x1,x2,x3...}, $inline$
де $inline$a0, b0$inline$ — молодші біти.

Під змінної $inline$x$inline$ я маю на увазі результат операцій.

Давайте ж спробуємо скласти ці числа. Чому дорівнюватиме нульовий біт суми? Якщо біти $inline$a0$inline$ і $inline$ b0$inline$ рівні, то $inline$x0$inline$ дорівнюватиме нулю, 1 в протилежному випадку, тобто $inline$x0 = a0\ XOR\ b0$inline$. Далі логічні оператори будуть записуватися простіше для економії дорогоцінного простору інтернету так: $inline$AND \equiv $inline$*, $inline$OR \equiv $inline$+.

Тепер перший біт. Він буде залежати від нульового біта, якщо обидва нульових біт дорівнює одиниці, то буде додаватися біт до першого. Назвемо цю компоненту біт переносу. Отже, ми маємо три компоненти, що впливають на перший біт. Це $inline$a1, b1$inline$ і $inline$(a0 * b0)$inline$.

Перший біт дорівнює одиниці, якщо один з цих компонентів дорівнює одиниці, або всі три. Це записується так:

$inline$a1*b1*(a0 * b0) + !a1*b1*(a0 * b0) + a1*!b1*(a0 * b0) + a1*b1*!(a0 * b0)$inline$.

Жах. Я навіть не впевнений, що я це правильно зараз записав.

Я ввів для зручності тернарную операцію $inline$XOR3$inline$ — вона дає одиницю, коли непарна кількість аргументів дорівнює одиниці.

Далі, другий біт. З ним все те ж саме — він залежить від трьох компонентів: $inline$a2,b2$inline$, і біта перенесення з першого біта. Тепер біт переносу першого біта залежить від трьох компонент: $inline$a1, b1$inline$, і попереднього біта переносу. Якщо два з трьох цих компонент будуть дорівнюють одиниці, то біт переносу теж буде дорівнює одиниці. Ця тернарная функція у мене називається $inline$AND3$inline$: вона дає одиницю якщо два з трьох бітів дорівнює одиниці. Формула простіше: $inline$AND3(a,b,c) = (a*b) + (a*c) + (b*c).$inline$

Ну а наступні біти будуть визначатися так само як і другий біт. У циклі це виглядає так: вважаємо біт переносу $inline$p(i-1)$inline$, і вважаємо біт результату $inline$x(i)$inline$

$inline$p2=AND3(a2,b2,p1)$inline$
$inline$x3=XOR3(a3, b3, p2)$inline$
$inline$p3=AND3(a3,b3,p2)$inline$


Ось, ми навчилися складати числа.

Ось як виглядає сума 5-бітних чисел------------BIT 0-----------------
!a0*b0 OR
a0*!b0

------------BIT 1-----------------
a0*a1*b0*b1 OR
!a1*!b0*b1 OR
!a0*!a1*b1 OR
a0*!a1*b0*!b1 OR
a1*!b0*!b1 OR
!a0*a1*!b1

------------BIT 2-----------------
a0*a2*b0*b1*b2 OR
!a1*a2*!b0*!b2 OR
!a0*!a1*!a2*b2 OR
!a2*!b0*!b1*b2 OR
!a0*!a2*!b1*b2 OR
!a0*!a1*a2*!b2 OR
a0*a1*a2*b0*b2 OR
a1*a2*b1*b2 OR
a2*!b0*!b1*!b2 OR
!a0*a2*!b1*!b2 OR
a0*a1*!a2*b0*!b2 OR
!a1*!a2*!b1*b2 OR
!a1*!a2*!b0*b2 OR
!a1*a2*!b1*!b2 OR
a0*!a2*b0*b1*!b2 OR
a1*!a2*b1*!b2

------------BIT 3-----------------
a2*a3*b2*b3 OR
a2*!a3*b2*!b3 OR
a3*!b0*!b1*!b2*!b3 OR
!a1*!a2*!a3*!b0*b3 OR
a0*a1*a2*!a3*b0*!b3 OR
!a3*!b0*!b1*!b2*b3 OR
!a0*!a2*!a3*!b1*b3 OR
a1*a3*b1*b2*b3 OR
a0*a2*a3*b0*b1*b3 OR
!a0*!a1*!a3*!b2*b3 OR
!a0*!a3*!b1*!b2*b3 OR
!a0*!a1*a3*!b2*!b3 OR
!a2*!a3*!b0*!b1*b3 OR
a0*a1*a3*b0*b2*b3 OR
a0*a1*a2*a3*b0*b3 OR
a0*a2*!a3*b0*b1*!b3 OR
!a1*!a3*!b1*!b2*b3 OR
!a0*a3*!b1*!b2*!b3 OR
!a2*a3*!b0*!b1*!b3 OR
!a2*!a3*!b2*b3 OR
!a1*a3*!b0*!b2*!b3 OR
a0*!a3*b0*b1*b2*!b3 OR
!a0*!a1*!a2*a3*!b3 OR
!a0*!a2*a3*!b1*!b3 OR
!a1*!a2*!a3*!b1*b3 OR
!a0*!a1*!a2*!a3*b3 OR
!a2*a3*!b2*!b3 OR
a0*a1*!a3*b0*b2*!b3 OR
a1*!a3*b1*b2*!b3 OR
a1*a2*!a3*b1*!b3 OR
a0*a3*b0*b1*b2*b3 OR
!a1*!a2*a3*!b0*!b3 OR
!a1*!a3*!b0*!b2*b3 OR
!a1*a3*!b1*!b2*!b3 OR
a1*a2*a3*b1*b3 OR
!a1*!a2*a3*!b1*!b3

------------BIT 4-----------------
!a0*!a2*!a3*a4*!b1*!b4 OR
!a0*!a3*a4*!b1*!b2*!b4 OR
a3*!a4*b3*!b4 OR
a3*a4*b3*b4 OR
!a0*!a1*!a3*a4*!b2*!b4 OR
a0*a2*!a4*b0*b1*b3*!b4 OR
!a2*!a3*!a4*!b2*b4 OR
a4*!b0*!b1*!b2*!b3*!b4 OR
a0*a1*a2*a3*a4*b0*b4 OR
!a2*!a4*!b2*!b3*b4 OR
!a1*!a2*!a4*!b1*!b3*b4 OR
!a1*a4*!b1*!b2*!b3*!b4 OR
!a1*!a3*!a4*!b0*!b2*b4 OR
a0*a1*a2*a3*!a4*b0*!b4 OR
!a1*!a2*!a3*!a4*!b0*b4 OR
a1*a3*a4*b1*b2*b4 OR
a2*a4*b2*b3*b4 OR
a0*!a4*b0*b1*b2*b3*!b4 OR
!a2*a4*!b0*!b1*!b3*!b4 OR
a0*a4*b0*b1*b2*b3*b4 OR
!a0*!a1*!a3*!a4*!b2*b4 OR
a0*a1*a3*!a4*b0*b2*!b4 OR
a1*a2*a3*a4*b1*b4 OR
a1*a2*!a4*b1*b3*!b4 OR
a0*a2*a3*a4*b0*b1*b4 OR
a2*!a4*b2*b3*!b4 OR
a0*a1*a2*!a4*b0*b3*!b4 OR
!a0*!a4*!b1*!b2*!b3*b4 OR
!a1*!a2*!a3*a4*!b0*!b4 OR
!a0*!a1*a4*!b2*!b3*!b4 OR
!a0*!a1*!a2*!a3*a4*!b4 OR
a0*a1*!a4*b0*b2*b3*!b4 OR
a1*a2*a3*!a4*b1*!b4 OR
a1*a2*a4*b1*b3*b4 OR
!a1*!a2*!a3*!a4*!b1*b4 OR
!a4*!b0*!b1*!b2*!b3*b4 OR
a1*a3*!a4*b1*b2*!b4 OR
a0*a1*a3*a4*b0*b2*b4 OR
!a2*!a3*!a4*!b0*!b1*b4 OR
!a1*!a2*a4*!b0*!b3*!b4 OR
!a0*!a1*!a2*!a4*!b3*b4 OR
!a0*!a1*!a2*a4*!b3*!b4 OR
a2*a3*a4*b2*b4 OR
!a1*!a3*a4*!b1*!b2*!b4 OR
!a3*!a4*!b3*b4 OR
a0*a1*a4*b0*b2*b3*b4 OR
!a1*!a4*!b1*!b2*!b3*b4 OR
!a0*!a3*!a4*!b1*!b2*b4 OR
!a1*!a3*!a4*!b1*!b2*b4 OR
a2*a3*!a4*b2*!b4 OR
!a2*!a3*a4*!b2*!b4 OR
a0*a3*!a4*b0*b1*b2*!b4 OR
a1*!a4*b1*b2*b3*!b4 OR
a0*a3*a4*b0*b1*b2*b4 OR
!a2*!a3*a4*!b0*!b1*!b4 OR
!a1*a4*!b0*!b2*!b3*!b4 OR
!a1*!a2*!a3*a4*!b1*!b4 OR
!a3*a4*!b0*!b1*!b2*!b4 OR
!a1*!a3*a4*!b0*!b2*!b4 OR
!a3*!a4*!b0*!b1*!b2*b4 OR
!a0*a4*!b1*!b2*!b3*!b4 OR
a1*a4*b1*b2*b3*b4 OR
!a0*!a2*a4*!b1*!b3*!b4 OR
!a0*!a1*!a4*!b2*!b3*b4 OR
!a0*!a1*!a2*!a3*!a4*b4 OR
!a1*!a2*!a4*!b0*!b3*b4 OR
!a2*a4*!b2*!b3*!b4 OR
!a0*!a2*!a4*!b1*!b3*b4 OR
!a2*!a4*!b0*!b1*!b3*b4 OR
a0*a2*a4*b0*b1*b3*b4 OR
!a0*!a2*!a3*!a4*!b1*b4 OR
!a3*a4*!b3*!b4 OR
!a1*!a4*!b0*!b2*!b3*b4 OR
a0*a2*a3*!a4*b0*b1*!b4 OR
!a1*!a2*a4*!b1*!b3*!b4 OR
a0*a1*a2*a4*b0*b3*b4

------------BIT 5-----------------
a0*a1*a4*b0*b2*b3 OR
a2*a3*b2*b4 OR
a1*a2*a3*a4*b1 OR
a2*b2*b3*b4 OR
a0*a1*a3*a4*b0*b2 OR
a0*a4*b0*b1*b2*b3 OR
a1*a4*b1*b2*b3 OR
a0*a2*b0*b1*b3*b4 OR
a1*a3*b1*b2*b4 OR
a2*a4*b2*b3 OR
a0*a1*a2*b0*b3*b4 OR
a0*b0*b1*b2*b3*b4 OR
a0*a1*a3*b0*b2*b4 OR
a0*a1*b0*b2*b3*b4 OR
a1*a2*a3*b1*b4 OR
a4*b4 OR
a2*a3*a4*b2 OR
a0*a1*a2*a3*b0*b4 OR
a1*a2*b1*b3*b4 OR
a1*a2*a4*b1*b3 OR
a3*a4*b3 OR
a0*a1*a2*a3*a4*b0 OR
a1*b1*b2*b3*b4 OR
a1*a3*a4*b1*b2 OR
a0*a3*a4*b0*b1*b2 OR
a0*a2*a3*b0*b1*b4 OR
a0*a3*b0*b1*b2*b4 OR
a0*a2*a3*a4*b0*b1 OR
a0*a1*a2*a4*b0*b3 OR
a3*b3*b4 OR
a0*a2*a4*b0*b1*b3

Так, тепер це число має на один біт більше: сума чисел може дати один новий біт.

А от стільки членів в кожному бите сумиВ біті 0: 2
В біті 1: 6
В біті 2: 16
В біті 3: 36
В біті 4: 76
В біті 5: 156
В біті 6: 316
В біті 7: 636
В біті 8: 1276
В біті 9: 2556
В біті 10: 1023
Членом я маю на увазі доданок після приведення виразу в дизъюнктивную нормальну форму (понапридумували ж термінів), простіше кажучи після приведення до виду як вище записана сума по п'яти бітам.

Розділ 2. Множення
Глава друга, множення. Складати ми навчилися, значить вміємо і множити! Так, стовпчиком, як вчили в школі, тільки над двійковими числами. У циклі це буде виглядати наступним чином: до першого операнду додаємо другий операнд, зрушений побитово на $inline$i$inline$ біт, і помножений в кожному бите на $inline$i$inline$-ий біт першого операнда. Мабуть псевдокодом це буде виглядати наочніше:

var big, small // наші числа 
for (int i = 0; i < small.bits.size(); i++ ) {
var big_tmp = big;
for (int j = 0; j < big.bits.size(); j++) {
big_tmp.bits[j] = big.bits[j] * small.bits[i];
}
result = (result + big_tmp.operator_SHIFT_LEFT(i));
}

При множенні чисел довжиною m і n біт вийде число довжиною m+n біт.

Спрощення результату множення займає дуже багато ресурсів, і виглядає дуже многочленно, ось добуток трьох-бітових чисел:

Показати------------BIT 0-----------------
a0*b0

------------BIT 1-----------------
a1*b0*!b1 OR
!a0*a1*b0 OR
a0*!b0*b1 OR
a0*!a1*b1

------------BIT 2-----------------
!a0*!a1*a2*b0 OR
a0*!b0*!b1*b2 OR
a0*!a1*!b0*b2 OR
a0*a1*a2*b0*b1*!b2 OR
a0*!a2*!b1*b2 OR
!a0*a1*!a2*b1 OR
a0*!a2*b0*b2 OR
a0*!a1*!a2*b2 OR
a2*b0*!b1*!b2 OR
a1*!b0*b1*!b2 OR
!a1*a2*b0*!b2 OR
!a0*a2*b0*!b1 OR
!a0*a1*!b0*b1

------------BIT 3-----------------
!a0*a1*b0*b2 OR
a0*a1*a2*!b0*b1*b2 OR
!a1*a2*b1*!b2 OR
a2*!b0*b1*!b2 OR
a0*!a1*a2*b0*!b1*b2 OR
!a0*a1*!a2*b2 OR
a1*!b0*!b1*b2 OR
!a0*!a1*a2*b1 OR
a1*!a2*!b1*b2 OR
a0*a1*!a2*b0*b1*!b2 OR
!a1*a2*!b0*b1 OR
!a0*a1*!b1*b2

------------BIT 4-----------------
!a0*!a1*a2*b2 OR
!a1*a2*!b1*b2 OR
a0*a1*a2*b0*b1*b2 OR
a2*!b0*!b1*b2 OR
!a1*a2*!b0*b2 OR
a0*a1*!a2*!b0*b1*b2 OR
!a0*a2*!b1*b2 OR
a1*a2*b0*b1*!b2 OR
a0*a1*!a2*b0*b1*b2

------------BIT 5-----------------
a0*a1*a2*b0*!b1*b2 OR
a1*a2*!b0*b1*b2 OR
a1*a2*b0*b1*b2 OR
a0*!a1*a2*b0*b1*b2

А ось скільки членів в бітах твори 6x6В біті 0: 1
В біті 1: 4
В біті 2: 13
В біті 3: 41
В біті 4: 168
В біті 5: 656
В біті 6: 791
В біті 7: 778
В біті 8: 606
В біті 9: 402
В біті 10: 240
В біті 11: 135

Але це тільки один з варіантів спрощення громіздкого багатоповерхового вираження від множення. У вас можуть вийти інші значення для старших бітів, все залежить наскільки сильно ви зможете спростити логічний вираз.

Отже, ми вміємо складати і множити. Ми можемо без особливих обчислювальних витрат отримати рекурсивні формулу, за якою вважається сума, або твір, або якась інша складова операція над числами. Але, як з'ясувалося, ми не можемо за прийнятний час спростити вираз для чисел більше 10 біт. Мені насилу вдалося спростити вираз для твору 8х8.

На цьому етапі я зіткнувся з однією з перших проблем. А можливо, подивившись на спрощені твори маленьких порядків, знайти якусь залежність, і навчитися будувати таку формулу.

В результаті додавання і множення повинна бути симетрія відносно a і b, на молодших бітах вона видна неозброєним оком, а що б її побачити на старших бітах очей потрібно озброювати.

Так ось, можливо побудувати формулу для старших біт складання/множення, дивлячись на молодші біти? У мене не вийшло, може вийде у вас?

Але є і зворотна сторона медалі: спрощене вираз точно буде займати багато місця, тому спрощувати добуток двох 1024-бітових чисел просто не має сенсу. Але адже всім цікаво множити 1024-бітні (особливо прості) числа, чи не так? Доведеться вчитися працювати з вкладеними логічними виразами.

Не склало особливих труднощів написати трохи коду, що оперує логічними виразами, наведеними в дизъюнктивную нормальну форму, в тому числі вкладеними один в одного. Ну, довелося кинути пити, навчитися програмувати, піти з роботи, в загальному дрібниці.

Глава третя, сама цікава
Візьмемо до прикладу md5. 64 нудних приблизно однакових раунду. При обчисленнях використовуються тільки звичайні логічні оператори і вказана сума. Тільки біти старше 32 відкидаються. Ну от, готово, ми вміємо обчислювати md5 за допомогою вкладених бітових формул.

Приблизно це виглядає так.

На вхід md5 подамо наприклад 128 логічних змінних. Вкладені змінні я обзываю змінної t, і починаю нумерувати номерами після основних. В даному випадку основні змінні (ті, які подаються на вхід функції md5) від $inline$x0$inline$ і $inline$x127$inline$, а вкладені починаються від $inline$t128$inline$. Тоді перший біт результату буде приблизно таким (все залежить в які моменти алгоритму ви будете згортати вираження в t-змінну).

Наприклад такимmd5[0] =
t67168*t70255 OR
t67167*t70255 OR
t67163*t67169*t70255 OR
!t65928*!t65929*!t65930*t65936*t67155*t67169*t70255 OR
t65929*t65937*t67155*t67169*t70255 OR
!t65928*!t65929*!t65930*t65938*t67155*t67169*t70255 OR
t65928*t65937*t67155*t67169*t70255 OR
t65929*t65939*t67155*t67169*t70255 OR
t65928*t65939*t67155*t67169*t70255 OR
t67162*t67169*t70255 OR
t67166*t70255 OR
t65937*t65930*t67155*t67169*t70255 OR
t65930*t65939*t67155*t67169*t70255

де кожна t-змінна є інший вираз.

І в кінці ланцюжка приблизно такеt219 =
!x6*t139*t217 OR
!x6*t140*t217 OR
t211*!t135*t217 OR
!x6*t211*t217 OR
!x10*t139*t217 OR
!x10*t211*t217 OR
!x8*t211*t217 OR
!x8*t139*t217 OR
!x9*t140*t217 OR
!x8*t140*t217 OR
!x9*t139*t217 OR
!x10*t140*t217 OR
!t135*t140*t217 OR
!x9*t211*t217 OR
!t135*t139*t217

t128 =
x0 OR
x5 OR
x6 OR
x4 OR
x8 OR
x7 OR
x9 OR
x3 OR
x10 OR
x2 OR
x1

Як ви зрозуміли складність функції md5 від 128 бітів приблизно дорівнює 70000. Тобто в результаті ми отримуємо ~70000 t-змінних. Як виявилося, якщо подати на вхід 15, 256, 347, або 512 змінних, то вкладеності (тобто кількість t-змінних) буде приблизно тим самим. Тут потрібно зробити важливе застереження. Операція створення t-змінної під час обчислення логічних виразів застосовується після логічних операторів $inline$AND$inline$ і $inline$AND3$inline$, потім $inline$OR$inline$ і $inline$XOR3$inline$ виконується спрощення, у мене ось так, тому й такий результат.

Отже, вкладена складність md5 дорівнює 70K. Отриману формулу в t-змінних для кожного біта будемо називати змінної логічного представлення.

А тепер. Тепер ми робимо наступне. Беремо будь-хеш, і представляємо його у вигляді бітів. Там, де біт хеш дорівнює 0, беремо відповідну змінну логічного представлення, там де 1 — обернену (оператор $inline$NOT$inline$). І складаємо їх оператором $inline$OR$inline$. В результаті у нас виходить нове вкладене логічне вираження, і прирівнюємо його до $inline$FALSE$inline$.

Що ж це вираз означає? А воно описує всі можливі рішення для заданого хеш. А якщо спростити, підставляючи t-змінні, то рішення виявляться як на долоні. Ось тільки спростити її не вийде. На цьому етапі мені довелося купувати якісну губозакатывательную машинку.

Ну ладно, спростити не можемо, але може бути хоч краєчком ока підглянути хоч одне можливе рішення… Дійсно, навіщо нам все, нам би хоч одну… І ось тут починається взагалі найцікавіше. У нас є логічна формула, яка дорівнює $inline$FALSE$inline$. Це означає, що якщо на якомусь етапі спрощень якийсь член спроститься в $inline$TRUE$inline$, то геш не має рішень. Починаючи спрощувати вираз, можна помітити, як багато членів самоліквідуються, перетворюючись на $inline$FALSE$inline$. Тобто після підстановки t-змінної виходить щось типу $inline$t67234\ *\ !t67234 * ...$inline$ тобто, якщо б ми заздалегідь знали, який член тотожно дорівнює $inline$FALSE$inline$, ми б змогли уникнути обчислювально пекла за підстановці t-змінних в таких членах.

Отже, урочисто заявляю. Завдання рішення вкладеного логічного виразу в умовах обчислювального пекла зводиться до визначення членів, тотожно рівних $inline$FALSE$inline$. От і все. Якщо це зробити, ви здогадуєтеся що станеться. Деякі криптографічні алгоритми перетворяться на гарбуз. Вкладена складність множення двох 256-бітних чисел — близько 500К, 512-бітних — 2М, 1024 — 8М, і так далі. Так, множення чисел перетворюється в таку ж вкладену конструкцію, тільки складність побільше.

На цьому етапі я неабияк попсував свою губозакатывательную машинку. Я випробував кілька ідей, але… все безрезультатно. Поки не знайшлося ознак, за якими можна хоч якось ідентифікувати false-члени. Може мало старався. А прикиньте, воно було вже десь поруч, а я не знайшов, не дійшов, ось буде прикро… Але, можливо, це моя карма — проходити половину шляху. Ось як-то так.

p.s.

Невелика післямова про те, що це взагалі таке і який у цьому сенс. Я чесно скажу, я поняття не маю, чи має все вищесказане якийсь науковий сенс, або практичну користь, або щось інше. У мене де факто немає класичного освіти, і я все це роблю керуючись своїми міркуваннями, натхненням, і світовідчуттям.

Мазай Банзаев.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.