News

1. News
2. 2016
3. January
4. What’s all the fuss about primes?
News from City, University of London

# What’s all the fuss about primes?

Senior Lecturer in Mathematics, Dr Olalla Castro-Alvaredo, discusses the discovery of the largest prime number and its implications for secure internet transactions. She also shares information about her favourite equation, the logistic map.

Using freely available software in their search for prime numbers, the collaborative project of volunteers known as the Great Internet Prime Search (GIMPS), has identified the largest known prime number ever found.

The number is 22m digits long and almost unimaginable.

Dr Olalla Castro-Alvaredo, Senior Lecturer in Mathematics in City’s Department of Mathematics, says there are two reasons why anyone should be interested in identifying very large prime numbers. First, because there is always value in learning something new, and secondly, because a knowledge of large primes has significant technological applications.

Finding new primes is no mean feat

She says the simple property or attribute of prime numbers - whole numbers that are only exactly divisible by 1 and by themselves - means that every whole number is either a prime or can be written as a product of primes:

“Prime numbers are the building blocks of all whole numbers, hence their central role in Mathematics. Unfortunately, there are still many things we do not know about the primes. At a basic level, the main problem is that we do not know exactly how the primes are distributed among other whole numbers and so ﬁnding new large primes is no mean feat.”

Fundamental technological implications

The knowledge of large prime numbers, Dr Castro-Alvaredo goes on to point out, has fundamental technological applications in the all-important area of cryptography, the science of data encryption and secure information transfer:

“Every time we send an e-mail, purchase something on the internet or do internet banking our data undergoes a process of encryption which ensures that such communications are secure. One the most widely used processes is the RSA cryptosystem, named after Rivest, Shamir and Adleman who proposed it in the 1970s. The RSA cryptosystem is extremely efficient and secure.”

She illustrates the point as follows:

“The success of the RSA protocol is founded on a simple characteristic which can be understood by this example. Suppose I gave you two prime numbers, 23 and 71. If I asked you to multiply these two numbers you would be able to do that easily and the result is 1633. Suppose, however, that I asked you to do the opposite, namely I give you a number (say 1763) and I tell you this is the product of two prime numbers and ask you to ﬁnd those primes. If you try to solve this problem you will quickly realise that it takes a lot longer to ﬁnd the primes whose product gives a certain number than to carry out the product if you know the primes. The larger the numbers involved are, the more extreme this asymmetry becomes.”

Primes as the basis of the decryption process

Encryption using the RSA cryptosystem uses a large whole number as an input which is the product of two primes.

Though the large whole number is public knowledge, its prime factors are kept secret and are only known to the individuals or institutions for whom the information is intended. The knowledge of the two primes is the basis of the decryption process and therefore only the intended recipients can decrypt the information. Even if the encrypted information gets intercepted along the way, it cannot be decrypted without knowing the original two primes and, as we have seen, the fact that their product is known does not assist us.

Dr Castro-Alvaredo, a theoretical physicist working in Quantum Field Theory (QFT) recently shared her thoughts on the logistic map, her “most beautiful equation”, in a BBC feature article. This equation can be used to model a variety of natural processes such as the way a population of animals grows and shrinks over time.

Definition
Quantum Field Theory

Quantum Field Theory is the application of quantum mechanics to physical systems described by fields, such as electromagnetic fields, developed to make quantum mechanics both consistent with the theory of special relativity and more readily applicable to systems involving many particles or the creation and destruction of particles.