What is the relationship between multiplication by the method of Russian peasants and modern cryptography? Unlike commonly studied multiplication procedures, it can be easily adapted to calculate degrees, not products; and in some cryptosystems the calculation of degrees is required.

I must admit right away that the article will not be devoted to how Russian peasants managed to exchange information secretly from their landowners.

Multiplication by the method of Russian peasants

If you did not know about it before, then this is a rather curious approach to multiplication, which does not require memorization of multiplication tables - the ability to double and halve integers is sufficient for it. It is not very clear how he relates to Russian peasants: it seems to be the same as the “Danish pastry” to Denmark. This method was known even to the ancient Egyptians , who obviously lived much earlier than the Russian peasants.

A general description of the method is simple, but not too informative. However, let's start with it.

If we need to multiply two integers$$ and $$, then we draw two columns, in the title of one we write $$and in the other - $$. Then we will begin to constantly add new rows obtained by dividing in half$$ (residue discarded) and doubling $$, and stop when in the column $$ will remain $$. Finally, we add all the elements of the column$$where the value $$odd.

Everything will become much clearer if you give an example. So let's do the multiplication$$. It gives us a table

$$

Now we add the right values ​​for which the left values ​​are odd, which gives us

$$

Which, as you can easily see, is the result $$.

Of course, I wonder why this mysterious procedure works.

If you look in the left column, and go to the very top, writing down$$when we see an odd number and $$when we meet even, we get $$, That is $$in binary form (and, of course, this is no coincidence). In fact, this is the standard algorithm for converting numbers to binary form.

Then, as we see, the repeated doubling of the column$$ calculates the product $$ with the appropriate degree $$, therefore, their addition with the corresponding odd value in the column $$ is addition $$multiplied by these degrees $$that gives in total $$.

That is, with this method we can multiply any integers, and moreover, the algorithm is quite effective. It must be admitted that it is not as effective as the commonly studied methods with columns or tables, but at least it does not need to memorize multiplication tables.

This is all pretty sweet, but it is noteworthy that the method can be slightly transformed to perform much more complex calculations, which are very useful in modern cryptography (public key).

Extinction by the method of Russian peasants

We will make two small changes to the algorithm; both will only touch the column$$.

• Instead of doubling, we will square
• Instead of adding at the end, we will multiply.

For each row in the table, instead of multiplying $$ to an appropriate degree $$ we will raise it to the appropriate degree $$. Multiplying all of this will give us$$.

Let's see how it will work with the same values.$$ and $$.

$$

Multiplication of the corresponding members gives

$$

What really equals $$.

But unlike multiplication, such a method is not just effective enough: it is very effective.

If we want to find$$ to the extent $$then we can do this by multiplying $$ times number $$. This is how to calculate$$ addition $$ times the numbers $$: can be done like that, but if $$ more $$, then the time spent can be disposed with greater benefit.

But thanks to this algorithm, the number of required squaring is a maximum of approximately$$ more number of digits $$ (because the binary decimal has about $$times more bits than the decimal number of digits), followed by the same number of multiplications.

Of course, for this we need to be able to multiply, but it suits us: the multiplication algorithm allows us to multiply by doubling and adding, and the adapted version allows us to raise to the power by squaring and multiplication. Is it a good deal.

A brief introduction to RSA

The point of this is that the way to implement RSA public key cryptography (Rivest-Shamir-Adleman) (and some others) implies that we need to calculate degrees to encrypt and decrypt messages.

The procedure works as follows: we select a closed pair of primes$$ and $$, and tell the world the meaning $$. (Values$$ and $$ we keep secret: the algorithm is based on the fact that the decomposition problem $$by factors is complicated.)

Then we pick up the number$$ and find $$ such that $$ on the $$ more than a work $$. We inform the world$$. (Number$$we keep it a secret. The algorithm is based on finding$$ without knowledge $$ and $$is a difficult task.)

Now we present the message as an integer$$. Encrypted Message Form$$ is the remainder of the division $$ on the $$.

Thanks to the magic of number theory (in fact, this is not magic, but Fermat’s little theorem ), the original message will be the remainder of the division$$ on the $$.

In principle, this is enough; there are many other descriptions on the Internet, often illustrated with meanings$$small enough to track all arithmetic calculations.

And here one problem arises.

In practice, the values$$ and at least or $$, or $$very great. If we have to perform repeated multiplication, then the Universe will die before we finish. This algorithm reduces the amount of work to quite acceptable proportions. Multiplications$$ (or $$) are reduced to the number of multiplications, which is a small divisor of the number of digits $$ (or $$)

But this is not the only problem.

Value$$almost unbelievably great. We will not be able to record it, even if we used to store one digit each elementary particle in the Universe known to us. How does this work?

The answer again will be number theory. One of the very convenient properties of calculating residuals is that it does not matter at what stage of the calculations we find them. If we need to know the remainder of a certain value when divided by$$, then you can calculate the whole number and divide it by $$, or, which is much more logical, you can divide everything into stages and take the remainder when the processed value exceeds $$. In the end, we are guaranteed to get the same result.

RSA Russian peasants

So now we see how to calculate the encrypted message. You can use adapted multiplication according to the method of Russian peasants, but now we can add the final touch - when the square of the number exceeds$$), we will take the remainder of the division by $$.

Let's see how this works, using the example of finding the remainder of a division$$ on the $$.

$$

What gives us

$$

And this is actually (Fuh!) Is the remainder of the division $$ on the $$.

But here is an unexpected denouement. This is a degree calculation algorithm, which is usually called exponentiation (repeating) squaring. And in fact, this algorithm (or a small variation of it) is used in the implementation of public-key cryptography (for example, in RSA), which uses degree calculation.

This is what we have come to. The multiplication algorithm, which was used by people who did not know the multiplication tables, turned into an exponentiation algorithm that underlies modern cryptographic methods.

Acknowledgments

At MathsJam Gathering 2017, Helen Smith and Linda Goldenberg made a presentation on multiplication techniques, including the method of Russian peasants. It was then that it finally dawned on me that the re-squaring algorithm was an adaptation of the multiplication of Russian peasants, and I realized that it was worth sharing this awareness with readers. Twenty minutes later, Oliver Masters talked about the Fibonacci matrix and mentioned the re-squaring algorithm to exponentiate the matrix. Fortunately, he did not associate it with the multiplication algorithm. Five minutes later, Colin Wright (@ColinTheMathmo) summarized the reports and mentioned this connection. But by that time, I still decided to write this article, which I did.