Prime Numbers

Since the dawn of electronic computing, programs for finding primes have been used as a test of the hardware.

A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. The first six primes are 2, 3, 5, 7, 11, and 13. But why? What good are prime numbers?

The problem of distinguishing prime numbers from composite numbers and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic.  It has engaged the industry and wisdom of ancient and modern geometers to such an extent that it would be superfluous to discuss the problem at length…  Further, the dignity of the science itself seems to require that every possible means be explored for the solution of a problem so elegant and so celebrated.

Carl Friedrich GaussDisquisitiones Arithmeticae, 1801

The largest known prime has almost always been a Mersenne prime[2]. The largest known prime number (as of May 2022) is 282,589,933 − 1, a number that has 24,862,048 digits when written in base 10. It was found via a computer volunteered by Patrick Laroche of the Great Internet Mersenne Prime Search (GIMPS) in 2018.

List of Mersenne Known Prime Numbers (c. 500 BCE – 2018 Dec 07)

The project was founded by George Woltman, who also wrote the prime testing software Prime95. The GIMPS project was formed in January 1996. Scott Kurowski wrote the PrimeNet server software that supports the research to demonstrate Entropia distributed computing software, a company he founded in 1997. In 2008, a legal entity was registered to administer GIMPS – Mersenne Research, Inc.

The Electronic Frontier Foundation (EFF) offered $100,000 to the first person(s) who discovered a ten million digits prime. GIMPS claimed this award. The owner of the discovering computer received $50,000 from the GIMPS foundation.

But what about binary you ask? In binary, all prime numbers except 2 begin and end with 1. Some primes have all digits set to 1, so these primes are of the form (2^n)-1 where n is just the number of binary digits. Primes of this form are called Mersenne primes

The twin prime pair (1049,1051) = (10000011001,10000011011) in binary. Now concatenate the binary bit streams to get 1000001100110000011011 = 2149403 and this is also a prime! Primes generating primes!

The first 50 prime numbers in binary

2 10
3 11
5 101
7 111
11 1011
13 1101
17 10001
19 10011
23 10111
29 11101
31 11111
37 100101
41 101001
43 101011
47 101111
53 110101
59 111011
61 111101
67 1000011
71 1000111
73 1001001
79 1001111
83 1010011
89 1011001
97 1100001
101 1100101
103 1100111
107 1101011
109 1101101
113 1110001
127 1111111
131 10000011
137 10001001
139 10001011
149 10010101
151 10010111
157 10011101
163 10100011
167 10100111
173 10101101
179 10110011
181 10110101
191 10111111
193 11000001
197 11000101
199 11000111
211 11010011
223 11011111
227 11100011
229 11100101

Prime numbers in nature

One of the amazing things about mathematics is how its presence can be felt in nature. You find it in the structure of a beehive, in the scales of a pineapple, or even in the petals of a rose. Prime numbers also have an amazing presence in nature. According to scientific research, it was found that cicada insects use prime numbers to come out of their burrows and lay eggs. Cicadas only leave their burrows in intervals of 7, 13, or 17 years. It has been theorized that they use prime numbers so that predators cannot evolve accordingly and prey on them. In other words, these insects use prime numbers to ensure their survival. How incredible is that!

Prime numbers in popular culture

We already know that prime numbers fascinate mathematicians and scientists. However, it has also inspired writers, singers, and other artists. The science fiction and astronomy legend, Carl Sagan, wrote a book titled “Contact” about using prime numbers to communicate with aliens. The Academy Award-winning film, “A Beautiful Mind”, also makes extensive use of prime numbers while telling the story of the gifted economist John Nash. These books and movies prove that prime numbers are a source of inspiration to people outside the realm of science and mathematics.

Finding the two prime numbers is very hard when you have a number that is the product of two primes. This problem is called prime factorization and finding an algorithm that does this quickly is one of the biggest unsolved problems in computer science.

So, if passwords or security numbers are made to be long and complex, and the product of two prime numbers, it could take the fastest computer in the world decades to decode the information behind it. This gives online security firms the time they need to protect your data and apprehend criminals.

Encryption[1] is also the lifeblood behind all sorts of online monetary transactions. Briefly, prime numbers protect your money and information from being stolen.

Whether it’s communicating your credit card information to Amazon, logging into your bank, or sending a manually encrypted email to a colleague, we are constantly using computer encryption.

Other uses are that Cicadas time their life cycles by them, modern screens use them to define color intensities of pixels, DVD makers used them to encrypt their products (illegal prime[3]), and manufacturers use them to get rid of harmonics in their products.

There are a few who seek primes just for the money. There are prizes for the first prover ten-million digit prime ($100000), the first hundred-million digit prime ($150000), and the first billion digit prime ($250000). Look at the incredible size of these giant primes! Those who found them are like athletes in that they outran their competition. If we lose the desire to do better, will we still be complete?



Footnotes
  1. In cryptography, encryption is the process of encoding information. This process converts the original representation of the information, known as plaintext, into an alternative form known as ciphertext. Ideally, only authorized parties can decipher a ciphertext back to plaintext and access the original information. Encryption does not itself prevent interference but denies the intelligible content to a would-be interceptor. For technical reasons, an encryption scheme usually uses a pseudo-random encryption key generated by an algorithm. It is possible to decrypt the message without possessing the key, but considerable computational resources and skills are required for a well-designed encryption scheme. An authorized recipient can easily decrypt the message with the key provided by the originator to recipients but not to unauthorized users. Historically, various forms of encryption have been used to aid in cryptography. Early encryption techniques were often used in military messaging. Since then, new techniques have emerged and become commonplace in all areas of modern computing. Modern encryption schemes use the concepts of public-key and symmetric-key. Modern encryption techniques ensure security because modern computers are inefficient at cracking the encryption. [Back]
  2. In mathematics, a Mersenne prime is a prime number that is one less than a power of two. That is, it is a prime number of the form Mn = 2n − 1 for some integer n. They are named after Marin Mersenne, a French Minim friar, who studied them in the early 17th century. If n is a composite number then so is 2n − 1. Therefore, an equivalent definition of the Mersenne primes is that they are the prime numbers of the form Mp = 2p − 1 for some prime p. The exponents n which give Mersenne primes are 2, 3, 5, 7, 13, 17, 19, 31, … and the resulting Mersenne primes are 3, 7, 31, 127, 8191, 131071, 524287, 2147483647, … Numbers of the form Mn = 2n − 1 without the primality requirement may be called Mersenne numbers. Sometimes, however, Mersenne numbers are defined to have the additional requirement that n be prime. The smallest composite Mersenne number with prime exponent n is 211 − 1 = 2047 = 23 × 89. Mersenne primes were studied in antiquity because of their close connection to perfect numbers: the Euclid–Euler theorem asserts a one-to-one correspondence between even perfect numbers and Mersenne primes. Many of the largest known primes are Mersenne primes because Mersenne numbers are easier to check for primality. As of October 2020, 51 Mersenne primes are known. The largest known prime number, 282,589,933 − 1, is a Mersenne prime. Since 1997, all newly found Mersenne primes have been discovered by the Great Internet Mersenne Prime Search, a distributed computing project. In December 2020, a major milestone in the project was passed after all exponents below 100 million were checked at least once. [Back]
  3. An illegal prime is an illegal number that is also prime. One of the earliest illegal prime numbers was generated in March 2001 by Phil Carmody. Its binary representation corresponds to a compressed version of the C source code of a computer program implementing the DeCSS decryption algorithm, which can be used by a computer to circumvent a DVD’s copy protection. [Back]



Sources

Prime Pages
Ken’s Blog
Wikipedia


Author: Doyle

I was born in Atlanta, moved to Alpharetta at 4, lived there for 53 years and moved to Decatur in 2016. I've worked at such places as Richway, North Fulton Medical Center, Management Science America (Computer Tech/Project Manager) and Stacy's Compounding Pharmacy (Pharmacy Tech).

One thought on “Prime Numbers”

Leave a Reply

%d