Undercurrent

<a href="http://www.cse.iitk.ac.in/news/primality.html" target="_blank">http://www.cse.iitk.ac.in/news/primality.html</a>

Yay!!!

m.

Friar Bellows

You mean I'm going to have to give up the Sieve of Eratosthenes? Bugger.

NialScorva

I was pretty sure that you could do this in linear time already...

[code]

if (candidate mod 2 = 0) return false;
for(int a=3; a LESSTHANEQUAL sqrt(candidate); a+=2)
if(candaidate mod a = 0) return false;

return true;
</pre>[/quote]

This is an O(N) algorithm on the majority of systems (with constant time division and sqrt).

Is this an algorithm for arbitrarily sized integers?

[edit- wouldn't post with the less than sign, said "cannot have parens inside an html tag". That's pretty dumb]

[ August 08, 2002: Message edited by: NialScorva ]</p>

lpetrich

It's a modification of the Sieve of Eratosthenes, where one does not try to find the intermediate prime values.

ohwilleke

Impressive result. I imagine it will be in advanced mathematics textbooks for the rest of time. And, in stark contrast to the recent proof of Fermat's Last Theorem, described in the brevity customary of new advances in mathematics (a mere nine pages in all with the algorhythm itself and proof that it works set out in just a couple of pages).

I'm also pleased that this result has been widely distributed on the web to the entire scientific community before it could be classified. One of the inherent hazards of working in number theory is that great results are classified for national security reasons before they can be published.

It is also an interesting example of the fact that many great advances can come even when there is no patent protection for the idea. . . just fame.

The fact that there is a real possibility that slight modifications can increase the efficiency of the approach from solving problems not within a function of (log n)^12 minutes, as proven, but in a function of (log n)^3 minutes or so, is also notable.

NialScorva

Ah, finally got to read the paper (had to download acroread, no open source reader I could find would handle the type 3 fonts in the paper )

Looks neat, one division and scales to arbitrarily sized integers.

Friar Bellows

From a "pure math" perspective this is a great result, but from the "applied math" perspective, surely it's no big deal, because after all there are "non-exact" (I forget the right term for them) algorithms which are faster, and for which the errors can be made exceedingly (arbitrarily?) small. But I could be wrong.

fando

That is correct. There are 'probablistic' algorithms that can show whether a number is prime or not with a certain probability, and by applying these algorithms repeatedly, one can minimize the probability of being wrong. However, I'm fairly certain that the time cost of this approach will outstrip the cost of the newly discovered deterministic algorithm for very, very large numbers. This new algo has benefits for certain problem domains, it's not just another useless math theory.

Coragyps

But all I wanted to know was if the integer comprising seventeen 1's in a row is prime. Well, that one and nineteen 1's, too.

ohwilleke

I think that the big consequence of this theorem, together with Fermat's Last and another of other big number theory developments lately, is that we may discover enough to really provide an overarching understanding of number theory, and not just a bunch of apparently fluky, unconnected results.