Xiao Cha Ming Min was sent from The Temple of OuFei
Qubits reports | Official account QbitAI
Unexpectedly, the legend of the ancient Han Xin Dianbing later inspired computer encryption algorithms.
According to legend, when chu and Han were fighting for hegemony, Han Xin led 1500 soldiers to fight with the Chu army and retreated to the mountain, at this time the enemy army led five hundred horses to kill and rush, and Han Xin quickly ordered troops to meet the enemy.
Han Xin ordered the soldiers to be in a row of 3 people, resulting in 2 more; then ordered the soldiers to be in a row of 5 people, resulting in 3 more; he ordered the soldiers to be in a row of 7 people, and the result was 2 more.
Han Xin immediately calculated that there were still 1,073 people left in the army, and the enemy was less than five hundred, and he was condescending and defeated by the crowd, so he led the army to kill the enemy and fled.
How does Han Xin calculate the number of people, and how does the algorithm behind it affect today's computer field? And look down.
<h1 class="pgc-h-arrow-right" data-track="9" > Han Xin or a mathematician? </h1>
Of course, Han Xin calculated that the number of soldiers was only a legend, and Han Xin himself was not a master of mathematics. This problem first appeared in an ancient book from 1700 years ago, more than 600 years after Han Xin's death.
During the Southern and Northern Dynasties, the Sun Tzu Arithmetic Recorded such a problem. (Note: This grandson is not Sun Wu who wrote "Sun Tzu's Art of War")
The original book says:
There are things that do not know their number, two of the three numbers, three of the five-five numbers, and two of the seven-seven numbers. Q Geometry?
This means that an integer is divided by three remaining two, divided by five remaining three, divided by seven remaining two, and the integer is found.
It is the Chinese surplus theorem, also known as the "Hanxin point soldier" problem.
In modern mathematics, there are few important theorems named after Chinese mathematicians, but such a mathematical theorem has the word "China" in its name.
During the Southern Song Dynasty, The Chinese mathematician Qin Jiushao first gave a solution to such a problem: the Great Yanshu.
It wasn't until 500 years later that the famous mathematician Gauss described similar results in his book.
So the question is: how did the legendary "Han Xin" calculate the number of people?
<h1 class="pgc-h-arrow-right" data-track="20" > solve the problem of "Hanxin Dianbing"</h1>
In order to better understand and express the problem of "Han Xin DianBing", we introduced a new mathematical concept - "tongyu".
Mathematically, if a and b are the same after dividing by the positive integer m, then a and b are said to be the same as the sum of modulo m, and Han Xin Dianbing uses the mathematical formula to express it as (X is an unknown number of people):
X ≡ 2 (vs. 3)
X ≡ 3 (vs. 5)
X ≡ 2 (vs. 7)
To simplify the problem, let's first consider only the first two congruence conditions, and the integers that satisfy division by 3 remain 2 and division by 5 remain 3 are:
2、5、8、11、14、17、20、23、26……
3、8、13、18、23、28、33、38……
It can be seen that the first number that meets both conditions is 8 and the second number is 23. The difference between each subsequent solution and the previous one should be the smallest common multiple of 3 and 5 15, i.e. :
X = 8 + 15K (K is an integer)
Thus we narrow down the solution of the integer we are looking for, and then add a third condition to find the numbers that satisfy X=8+15K and divide by 7 and 2, respectively:
8、23、38、53、68、83、98、113、128……
2、9、16、23、30、37、44、51……
The first number that satisfies the condition is 23 and the second number is 128. The difference between each subsequent solution and the previous one should be the smallest common multiple of 3, 5, and 7 105.
The process of finding a solution is obviously too cumbersome. Later, the Ming Dynasty mathematician Cheng Dawei compiled the solution method into a poem:
Three people walked together seventy thin, five trees plum blossom twenty branches.
The reunion of the seven sons is half a month, except for one hundred and five.
This means:
Multiply the remainder by dividing by 3 by 70, multiply the remainder obtained by dividing by 5 by 21, multiply the remainder obtained by dividing by 7 by 15, add them all together and subtract an integer multiple of 105 or 105, and the resulting number is the answer.
70 × 2 + 21 × 3 + 15 × 2 = 233 - 2 × 105 = 23
The other solutions can only be an integer multiple of 105 different from 23, and Han Xin should have estimated the approximate number of troops, taking the solution of 105 × 10 + 23 = 1073.
How did the above 70, 21, and 15 groups of numbers come from, interested readers can further read the general solution of the "Chinese residual theorem", which will not be repeated here.
This "Hanxin point soldier" problem can not only be used for point soldiers, but also has important applications in the astronomical calendar.
Suppose there is a comet that appears once every 4 years, we saw it in 1991, another comet saw it once every 10 years, and we saw it in 1997. When will we see them next in the same year?
X ≡ 1991 (vs. 4)
X ≡ 1997 (vs. 10)
It has been calculated that the last time they met was in 2007 and reunited every 20 years, so the next time should be in 2027.
Today, the Chinese residual theorem has become the basis for many computer encryption algorithms, and its application scope is beyond your imagination.
<h1 class="pgc-h-arrow-right" data-track="44" > affects today's computer algorithms</h1>
In an article titled "How Ancient War Strategies Affect Contemporary Mathematics", foreign media Quantamagazine also mentioned that the Chinese residual theorem has great enlightenment significance for modern mathematics, computer algorithms, astronomy and other fields.
For example, the very famous RSA encryption algorithm applies the Chinese residual theorem.
We know that in number theory, it is relatively simple to ask for the solution of two large prime numbers, but it is difficult to factorize their products.
The RSA encryption algorithm uses this product as its own encryption key.
Since its inception in 1977, the RSA encryption algorithm has become one of the most widely used public key algorithms.
In addition, the Chinese residual theorem is also applied in the fast Fourier transform (FFT), which can greatly reduce the number of multiplications required to calculate the discrete Fourier transform.
In recent years, the Chinese surplus theorem has also been used in information encryption.
In 2018, columbia university scholars invented a way to encrypt information in text, which applies the Chinese residual theorem to ensure the accuracy of information restoration.
As long as the phone scans a piece of text, the algorithm can give the encrypted information.
This method is called FontCode, which is to make small adjustments to ordinary characters, and then re-encode the information on the adjusted characters to achieve encryption of the information.
For example, the following 5 different colors of "a", which represent 1-5 digital information.
Without color distinction, it is difficult for the naked eye to tell what is the difference between them and regular fonts.
But machines can.
By scanning and analyzing, the algorithm can deduce which letters have been specially processed and what information the processed letters represent.
Therefore, in a seemingly ordinary piece of text, it is possible to hide these special letters well, thus passing an encrypted string of numbers.
Then, these numbers are calculated to arrive at the information you really want to convey.
But this encryption method is not safe enough, after all, when a character appears on the screen or on paper, its format may have some small changes.
This is where the Chinese residual theorem is needed.
As we have already seen above, numerical values can be calculated from a system of linear congruence equations.
If you want to solve for 3 unknowns, you need 3 linear equations to do so.
Now, to be on the safe side, scientists have increased the number of linear equations.
For example, in order to solve 3 unknowns, they will set 5 linear equations, and as long as they know 3 of the 5 equations, they can solve the desired answer.
Obviously, more than 1,000 years later, although we will no longer hide the number of soldiers like Han Xin, researchers in modern mathematics, computers and other fields can still get a steady stream of inspiration from the Chinese residual theorem.
Reference Links:
[1]https://www.quantamagazine.org/how-ancient-war-trickery-is-alive-in-math-today-20210914/
[2]https://www.sciencedaily.com/releases/2018/05/180510150231.htm
[3]http://www.xinhuanet.com/science/2018-08/07/c_137372635.htm
— Ends —
Qubit QbitAI · Headline signing
Follow us and be the first to know about cutting-edge technology developments