Teenager Solves Stubborn Riddle About Prime Number Look-Alikes
Over a century ago, in that quest for a fast, powerful primality test, mathematicians stumbled on a group of troublemakers — numbers that fool tests into thinking they're prime, even though they're not. These pseudoprimes, known as Carmichael numbers, have been particularly difficult to grasp. It was only in the mid-1990s, for instance, that mathematicians proved there are infinitely many of them. Being able to say something more about how they're distributed along the number line has posed an even greater challenge.
Then along came Larsen with a new proof about just that, one inspired by recent epochal work in a different area of number theory. At the time, he was just 17.
[...] Mathematicians saw the potential for a perfect test of whether a given number is prime or composite. They knew that if N is prime, bN – b is always a multiple of N. What if the reverse was also true? That is, if bN – b is a multiple of N for all values of b, must N be prime?
Alas, it turned out that in very rare cases, N can satisfy this condition and still be composite. The smallest such number is 561: For any integer b, b561 – b is always a multiple of 561, even though 561 is not prime. Numbers like these were named after the mathematician Robert Carmichael, who is often credited with publishing the first example in 1910 (though the Czech mathematician Václav Šimerka independently discovered examples in 1885).
In particular, he (Andrew Granville) and his co-authors hoped to prove a statement that reflected this idea — that given a sufficiently large number X, there will always be a Carmichael number between X and 2X. "It's another way of expressing how ubiquitous they are," said Jon Grantham, a mathematician at the Institute for Defense Analyses who has done related work.
But for decades, no one could prove it. The techniques developed by Alford, Granville and Pomerance "allowed us to show that there were going to be many Carmichael numbers," Pomerance said, "but didn't really allow us to have a whole lot of control about where they'd be."
Then, in November 2021, Granville opened up an email from Larsen, then 17 years old and in his senior year of high school. A paper was attached — and to Granville's surprise, it looked correct. "It wasn't the easiest read ever," he said. "But when I read it, it was quite clear that he wasn't messing around. He had brilliant ideas."
Pomerance, who read a later version of the work, agreed. "His proof is really quite advanced," he said. "It would be a paper that any mathematician would be really proud to have written. And here's a high school kid writing it."
The key to Larsen's proof was the work that had drawn him to Carmichael numbers in the first place: the results by Maynard and Tao on prime gaps.
(Score: 2) by driverless on Monday October 24 2022, @10:14AM (8 children)
Unfortunately it's a mostly theoretical result and doesn't provide any hints at a new better primality test. Currently Fermat and Miller-Rabin can be fooled with mailciously-constructed values and tests like BPSW are too slow and complex to be used by most crypto libraries.
(Score: 3, Insightful) by JoeMerchant on Monday October 24 2022, @12:43PM
It seems like a multi layered test would be the thing...
If you want a prime, start with the b^N-b test and then if that passes, test it against primes up to sqrt(N).
I'm sure there are other clever tricks that can accelerate the process considerably.
Україна досі не є частиною Росії Слава Україні🌻 https://news.stanford.edu/2023/02/17/will-russia-ukraine-war-end
(Score: 5, Informative) by Immerman on Monday October 24 2022, @02:42PM (3 children)
You seem to have missed the point - even the headline indicates that the paper was NOT about prime numbers.
Rather, they managed to prove a lower bound on the frequency of Carmichael numbers - a particular class of numbers that share some properties with prime numbers, and are interesting in their own right because of it..
As for being theoretical - of course! This is mathematics, theoretical proofs are the bedrock on which it's built, everything else is just a curiosity. Practical applications are something for other fields to concern themselves with, mathematics is the hunt for provably inviolate relationships within the rules of logic.
(Score: 2) by FatPhil on Monday October 24 2022, @02:53PM (2 children)
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
(Score: 2) by JoeMerchant on Monday October 24 2022, @03:00PM (1 child)
>"there's always another pair of primes closer than X to each other"
That's so inherently intuitive, I'm glad they were able to prove it.
Україна досі не є частиною Росії Слава Україні🌻 https://news.stanford.edu/2023/02/17/will-russia-ukraine-war-end
(Score: 2) by FatPhil on Monday October 24 2022, @06:41PM
Then again, PRIMES is in P kinda came out of nowhere as a quantum leap that wasn't so terribly different from prior work.
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
(Score: 3, Insightful) by FatPhil on Monday October 24 2022, @02:50PM
You definitely need a lucas-based test in the mix somewhere (so a Frobenius test is an alternative) because of things like Arnaud's malicious pseudoprimes.
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
(Score: 2, Disagree) by Immerman on Monday October 24 2022, @05:42PM (1 child)
As for theoretical versus practical - what are the practical applications of large prime numbers? I mean, for a better prime test to be practical, that implies that primes themselves are practical, doesn't it?
The only thing I can think of as a candidate is cryptography, where they're actually fairly useless because there's so few of them that a brute force attack using them is trivial, hence the common use of pseudo-primes and relatively prime numbers instead, which radically increases the problem space beyond what brute forcing can explore in a timely manner.
And other than that... small primes are useful in engineering for avoiding resonance, but I doubt anyone has ever used for a prime with more than a couple digits in that context, since physical imperfections blur the line between perfect and approximate resonance.
(Score: 4, Informative) by bzipitidoo on Monday October 24 2022, @09:22PM
Number theory used to be the ultimate in research that was useless for military application, and therefore a favorite of scientists who hate seeing their discoveries perverted for purposes of killing. Then public key encryption came along.
If by "large", you mean between 100 and 10,000 digits, those have been and still are very useful for RSA public key encryption. (I am not sure what size state of the art RSA uses nowadays.) That's way too large a problem space for brute force. Until quantum computing is able to run Shor's factoring algorithm on numbers of that size, RSA will remain secure. For this reason among others, the military lusts for quantum computing.
For many years now, the largest known prime has been a Mersenne prime. The current largest known is a little under 25 million digits.