2021, an unremarkable number

2021-01-04 | Return to Park |

Author | Ni Yi Professor, Department of Mathematics, California Institute of Technology

Source: Pulin Tigers

The ups and downs of 2020 are finally over, and 2021 will come to the world. According to the author's practice of participating in mathematics competitions in middle school, I always analyze the nature of the number 2021, in case there is a problem containing this number in the competition. Like 1997In the 2008 International Mathematical Olympiad, 1997 appeared in the fourth question.

In 1997, the fourth question of IMO, interested readers can do it. However, compared with 2020, 2021 is really an ordinary number.

2020 has many interesting splits, such as the sum of 5 404s. A reader asked: "What does 404 mean?" Well, everyone should often see 404 pages, right?

2020=1024+996, so the Codenong Festival on October 24, 2020 has a special meaning.

For 2021, the author has not yet found such a split, should I use 2021=1024+997? That would be too desperate!

Prime and semi-prime numbers

If the division fails, then try factoring? We know that if the factor of an integer greater than 1 is only 1 and itself, then the number is called a prime number also called a prime number. 2, 3, 5, 7It is the smallest prime number, and 1997 is also a prime number. Prime numbers are the basic objects studied in the branch of mathematics "number theory" and have important meanings in mathematics. If 2021 is a prime number, then it is mathematically interesting. ButUnfortunately,

So it is not a prime number. In the above multiplication formula, 43 and 47 are both prime numbers. If a positive integer is the product of two may be the same prime numbers, then the positive integer is called a semiprime.So 2021 is a "semi-prime number." There are many problems related to prime numbers in number theory. For example, the famous Goldbach conjecture, the content is that any even number greater than 4 can be written as the sum of two prime numbers. If two prime numbersIf they differ by only 2 from each other, then they are called a pair of twin primes. For example, 1997 and 1999 are a pair of twin primes. The twin prime conjecture asserts that there are infinite pairs of twin primes.

Zhang Yitang made a major breakthrough in the conjecture of twin primes丨Picture source: Peking University News Network Sometimes, mathematicians cannot prove their conjectures about prime numbers, so they just step back and see if they can prove the corresponding conclusions about semi-prime numbers.The most famous example is Chen Jingrun’s work on Goldbach’s conjecture, which is usually recorded as "1+2". Its mathematical meaning is: any even number greater than 4 can be written as the sum of two numbers, one of which isPrime number, the other number is prime or semi-prime. What the public doesn’t know is that Chen Jingrun has similar results on the twin prime conjecture. He proved that there are infinitely many prime numbers, so that the prime number plus 2 becomes a prime number orSemi-prime.

Famous mathematician Chen Jingrun丨Source: Xinhuanet

One property of a semi-prime number is that if it is written as the product of two integers greater than 1, then this multiplication is unique regardless of the order. Readers can think about it, except for semi-prime numbers,Is there any other integer with this property? In 1974, people used the Arecibo radio telescope to send a piece of information with a total of 1679 bits to the M13 Hercules globular cluster. The first step in deciphering the Arecibo information,Just notice that 1679 is a semi-prime number, so the information can be formed into a 73×23 rectangle.

Arecibo information includes numbers from 1 to 10, DNA, human and solar system information, and even the image and diameter of the Arecibo telescope itself. 丨Source: Wikipedia

Ulam spiral

The two prime factors of 2021 itself are 43 and 47. If you are an amateur number theory enthusiast like the author, you can probably recognize them at a glance. They are among a series of prime numbers that can be generated by polynomials discovered by Leonhard EulerThe two. Euler noticed in 1772, for the quadratic polynomial

When n is taken

0, 1, 2, 3, ……, 39

When the value is obtained

41, 43, 47, 53, ……, 1601,

All are prime numbers. This fact can be represented intuitively by the Ulam spiral below. Starting from 41, write the natural numbers in a counterclockwise spiral on graph paper, and then mark all the prime numbers in it.We will find that there are many prime numbers consecutively arranged on the diagonal line from the upper right to the lower left containing 41.

The Ulam spiral starting from 41, the prime number is marked in blue, and the square of the prime number is marked in green. 丨Source: Twitter account Fermat's Library

Note: Stanislaw Ulam is a Polish-Jewish mathematician who immigrated to the United States on the eve of the Nazi invasion of Poland. He participated in the Manhattan Project for the development of the atomic bomb and played a key role in the development of the hydrogen bomb. From the United States, Britain and other countriesThe configuration of the hydrogen bomb was named the Taylor-Ulam configuration. The Ulam spiral was discovered when he was boring while listening to a report at a meeting and doodled on paper.

Euler’s quadratic polynomial cannot always get prime numbers, but many of the following values ​​are still prime or semi-prime numbers:

P44 is our year 2021! It is easy to calculate with a computer, and we will get the first Pn that is neither prime nor semi-prime until n=420:

And in a total of 420 Pn from n=0 to n=419, there are 281 prime numbers and 139 semi-prime numbers. In 1857, Russian mathematician Viktor Bunyakovsky guessed, There are infinitely many positive integers n, so that Pn is a prime number. Bnyakowski actually made this conjecture for more general polynomials. This conjecture has not yet been proven. In 1978, PolandThe mathematician Henryk Iwaniec proved that there are infinitely many positive integers n, so that Pn is prime or semi-prime. Iwaniec proved this conclusion for general quadratic polynomials.

Ivanick took over the 2015 Shaw Prize in Mathematics from Chief Executive Liang Zhenying丨Source: Shaw Prize

RSA public key password

So, why do mathematicians study prime numbers or semi-prime numbers? What do they have to do with our lives? Can they be eaten? The answer is that they do have a close relationship with our lives. We can open online banking today by giantsCut leeks, make online shopping on Double Eleven, and even browse the Internet. You have to thank prime numbers and semi-prime numbers. The reason is that it uses the following properties: it is easy to multiply two numbers, and it is easy to break a number into a product.It is difficult. We can look at the example of 2021. If you want to calculate 43×47, students in the third and fourth grades of elementary school can easily calculate the result to be 2021. But if you don’t know any of these factors, you have to find out which two are 2021.The product of numbers is not so easy.

Another famous example is decomposition

In 1903, the American mathematician Frank Nelson Cole gave a speechless "lecture" at a meeting of the American Mathematical Society. He silently walked to the podium and used chalk to calculate on the blackboard

Then he continues to calculate

The result is the same as before. His silent speech won a standing applause from the audience. Someone asked him how he found this decomposition, and he said: "All Sundays in three years."

Cole丨Source: Wikipedia

Actually, calculation

A careful person can figure it out in five minutes at most, but it took Cole more than a hundred days to find such a decomposition. Cole's name is used to name the highest award of the American Mathematical Society in number theory and algebra., Zhang Yitang and Xu Chenyang won these two Cole Awards respectively Today, 2021 can be easily decomposed with an ordinary computer

But if the number is larger, the decomposition is still very difficult. For example, if we multiply two prime numbers with more than 300 digits, we can quickly calculate the result with an ordinary computer. But if we only give you the result of this product, we don’t know any factorIn the case of, it takes many years to decompose even using a supercomputer. This feature of large number decomposition is used by cryptographers to design public key cryptography. Cryptography often appears in various film and television literature works, such as Sherlock HolmesThe dancing villain in the story. In this story, there is a key that corresponds to the English letters one by one to various dancing villains in different forms.

Holmes and Watson are studying the password of the dancing villain丨Source: TV series "Sherlock" has two steps in the process of password transmission that require the use of a key. One is that the sender encrypts normal information so that others cannot understand it.The other is that the recipient decrypts this piece of information that is not understood by others into normal information. Early passwords used by people were symmetrical passwords, and the same key was used for encryption and decryption. If you know how to encrypt,Naturally know how to decrypt; the reverse is also true, know how to decrypt, naturally know how to encrypt.

Dancing villain key丨Picture source: The symmetrical password is suitable for one-to-one communication, but it is very inconvenient in the case of many-to-many communication. For example, Zhang San, Li Si, Wang WusanIndividuals use the same password to communicate with each other, but sometimes Zhang San wants to communicate with Li Si alone, and the content does not want Wang Wu to know. At this time, it is not appropriate to use the same password before, and only start a new set of new ones.Password. This is just three people communicating with each other. It will be more troublesome if billions of people around the world communicate with each other. Public key passwords are designed to solve this problem. In public key passwords, each user is assigned two sets of passwords.Key, a set of encryption keys, and a set of decryption keys. The encryption key is open to everyone, and the decryption key is only known to the user. If Zhang San wants to send a message to Li Si, he only needs to use Li SiEncryption key to encrypt the original information and send the encrypted information to Li Si. Then only Li Siben can use Li Si’s decryption key to decrypt the encrypted information.

Digital signature can also be realized with public key cryptography. For example, when Zhang San sends a piece of information to Li Si, he can first use Zhang San’s own decryption key to process the original information to obtain the encrypted information No. 1, and then use Li Si’sThe encryption key is used to encrypt the encrypted information No. 1 and obtain the encrypted information No. 2. What is actually sent to Li Si is the encrypted information No. 2. After Li Si receives the encrypted information No. 2, he needs to use his own decryption key to decrypt the information 2.Encrypted message No. 1 to get the encrypted message No. 1, and then process it with Zhang San’s encryption key to get the original message. The encrypted message No. 2 sent in this way can only be sent by Zhang San, and only Li Si can interpret it.Yes. So we got Zhang San’s "digital signature" that others could not imitate.

The key to the public key cryptography mechanism is that it is difficult to infer the decryption key from the encryption key. In 1977, three MIT cryptographers Ronald Rivest, AdiShamir, and Leonard Adleman proposed the RSA public key cryptography, which used largeThe difficulty of number decomposition to achieve public key cryptography. Specifically, each user is assigned two large prime numbers. The product of these two large prime numbers ie a "semi-prime number" is disclosed to all users, but only thisThe user himself knows which two prime numbers are. The decryption key needs to know these two prime numbers, and the encryption key only needs to use their product.

1983, Shamir, Rivest, Adleman from left Source: imps.mcmaster.ca In RSA public key cryptography, as long as the two prime numbers used are large enough, the password can be guaranteed to be secure. In the Internet age, publicKey cryptography is widely used in online banking, e-commerce and other scenarios. Readers may notice that in the past, most of the addresses in the browser started with http://, but in recent years, most of the addresses started with http://.In the https protocol, public key cryptography is used, which is more secure than the http protocol. However, in 1994, Peter Shor proposed a Shor algorithm that uses a quantum computer to quickly perform large number decomposition. Once a practical quantum computer is built, RSAPublic key cryptography will no longer be secure. How to design more secure passwords and how to decipher existing passwords has always been a problem that cryptographers have been studying tirelessly, and number theory plays an irreplaceable role in it. Of course, RSA usesThe semi-prime numbers of are all large numbers with hundreds or even thousands of digits, and will not be used as small as 2021. Our year 2021 is still a mediocre number. Hope 2021 will be like this numberNormal, not as thrilling as in 2020.

This article is reprinted from the WeChat public account "Pulin Tigers" with authorization.

Special statement

This article was uploaded and published on Baidu Know Daily from the media, the author, etc. It only represents the author's views, and does not mean that Baidu knows the views or positions of the daily, and knows that the daily only provides an information publishing platform. For cooperation and contributions, please contact zdribao@baidu.com.

+1 Like it Like

Follow the author

Return to Park
Trace to the source and keep clumsy, ask for new ideas

Know the popular articles in daily newspapers

www.knowledge-daily.com e-mail: k@knowledge-daily.com