دانشجویان نقشه برداری دانشگاه خواجه نصیر

مقاله ی داغ داغ

Background

Prime numbers are said to be first studied by ancient mathematicians of Pythagoras’s school, 500BC to 300 BC (O’Connor and Robertson, 2005). In about 300 BC, Euclid’s "Elements IX" proved that there are infinite prime numbers. Euclid also gave a proof of the Fundamental Theorem of Arithmetic which means integers can be written as a product of primes in an essentially unique way. This is one of the first proofs known which uses the method of contradiction to establish a result (O’Connor and Robertson, 2005). By the time 200 BC, the Greek Eratosthenes devised an algorithm for calculating primes called "Sieve of Eratosthenes." After that, there was a long gap in the history when no one seemed to be working on prime numbers. This was during the time period called the Dark Ages.


There are more than 50 types of prime numbers according to the wikipedia website (2006). Among them, The Fermat Primes are prime numbers that take the form 22^n+1. It was named after Pierre de Fermat who first studied them when "n" is a non-negative integer. There is an infinite number of Fermat Primes but only the first twelve numbers have been completely factorized.

At first, many early scientists felt that the numbers of the form 2n-1 were primes for all prime "n" until a mathematician Hudalricus Regius showed that 211-1 = 2047 (23*89=2047) was not a prime number (Dharwadker, 2004). From the further researches, scientists found that some prime numbers take the form 2n-1 and some do not; therefore they are called Mersenne Prime for numbers which take the form of 2n-1. Mersenne primes were named after Father Marin Mersenne, a French monk who wanted to discover which such numbers were actually primes (O’Connor and Robertson, 2005). Three, seven, thirty-one, 127, 2047, 8191, 131071, 524287, 2147483647 and 213466917-1 are some examples of Mersenne Primes. On December 15 2005, scientists found the 43rd Mersenne Prime which is 230,402,457-1 (Caldwell, 2006) .This number is 9,152,052 digits long! This, however, is not the end of prime numbers. Since the number of prime numbers is infinite, scientists are trying to find new Mersenne Primes which are larger than the largest Mersenne primes to date.  


method

Mathematics

Prime numbers are constantly used in mathematics. People may not realize it, but every time they factor a number or simplify a number in any way, they are using prime numbers. There are many examples of ways to use prime numbers in mathematics. Some of them include, but are not limited to: simplifying numbers, factoring, and simplifying equations.

When simplifying a number into its factors, the mathematician is using prime numbers. For example, when factoring the number thirty, its factors are two, three, and five, all of which are prime numbers. If one were to have a composite number in the list of factors, it would be incorrect because any composite number can also be simplified into its (even smaller) prime factors. Simplifying a number into its factors comes into play when factoring equations.

Prime numbers play a huge part in simplifying radicals, fractions, or even equations. When simplifying radicals, it is very important to know the prime factors of the radicand that needs to be simplified in order to be able to represent the number in its smallest form. When simplifying equations, the same principle applies: if one knows the prime factors of the coefficients in the equation, it becomes possible to simplify the equation into smaller pieces.

To prove that there is, in fact, an infinite number of prime numbers, the scientists can use Euclid’s proof by contradiction. Suppose that there is only a finite amount of prime numbers. For this experiment, the researchers will use only six prime numbers, and they are two, three, five, seven, eleven, and thirteen. If these numbers were multiplied together and increased by one (2*3*5*7*11*13+1), the resulting number would be 30,031; which is a prime number by definition; because if 30,031 was divided by all of the known prime numbers (two, three, five, seven, eleven and thirteen), there would always be a remainder. As we know, 30,031 is not; however, a prime number. It is composite because it is divisible by fifty-nine and 509 (both of which are prime numbers). Since fifty-nine and 509 are not in the list of finite primes, and they are in fact prime numbers, it is a contradiction of the possibility of finite primes, because there obviously are more prime numbers than those listed. Thus, the infinitude of primes is proven due to the contradictory outcome of the experiment (Weisstein, 1999).


If a person wants to know a number is prime number or not, he/she can use trial division. For example, if N is the number that needs to be tested, then it can be divided by all prime numbers which are less than or equal to the square root of N. If none of them divide into it evenly, the number is a prime.

For example, the researchers will use N=10. This can be divided by two and three, which are prime numbers less than the square root of ten, two can easily divide ten evenly, thus revealing that ten is not a prime. To produce the prime numbers more efficiently, the researchers created a prime number generator. The following is the JavaScript created for the experiment)

 


 

Results

Public Key Cryptography

One example of the use of prime numbers in real life is Public Key Cryptography. Most encryption methods which can be decrypted require a specific key, which is shared to the receiver of the encrypted message as well as the one who encrypts it. This however, was time-consuming, because the key had to be shared securely (Zimmerman, 1998). This was the conventional method of encryption until public key cryptography was introduced by Whitfield Diffie and Martin Hellman in 1975. Modern evidence shows that the British Secret Service invented it a few years before, but they kept it a military secret (Zimmerman, 1998).

Public Key Encryption is a method of encryption which uses not one, but two keys. The keys are a public key and two private keys. The public key is generated by multiplying the two private keys together. The private keys are two extremely long prime numbers (usually around 100 digits), and when multiplied together; they create a public key which is given to everyone. It is basically impossible to reverse the multiplication of the two private keys because they are prime numbers. (Zimmerman, 1998) If they were composite numbers (for example), the encrypted data could easily be decrypted by factoring the public key. Since the public key and the private keys are prime numbers, it would take literally centuries for even the fastest computer to calculate the private keys from the public key.

The public key is used by anyone who needs to encrypt a message and send it to the owner of the private key. The public key can only be used to encrypt information – it cannot be used to decrypt it. An "engine" (usually a computer program) uses a certain method to encrypt the data using the public key. The encrypted message is then sent to the owner of the private keys. For the owner of the private keys to be able to read the encrypted message, they must also run the message and their private keys through another "engine". The engine then uses either of the private keys to easily decrypt the data into a human-readable message (Zimmerman, 1998). The picture below illustrates this process.

Example of Public Key Encryption:

Source: /


 

Illegal Prime Number

Recnetly, there has surfaced "illegal prime numbers". An illegal prime is a prime number which is forbidden by law according to Webster’s Dictionary (2000). Its name was coined the "illegal prime number" when Jon Lech Johnansen wrote an illegal program that allowed PCs to circumvent copyright protecting software on DVDs. The picture below shows a model of a DVD and how the filming industry uses binary prime numbers to protect the copyrighted software. To encode the program, a mathematician named Phil Carmody found a prime number that in binary ended in that string. It is supposedly the tenth largest prime number ever found, and it is 1401 digits long. Since then, it became popular because it has a program that is useful and has a totally illegal program embedded inside it in a way that is not too difficult to decrypt (Leeper, 2006).


In Nature

Believe it or not, humans are not the only ones with uses for prime numbers. Animals in the wild also have uses for them. For example, the cicada - a small grass-hopper-like insect, (illustrated below) - has a very unique lifestyle. It spends most of its life in the ground, and only comes out every few years to eat, have a good time, and reproduce. The eggs are planted in the bark of the trees only for the babies to hatch. As soon as they hatch, they head back into the ground. Coincidentally cicadas only come out on prime numbered years - usually every seven, thirteen, or seventeen years. The cicada's number-one predator, the cicada killer wasp (also known as the cicada hawk, "killer wasp" was causing panic in some gardens), only comes out every two years. For a cicada to come out on prime-numbered years, strongly reducing the years on which the cicada and the cicada hawk will meet. (Moulds, 1990) For example, suppose a cicada comes out every seventeen years, the cicada and cicada hawk would only meet every thirty-four years! So, prime numbers can save lives. 


Contests Today

Finding the largest prime number has become more of a sport. The Electronic Frontier Foundation (EFF) offers large rewards for the following:

$50,000 to the first individual or group who discovers
a prime number with at least 1,000,000 decimal digits (awarded Apr. 6, 2000)

$100,000 to the first individual or group who discovers
a prime number with at least 10,000,000 decimal digits

$150,000 to the first individual or group who discovers
a prime number with at least 100,000,000 decimal digits

$250,000 to the first individual or group who discovers
a prime number with at least 1,000,000,000 decimal digits

Source: Electronic Frontier Foundation

In by rewarding those who work to solve those problems, the EFF hopes to "kick-start" the technology of cooperative networking and to encourage Internet users to join together in solving mathematical and scientific problems involving massive computation.

Many foundations, groups, and individuals compete in finding the largest known prime number. The GIMPS (The Great Internet Mersenne Prime Search) is a company that distributes a program that enables hundreds of internet users to solve for even larger primes by linking computers across the globe and donating their spare CPU cycles to the GIMPS research (Kurowski, 2000). So far, the GIMPS had found 9 world-record Mersenne prime numbers.


Conclusion

From the research conducted, prime numbers prove to be important in everyday life. One can use prime numbers for solving problems as well as using prime numbers to encrypt secret messages. Prime numbers are used in many places, not just in everyday life, but nature also supports prime numbers by the behavior of some animals and insects. Scientists even use prime numbers for sport in terms of a collection or contests. Prime numbers are not just numbers which are used for factoring, but they play a role in everyday use. While their usefulness may appear to be hidden, they give an efficient way to communicate secretly. While these numbers are hidden, they control the most secretive things and break through the most secretive codes as well.


References 


Rockmore, D (May 28, 2005) – Stalking the Riemann hypothesis: The Quest to Find the Hidden Law of Prime Number. Retrieved July 13, 2006 on the World Wide Web:

http://en.wikipedia.org/wiki/Image:SIGABA-patent.png

O’Connor and Robertson – Prime Numbers

Retrieved March 2005 on World Wide Web: http://www-history.mcs.st-

andrews.ac.uk/HistTopics/Prime_numbers.html

Leeper, M – Illegal Prime Numbers. Retrieved Jan 5 2006 on the World Wide Web:

http://www.sfcrowsnest.com/articles/editorial/2006/nz10127.php

Ken – Ask Dr. Math: Questions and Answer http://mathforum.org/dr.math/

Sautoy, M (2006, March 27). From the Feb/March 2006 issue of seed. Prime

Number Get Hitched on World Wide Web:

http://www.seedmagazine.com/news/2006/03/prime_numbers_get_hitched.php

Brillhart, J., et al., Factorizations of bn±1, b = 2, 3,5,6,7,10,11,12 up to high powers , American Mathematical Society, 1988 [BLSTW88].

+ نوشته شده در  88/08/19ساعت 14:58  توسط نوید جان  |