Nested logical expressions

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

We will perform all operations in logical bits, but we will not calculate them. We will operate only on logical variables, trembling from computational complexity and anticipating endless waiting. In this world you feel helpless when you hardly manage to 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 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 bits$$ $ inline $ a0 $ inline $ and$$ $ inline $ b0 $ inline $ are equal then$$ $ inline $ x0 $ inline $ will be zero, and 1 otherwise, that is$$ $ inline $ x0 = a0 \ XOR \ b0 $ inline $ . Further, the 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 the bit will be added to the first one. Let's call this component the carry bit. So 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 recorded it right now.

I have introduced ternary surgery for convenience.$$ $ inline $ XOR3 $ inline $ - it gives a unit when an odd number of arguments equals one.

Next, the second bit. With him everything is the same - it depends on three components:$$ $ inline $ a2, b2 $ inline $ , and carry bits 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 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 count 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 $
...

Here, we learned how to add numbers.


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


As a member, I mean the term after casting the expression into a disjunctive normal form (we used the same terms), to put it simply, after reducing it to the form as the sum of five bits is written above.

Chapter 2. Multiplication

Chapter Two, multiplication. We learned how to fold, so we can multiply! Yes, a column, as taught in school, only on binary numbers. In the loop, it will look like this: to the first operand we add the second operand shifted bitwise by$$ $ inline $ i $ inline $ bit, and multiplied in each bit by$$ $ inline $ i $ inline $ bit of the first operand. Apparently the pseudocode will look clearer:

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

When multiplying numbers of length m and n bits, you get a number of length m + n bits.

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



But this is only one of the options for simplifying the cumbersome multi-storey expression from multiplication. You may have other values ​​for the higher bits, it all depends how much you can simplify the logical expression.

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

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

As a result, both addition and multiplication should have symmetry with respect to a and b, it can be seen with the naked eye on the lower bits, and in order to see it on the upper bits you need to arm it.

So, is it possible to build a formula for the higher bits of addition / multiplication, looking at the lower bits? I did not succeed, maybe you will?

But there is a downside: the 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 simple) numbers, isn't it? We'll have to learn how to work with nested logical expressions.

It was not difficult to write a little code that operates with logical expressions given in a disjunctive normal form, including nested ones. Well, I had to quit drinking, learn how to program, quit my job, in general, little things.

Chapter Three, the most interesting

Take for example md5. 64 boring roughly identical rounds. In the calculations, only the usual logical operators and the sum described above are used. Only bits older than 32 are discarded. Well, ready, we can calculate md5 using nested bit formulas.

It looks like this.

At the input of md5, we give for example 128 logical variables. Nested variables I call the variable t, and begin to number the numbers after the main ones. In this case, the main variables (those that are input to 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 approximately the same (it all depends on which moments of the algorithm you will convolve into t-variable).


where each t-variable is a different expression.


As you understand, the complexity of the md5 function from 128 bits is approximately 70000. That is, as a result, we get ~ 70000 t-variables. As it turned out, if we apply 15, 256, 347, or 512 variables to the input, then the nesting (that is, the number of t-variables) will be about the same. Here it is necessary to make an important reservation. The operation of creating a t-variable during the evaluation of logical expressions is applied after 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. For each bit, we will call the resulting formula in t-variables a logical representation variable.

And now. Now we do the following. Take any hash, and present 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 we 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 possible solutions for a given hash. And if to simplify, 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 grip rolling machine.

Well, okay, we can’t simplify, but maybe at least a corner of the eye can look at at least one possible solution ... Indeed, why should we all, we should have at least one ... And here the most interesting part begins. We have a logical formula that is$$ $ inline $ FALSE $ inline $ . This means that if at some simplification stage a member becomes simpler in$$ $ inline $ TRUE $ inline $ , the hash has no solutions. Starting to simplify the expression, you can see how many members self-destruct, turning into$$ $ inline $ FALSE $ inline $ . That is, after substituting a t-variable, you get something like$$ $ inline $ t67234 \ * \! t67234 * ... $ inline $ That is, if we knew in advance which member is identically equal$$ $ inline $ FALSE $ inline $ , we would be able to avoid computationally hell on the substitution of t-variables in such terms.

So solemnly declare. The task of solving a nested logical expression in terms of computational hell is reduced to the definition of terms that are identically equal$$ $ inline $ FALSE $ inline $ . That's all. If you do this, you can guess 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 numbers are 2M, 1024 is 8M, and so on. Yes, the multiplication of numbers turns into the same nested construction, only the complexity is more.

At this stage, I pretty much patted my jerking machine. I tried out a few ideas, but ... all to no avail. There are no signs yet that can somehow identify false members. Maybe I tried a little. And think for it, it was already somewhere nearby, but I did not find it, did not reach it, that would be a shame ... But perhaps this is my karma - to go half the way. Something like that.

PS

A small afterword about what it is and what is the point. I will honestly say, I have no idea whether all of the above has any scientific meaning, or practical use, or something else. I de facto do not have a classical education, and I do all this based on my considerations, influx, and attitude.

Mazai Banzayev.