Nested Logical Expressions

Hey. In this article I will tell you how you can get very confused. How a few thoughts can capture your head for years, and even affect your life. I’ll tell you how to add and multiply numbers, how to calculate md5, and maybe look for numbers from the Euler hypothesis.

We will perform all operations in logical bits, only we will not calculate them. We will operate only with logical variables, trembling from computational complexity and anticipating infinite expectation. In this world, you feel helpless when you can hardly multiply a couple of ten-bit numbers.

Chapter 1. Addition


So let's go. Let's start with the addition. We represent numbers as a sequence of bits

$ inline $ {a0, a1, a2, a3 ...}, $ inline $
$ inline $ {b0, b1, b2, b3 ...}, $ inline $
$ inline $ {x0, x1, x2, x3 ...}, $ inline $
Where $ inline $ a0, b0 $ inline $- low bits.

Under the variable$ inline $ x $ inline $I mean the result of operations.

Let's try to add these numbers. What will be the zero bit of the sum? If the bits$ inline $ a0 $ inline $ and $ inline $ b0 $ inline $ equal then $ inline $ x0 $ inline $ will be zero, and 1 otherwise, that is $ inline $ x0 = a0 \ XOR \ b0 $ inline $. Further, logical operators will be written easier to save precious Internet space like this:$ inline $ AND \ equiv $ inline $*, $ inline $ OR \ equiv $ inline $+.

Now the first bit. It will depend on the zero bit, if both zero bits are equal to one, then a bit will be added to the first. Call this component the carry bit. In total, we have three components that affect the first bit. it$ inline $ a1, b1 $ inline $ and $ inline $ (a0 * b0) $ inline $.

The first bit will be equal to one if one of these components is equal to one, or all three. This is written like this:

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

Horror. I'm not even sure that I wrote it right now.

I introduced ternary operation for convenience$ inline $ XOR3 $ inline $- it gives one when the odd number of arguments is equal to one.

Next, the second bit. Everything is the same with him - he depends on three components:$ inline $ a2, b2 $ inline $, and the carry bit from the first bit. Now the carry bit of the first bit depends on three components:$ inline $ a1, b1 $ inline $, and the previous carry bit. If two of these three components are equal to one, then the carry bit will also be equal to one. This ternary function is called$ inline $ AND3 $ inline $: it gives one if two of the three bits are equal to one. The formula is simpler:$ inline $ AND3 (a, b, c) = (a * b) + (a * c) + (b * c). $ inline $

Well, the next bits will be determined in the same way as the second bit. In a loop, it looks like this: count the carry bit$ inline $ p (i-1) $ inline $, and consider the result bit $ 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 $
...

Now, we learned how to add numbers.

Here is what the sum of 5-bit numbers looks like
------------ 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

Yes, now this number has one bit more: the sum of the numbers can give one new bit.

But so many members in each bit of the amount
In bit 0: 2
In bit 1: 6
In bit 2: 16
In bit 3: 36
In bit 4: 76
In bit 5: 156
In bit 6: 316
In bit 7: 636
In bit 8: 1276
In bit 9: 2556
At bit 10: 1023

By term, I mean the term after the expression is reduced to the disjunctive normal form (they came up with the same terms), in other words, after reduction to the form, the sum of five bits is written above.

Chapter 2. Multiplication


Chapter Two, Multiplication. We learned to add, so we can and multiply! Yes, a column, as taught at school, only over binary numbers. In a loop, it will look like this: add the second operand, shifted bitwise by$ inline $ i $ inline $ bit, and multiplied in each bit by $ inline $ i $ inline $1st bit of the first operand. Apparently this will look more clearly with pseudo-code:

    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));
    }

Multiplying numbers of length m and n bits will result in a number of length m + n bits.

Simplification of the result of multiplication takes a lot of resources, and looks very polynomial, here is the product of three-bit numbers:

Show
------------ 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

But how many members are in the bits of a 6x6 piece
In bit 0: 1
In bit 1: 4
In bit 2: 13
In bit 3: 41
In bit 4: 168
In bit 5: 656
In bit 6: 791
In bit 7: 778
In bit 8: 606
In bit 9: 402
In bit 10: 240
In bit 11: 135

But this is only one of the options to simplify the cumbersome multi-story expression from multiplication. You may get other values ​​for the high bits, it all depends on how much you can simplify the logical expression.

So, we can add and multiply. We can obtain a recursive formula without special computational costs, which is used to calculate the sum, or the product, or some other composite operation on numbers. But, as it turned out, we cannot simplify this expression for numbers even more than 10 bits in an acceptable time. I hardly managed to simplify the expression for the 8x8 piece.

At this stage, I ran into one of the first troubles. Is it possible, looking at the simplified works of small orders, to find some kind of dependence, and learn to build such a formula.

As a result of addition and multiplication, there must be symmetry with respect to a and b, on the lower bits it is visible to the naked eye, and in order to see it on the highest bits, the eyes must be armed.

So, is it possible to build a formula for the most significant bits of addition / multiplication by looking at the least significant bits? I didn’t succeed, maybe you can do it?

But there is a flip side to the coin: a simplified expression will definitely take up a lot of space, so it simply does not make sense to simplify the product of two 1024-bit numbers. But everyone is interested in multiplying 1024-bit (especially prime) numbers, right? You will have to learn to work with nested logical expressions.

It was not difficult to write some code that operates with logical expressions reduced to a disjunctive normal form, including those embedded in each other. Well, I had to stop drinking, learn to program, quit work, in general, little things.

Chapter Three, the Most Interesting


Take md5 for example. 64 boring about the same round. In calculations, only ordinary logical operators and the above sum are used. Only bits older than 32 are discarded. Well, done, we can calculate md5 using nested bit formulas.

Roughly it looks like this.

For example, md5 provides 128 logical variables. Nested variables I call the variable t, and begin to number after the main ones. In this case, the main variables (those that are fed to the input of the md5 function) from$ inline $ x0 $ inline $ before $ inline $ x127 $ inline $, and nested ones start from $ inline $ t128 $ inline $. Then the first bit of the result will be something like this (it all depends at what points in the algorithm you will fold the expression into a t-variable).

For example,
md5 [0] =
t67168 * t70255 OR
t67167 * t70255 OR
t67163 * t67169 * t70255 OR
! t65928 *! t65929 *! t65930 * t65936 * t67155 * t67169 * t70255 OR
t65929 * t65937 * t67155 * t65 *
285 * t65929 *! t65930 * t65938 * t67155 * t67169 * t70255 OR
t65928 * t65937 * t67155 * t67169 * t70255 OR
t65929 * t65939 * t67155 * t67169 * t70255 OR
t65928 * t65939 * t67155 *
t70 * 65716616 *
561 * t70255 OR
t65937 * t65930 * t67155 * t67169 * t70255 OR
t65930 * t65939 * t67155 * t67169 * t70255

where each t-variable is a different expression.

And at the end of the chain something like this
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

As you understand, the complexity of the md5 function of 128 bits is approximately equal to 70,000. That is, as a result, we get ~ 70,000 t-variables. As it turned out, if you apply 15, 256, 347, or 512 variables to the input, then nesting (that is, the number of t-variables) will be approximately the same. An important reservation must be made here. The operation of creating a t-variable during the calculation of logical expressions is applied after the logical operators$ inline $ AND $ inline $ and $ inline $ AND3 $ inline $after $ inline $ OR $ inline $ and $ inline $ XOR3 $ inline $simplification is performed, I have it like this, therefore, such a result.

So, the nested complexity of md5 is 70K. The resulting formula in t-variables for each bit will be called the logical representation variable.

And now. Now we do the following. We take any hash, and represent it in the form of bits. Where the hash bit is 0, we take the corresponding logical representation variable, where 1 is inverted (operator$ inline $ NOT $ inline $) And add them to the operator$ inline $ OR $ inline $. As a result, we get a new nested logical expression, and equate it to$ inline $ FALSE $ inline $.

What does this expression mean? And it describes all the possible solutions for a given hash. And if you simplify by substituting t-variables, then the solutions will be in full view. That's just to simplify it will not work. At this stage, I had to buy a quality lip-sealer.

Well, we can’t simplify, but it can be at least out of the corner of your eye to peep at least one possible solution ... Indeed, why do we need everything, we need at least one ... And here the most interesting thing begins. We have a logical formula that is equal to$ inline $ FALSE $ inline $. This means that if at some stage of simplifications some member simplifies into$ inline $ TRUE $ inline $then the hash has no solutions. Starting to simplify the expression, you can notice how many members self-destruct, turning into$ inline $ FALSE $ inline $. That is, after substituting the t-variable, something like$ inline $ t67234 \ * \! t67234 * ... $ inline $ That is, if we knew in advance which term is identically equal $ inline $ FALSE $ inline $, we could avoid the computational hell of substituting t-variables in such terms.

So, I solemnly declare. The problem of solving a nested logical expression in terms of computational hell comes down to the definition of terms that are identically equal$ inline $ FALSE $ inline $. That's all. If you do this, you know what will happen. Some cryptographic algorithms will turn into a pumpkin. The nested complexity of multiplying two 256-bit numbers is about 500K, 512-bit 2M, 1024 8M, and so on. Yes, multiplication of numbers turns into the same nested construction, only more complexity.

At this stage, I prettyly patted my lip-sealing machine. I tried a few ideas, but ... all to no avail. So far, no signs have been found by which it is possible to somehow identify false members. Maybe I tried a little. And estimate, it was already somewhere nearby, but I didn’t find it, didn’t reach it, it would be insulting ... But, perhaps, it’s my karma to go half way. Something like that.

PS


A short afterword about what it is in general and what is the point. I honestly say, I have no idea whether all of the above has any scientific meaning, or practical benefit, or something else. I do not have a de facto classical education, and I do all this guided by my considerations, influx, and attitude.

Mazai Banzaev.

Also popular now: