Threading Through Math History
One of the mottos at Uncle Bob’s Store is “drop a dime and pick up a puzzle.” Let’s mentally drop a dime on a corner square of a standard checker/chess board. We’ll stack two dimes on a second square, four dimes on a third square, eight on a fourth, and so on … until we run out of dimes – but wait! We are performing a mental exercise, and so mentally we continue to stack virtual dimes, doubling the amount for each new square until we have a single stack on the final 64th square. The count of dimes on that last square will be a 19-digit number, and the stack will be approximately 2 light years tall. It will extend halfway to the nearest star – virtually.
Versions of this tale have been told ever since ancient times. Grains of rice preceded my dimes by several thousand years, but I’d like you to focus on the final 19-digit number. It’s the 63rd power of 2, that is
2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x ... x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2
We’ll let the dots stand for the missing 46 factors. I relate this number to a famous purported prime number known as Mersenne 67. It is one less than the 67th power of 2, and that is a 21-digit number.
We have some things to clear up. What is a prime? What is a Mersenne prime, and who was Marin Mersenne? Working backwards, as math guys often insist on doing, Mersenne was French, an ordained priest with the handle small-f “father Mersenne,” and he was so much more. He began his scholarly career writing philosophy but eventually turned to the sciences both pure and applied. He was not at the forefront of any of math, astronomy, or music theory, but he contributed to each; moreover, he was at the center of a network of correspondents who were at the top of their games – Galileo, DesCartes, Pascal, Kepler, Roberval, Hobbes, and Huygens. He stimulated discussions and even arguments among these greats, and his network is seen as the forerunner of the Academy of Sciences in Paris and the Royal Society of London.
A prime number is a whole number divisible by only itself and one. Mersenne looked into how the powers of 2 could generate primes. Of course, those powers were divisible by 2, so his “primes” were one less than each power of 2.
Mersenne’s numbers were semi-successful in producing primes, for example, Mersenne 3 is 2 x 2 x 2 – 1 or 7. He was aware that all of his numbers were not prime, for example, Mersenne 6 is 63, or 7x9. In fact it can be shown that Mersenne n will not be prime unless n, the power, is prime. Mersenne produced a list ranging to the 257th power, a phenomenal number, and proffered which of these were prime including Mersenne 67. His list had 5 errors, and there is a tale in that.
In 1903, Frederick Cole rose to present to the prestigious American Mathematic Society. He went to a chalk board and wrote Mersenne 67, or 2^67 – 1. He then calculated it, efficiently we presume. He walked to a second board and multiplied 761,838,257,287 by 193,707,721 – in longhand. The result on each board was the same. He took his seat. Never having said a word, he received a standing ovation from the audience. Numbers, and particularly number theory, attract the hobbyist more than any other branch of math. Cole had spent his Sunday afternoon free time for 20 years searching for and finding the factors of Mersenne 67, thus disproving its primality.
So what? These are just numbers, right? Wrong! For the last 20 years or so, computers ‘round the world have been contributing processing time to the search for more Mersenne primes, and here is where your online banking and other e-commerce enter the picture. The project is called GIMPS, the Great Internet Mersenne Prime Search. GIMPS is no WIMP. Thanks to the combined digital muscle of amateur and professional computers and improved techniques in looking for factors, the project has bagged the latest 16 Mersenne prime discoveries; the largest, found in December, 2017, is a 23-million digit behemoth.
Mersenne numbers in that range are very rarely prime, but to prove they are not requires finding the factors or showing somehow that they exist. Part of the security in doing business online depends on the difficulty of finding factors of large numbers, say 50 to 100 digits in length. Another part involves operations on those numbers that are difficult to work backwards, so called one-way functions. The factors can be found and the functions can be cracked – or hacked, if you will – but the processes involve more time and expense than is worth the effort. For example, a 232-digit number was factored in 2009, but it took collaborating institutions two years to do it.
So far, internet security is bolstered by using larger and larger primes, but these come at a cost and impact the bottom lines of businesses. How much are they willing to pay for top security?Also, there may come a day when new techniques make this mode of protection obsolete. Do we doubt that crooks and enemies are working these avenues at present? If father Mersenne were alive today he would advise you to change your passwords – often.
Sources: Devlin, Mathematics: The New Golden Age; Mersenne picture: St. Andrews, Scotland
© All rights reserved