Largest fake prime number holds 300 billion digits

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 a^p ? a by p, the remainder is 0. Unfortunately, that is sometimes also true when p is not a prime.

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'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 the Joint 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."

If you would like to reuse any content from New Scientist, either in print or online, please contact the syndication department first for permission. New Scientist does not own rights to photos, but there are a variety of licensing options available for use of articles and graphics we own the copyright to.

Have your say

Only subscribers may leave comments on this article. Please log in.

Only personal subscribers may leave comments on this article

Subscribe now to comment.

All comments should respect the New Scientist House Rules. If you think a particular comment breaks these rules then please use the "Report" link in that comment to report it to us.

If you are having a technical problem posting a comment, please contact technical support.

Source: http://feeds.newscientist.com/c/749/f/10897/s/288ee4fd/l/0L0Snewscientist0N0Carticle0Cdn231710Elargest0Efake0Eprime0Enumber0Eholds0E30A0A0Ebillion0Edigits0Bhtml0Dcmpid0FRSS0QNSNS0Q20A120EGLOBAL0Qonline0Enews/story01.htm

michele bachmann donald trump Election 2012 map Election Results Map Early voting results BBC Dick Morris