A 300-billion-digit number is the biggest known pseudoprime, a number which looks like a prime but isn鈥檛. The techniques used to find this behemoth could help keep online transactions secure.
The first 10 digits are 1512269972 鈥� but we can鈥檛 give you the rest as the new number is so large that typing out the full thing eats up around a third of a terabyte. 鈥淚鈥檝e got an external drive holding it,鈥� says co-discoverer Andrew Shallue of Illinois Wesleyan University in Bloomington. It dwarfs the largest known true prime, a 17-million digit monster announced last week.
Prime numbers can only be divided by themselves and 1. Figuring out which numbers are prime can be tricky, so mathematicians have developed various algorithms to speed up the search. One simple test is based on an observation by 17th-century mathematician Pierre de Fermat, who said that for any prime number p and whole number a, if you divide ap 鈥� a by p, the remainder is 0. Unfortunately, that is sometimes also true when p is not a prime.
Advertisement
Finding fakes
There are just 43 of these Fermat pseudoprimes in the first million numbers, compared to nearly 80,000 primes. Primes form the building blocks of modern cryptography, so mistaking a pseudoprime for the real deal would make it easy for someone to steal your secrets. Mathematicians have developed more sophisticated tests since Fermat鈥檚 that reduce these mistakes, but pseudoprimes still crop up unexpectedly.
To hunt out the fakes, Shallue and colleague Steven Hayman created an algorithm that looks at a list of numbers to find a subset that, when multiplied together, produces a particular target 鈥� in this case, a pseudoprime that passes Fermat鈥檚 test. Finding the largest known pseudoprime shows that the algorithm is dramatically better than previous techniques, says Shallue, who presented it last month at the in San Diego, California.
鈥淔inding this number is indeed an achievement,鈥� says of the University of Lancaster, UK. However, the practical advance is the new algorithm, which could tell mathematicians and cryptographers more about the general properties of pseudoprimes, he says. 鈥淭he more important problem is to establish just how uncommon these numbers are.鈥�
