A 300-billion-digit number is the biggest known pseudoprime, a number which looks like a prime but isn't. The techniques used to find this behemoth could help keep online transactions secure.
The first 10 digits are 1512269972 - but we can't 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. "I've 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.
Fermat pseudoprimes
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's 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's test. Finding the largest known pseudoprime shows that the algorithm is dramatically better than previous techniques, says Shallue, who presented it last month at theJoint Mathematics Meeting in San Diego, California.
"Finding this number is indeed an achievement," says Graham Jameson 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. "The more important problem is to establish just how uncommon these numbers are."
Source:
http://www.electronicsweekly.com/Articles/2013/02/15/55574/science-fermat-pseudoprime-algorithm-supports-online-security.htm
