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

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

Multiplication by the method of Russian peasants

If you didn’t know about it before, then this is a rather curious approach to multiplication, which does not require memorizing multiplication tables - for it is enough to have the ability to double and halve whole numbers. It is not very clear how he treats Russian peasants: it seems, the same as the “Danish pastry” to Denmark. This method was known to the ancient Egyptians , who obviously lived much earlier than Russian peasants.
')
The general description of the method is simple, but not too informative. However, let's start with it.

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

Everything becomes much clearer if you give an example. So let's do the multiplication $$$13 \ times 7$. This gives us a table.

$$

$$\ begin {array} {| c | c |} \ hline m & n \\ \ hline 13 & 7 \\ 6 & 14 \\ 3 & 28 \\ 1 & 56 \\ \ hline \ end {array}$$

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

$$

$$7 + 28 + 56 = 91$$

What, as can be easily seen, is the result $$$13 \ times 7$.

Of course, it’s interesting why this mysterious procedure works?

If you look in the left column, and walk up to the top, recording $$$1$when we see an odd number and $$$0$when we meet the even, we get $$$1101$, That is $$$13$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 can see, the duplicate column doubling $$$m$calculates the product $$$m$with the appropriate degree $$$2$therefore their addition with the corresponding odd value in the column $$$n$is an addition $$$m$multiplied by these degrees $$$2$that adds up to $$$m$.

That is, by 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 methods currently studied with columns or tables, but at least it does not need to memorize multiplication tables.

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

Exponentiation by the method of Russian peasants

We will make two small changes to the algorithm; both will only deal with speakers $$$m$.

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

For each row in the table instead of multiplying $$$m$to the appropriate degree $$$2$we will raise it to the appropriate degree $$$2$. Multiplying all of this will give us $$$n ^ m$.

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

$$

$$\ begin {array} {| c | c |} \ hline m & n \\ \ hline 13 & 7 \\ 6 & 49 \\ 3 & 2401 \\ 1 & 5764801 \\ \ hline \ end {array}$$

Multiplying the corresponding members gives

$$

$$5764801 \ times 2401 \ times 7 = 96889010407$$

What is really equal $$$7 ^ {13}$.

But unlike multiplication, this method is not just sufficiently effective: it is very effective.

If we want to find $$$n$in degree $$$m$, then we can do it by multiplying $$$m$number times $$$n$. This is how to calculate $$$m \ times n$by addition $$$m$number times $$$n$: you can do this, but if $$$m$more $$$3$then the time spent can be disposed of with greater benefit.

But thanks to this algorithm, the number of squares needed is a maximum of about $$$3$more digits $$$n$(because the binary representation of the decimal number has approximately $$$3$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 this suits us: the multiplication algorithm allows us to multiply by doubling and adding, and the adapted version allows us to raise the power by squaring and multiplying. Is it a good deal.

Brief introduction to RSA

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

The procedure works as follows: we choose a closed pair of prime numbers $$$p$and $$$q$and tell the world the meaning $$$N = pq$. (Values $$$p$and $$$q$we keep secret: the algorithm is based on the fact that the decomposition problem $$$N$The factors are complex.)

Then we pick the number $$$e$and find $$$d$such that $$$ed$on $$$1$more than a work $$$(p-1) (q-1)$. We inform the world $$$e$. (Number $$$d$we keep a secret. The algorithm is based on the fact that finding $$$d$without knowledge $$$p$and $$$q$is a challenge.)

Now we present the message as an integer. $$$M \ lt N$. Encrypted Message Form $$$E$is the remainder of the division $$$M ^ e$on $$$N$.

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

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

And here there is one problem.

In practice, the values $$$M$and at least or $$$e$, or $$$d$very large. If we have to re-multiply, the universe will die before we finish. This algorithm reduces the amount of work to quite acceptable proportions. Multiplications $$$e$(or $$$d$) reduced to the number of multiplications, which is a small divisor of the number of digits $$$e$(or $$$d$).

But this is not the only problem.

Value $$$M ^ N$almost incredibly large. We will not be able to write it, even if we used to store one digit each elementary particle in the known universe. How does this work?

The answer is again the theory of numbers. 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 some value when divided by $$$N$then you can calculate the whole number and divide it by $$$N$or, which is much more logical, you can break everything up into stages and take the remainder when the processed value exceeds $$$N$. 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 the adapted multiplication according to the method of Russian peasants, but now we can add the final touch - when the square of the number exceeds $$$N$), we will take the remainder of the division by $$$N$.

Let's take a look at how this works, on the example of finding the remainder of the division $$$7 ^ {13}$on $$$59$.

$$

$$\ begin {array} {| c | c |} \ hline m & n \\ \ hline 13 & 7 \\ 6 & 49 \\ 3 & 2401 \ rightarrow 41 \\ 1 & 1681 \ rightarrow 29 \\ \ hline \ end {array}$$

What gives us

$$

$$29 \ times 41 \ times 7 = 8323 \ rightarrow 4$$

And this is actually (fuh!) Is the remainder of the division $$$96889010407$on $$$59$.

But here is an unexpected outcome. This is an exponent algorithm, commonly referred to as exponentiation (repetitive) squaring. In fact, this algorithm (or its small variation) is used in the implementation of public-key cryptography (for example, in RSA), in which the calculation of degrees is used.

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

Thanks

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 I finally realized that the re-squaring algorithm is an adaptation of the multiplication of the Russian peasants, and I realized that it is worth sharing this awareness with readers. Twenty minutes later, Oliver Masters talked about the Fibonacci matrix and mentioned the re-squaring algorithm for raising to the power of the matrix. Fortunately, he did not connect it with the multiplication algorithm. Five minutes later, Colin Wright (@ColinTheMathmo) summarized the reports and mentioned this connection. But by that time I had already decided to write this article anyway, which I did.