[attach id=634803 size="medium" align="right"]The 2,160-bit public key, in hexadecimal, of a local website that employs the RSA algorithm to encrypt its data. As its name suggests, this number is public information and is downloaded by your web browser and stored on your device as soon as you visit the website.[/attach]
You are given a number n, and you are asked to find the two whole numbers a and b, both greater than 1, such that a times b is equal to n. If I give you the number 21, say, then you would tell me “that is 7 times 3”. Or, if I give you 55, you would say “that is 11 times 5”.
Now suppose I ask you for the two whole numbers, both greater than 1, whose product (multiplication) equals the number 6,436,609. This is a much harder problem, right? I invite you to try to work it out, before you read on.
A prime number is a number that is only divisible by 1 and by itself. The number 21 is not prime, because it is divisible by 3 and by 7. However, the numbers 3 and 7 themselves are both prime. On the other hand, the numbers 21, 55 and 6,436,609 have this thing in common: each of them is equal to the product of two prime numbers.
The problem of splitting up a number into its constituent primes is called the prime factorization problem. It is known that if these prime numbers are large enough, then there is no efficient way of finding them in a feasible amount of time. This fact is the basis of internet security schemes such as the RSA algorithm used to encrypt online bank transactions and social network websites such as Twitter.
Even though the prime factorisation problem for the number 6,436,609 looks difficult, it is a relatively straightforward problem for a computer. Indeed, in 2009, a 512-bit number was factored into its two primes by Benjamin Moody – that is a number having 155 digits! (By comparison, the number 6,436,609 has only seven digits.) It took his desktop computer 73 days to achieve this feat. Later, during the same year, a 768-bit number, having 232 digits, was factored into its constituent primes by a team of 13 academics – it took them two years to do so! This is the largest number that has been factored to date.
Nowadays, most websites employing the RSA algorithm use at least a 2,048-bit (617-digit) number to encrypt data. Some websites such as Facebook and GMail use a different encryption algorithm called ECC (elliptic curve cryptography), which is not based on the prime factorisation problem.
By the way, what are the prime factors of 6,436,609? I will not spoil you with the answer, but I will give you a hint: one of its prime factors has three digits.
Alexander Farrugia is a lecturer at the University of Malta Junior College with a PhD in mathematics and a top writer on the website www.quora.com, where he writes primarily about various aspects of mathematics.
Did you know?
• G. H. Hardy, in his 1940 book A Mathematician’s Apology, wrote: “No one has yet discovered any purpose to be served by the theory of numbers and it seems unlikely that anyone will do so for many years.” Sixty years later, the theory of numbers is at the heart of internet security! Read the main article for more details.
• The sieve of Eratosthenes is an old method used to generate all the prime numbers up to some number N. Essentially, a list of all the numbers from 2 to N is produced, then the first number in this list is placed among the prime numbers and all the multiples of this number are crossed out from the list. This process is repeated until the list is exhausted.
• The number 11 is the smallest so-called repunit prime, whose decimal representation 11 is a string of ones. The next decimal repunit prime is 1,111,111,111,111,111,111, the number represented by a string of 19 ones. This means, for example, that the number 11,111 is not prime. What are the two factors of 11,111?
For more trivia, see: www.um.edu.mt/think.
Sound bites
• The day after Christmas of 2017, a 51-year old electrical engineer from Germantown, Tennessee discovered what, up to this day, is the largest known prime number. Jonathan Pace has been a volunteer of the GIMPS project (Great Internet Mersenne Prime Search) for 14 years, using free software available by GIMPS to search for so-called Mersenne primes. A Mersenne prime is a prime number that is equal to one less than a power of two. For example, 3 and 7 are Mersenne primes, because they are equal to 2x2-1 and 2x2x2-1, respectively. Mr Pace’s Mersenne prime is found by multiplying 77,232,917 twos, and then subtracting 1! This number, if written down, would have a whopping 23,249,425 digits! That is almost a million digits more than the next largest discovered prime, which was discovered in January 2016, also by GIMPS.
• A prime gap is the difference between two successive prime numbers. For example, the numbers 317 and 331 are both prime, but no number in between is prime, so we have a prime gap of 14. By the Prime Number Theorem, the average prime gap between any two consecutive prime numbers among the first n whole numbers is the natural logarithm of n. The merit of a prime gap is thus defined as the prime gap divided by this average prime gap. For example, the merit of the prime gap between 317 and 331 is 2.43, which means that this prime gap is more than twice the average prime gap among those between 1 and 317. In December 2017, the GapCoin network discovered a prime gap of length 8350 following an 87-digit prime. This prime gap has merit 41.94, which means that it is almost 42 times as large as the average prime gap. This is the largest prime gap merit discovered to date.
For more science news, listen to Radio Mocha on Radju Malta 2 every Saturday at 11.05am.