RE: A little bomb ?

From: Bruno Marchal <marchal.domain.name.hidden>
Date: Mon, 12 Aug 2002 12:25:26 +0200

Saibal Mitra:

> > I don't know what the relevance [of PRIMES in P] to quantum computing is.


Doug Donaghue:


>Other than getting primality and factoring confused, I don't knnow either.


BM:

MEA CULPA! (my fault, my confusion)

And that's nothing compared to my mixing of the bowsprit and the rudder!
   (A thing, as the Bellman remarked
    That frequently happens in tropical climes
    When a Vessel is so to to speak, "snarked".)

;-)

More seriously I do no more know what exactly is new in that papers
on the primes.
Here a message I got from friends. I currently agree, but perhaps I still miss
something?


>Is this just a case of sloppy science journalism or (more
>worryingly) a case of
>an esoteric scientific/mathematical field using terminology in a
>very misleading way?
>
>The title of the paper by Agrawal et al is: "PRIMES is in P" and reading
>the article you get the impression that this is a new discovery.
>However, to my knowledge (poor though it is in number theory)
>checking if a number n is prime or composite can be done in
>polynomial time by
>simply checking whether any of the numbers up to root n divides n.
>This takes O(n) divisions and since division is also polynomial then
>this is
>also a primality testing algorithm that is polynomial.
>
>This confused me for a while. The answer, it seems, is that the
>authors are talking about
>algorithms that are also practical for numbers of large size with
>millions of digits.
>The new algorithm has not reclassified the complexity class of a
>problem as the title and indeed the whole paper (read naively) imply.
>Josh and Max



Bruno
Received on Mon Aug 12 2002 - 03:30:36 PDT