Вложенные логические выражения

Привет. В этой статье я расскажу, как можно очень сильно заморочиться. Как несколько мыслей могут захватить голову на годы, и даже повлиять на жизнь. Я расскажу, как складывать и умножать числа, как вычислить 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$
…

Вот, мы научились складывать числа.

Да, теперь это число имеет на один бит больше: сумма чисел может дать один новый бит.

Членом я подразумеваю слагаемое после приведения выражения в дизъюнктивную нормальную форму (понапридумывали же терминов), проще говоря после приведения к виду как выше записана сумма по пяти битам.

Глава 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 бит.

Упрощение результата умножения занимает очень много ресурсов, и выглядит очень многочленно, вот произведение трех-битовых чисел:

Но это только один из вариантов упрощения громоздкого многоэтажного выражения от умножения. У вас могут получиться другие значения для старших битов, всё зависит насколько сильно вы сможете упростить логическое выражение.

Итак, мы умеем складывать и умножать. Мы можем без особых вычислительных затрат получить рекурсивную формулу, по которой считается сумма, или произведение, или какая-то другая составная операция над числами. Но, как выяснилось, мы не можем за приемлемое время упростить это выражение для чисел даже больше 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-переменную).

где каждая t-переменная есть другое выражение.

Как вы поняли сложность функции 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.

Небольшое послесловие о том, что это вообще такое и какой в этом смысл. Я честно скажу, я понятия не имею, имеет ли всё вышесказанное какой-то научный смысл, или практическую пользу, или что-то другое. У меня де факто нет классического образования, и я всё это делаю руководствуясь своими соображениями, наитием, и мироощущением.

Мазай Банзаев.

Автор: pokamest_nikak

Источник