> > I don't know what the relevance [of PRIMES in P] to quantum computing is.
>Other than getting primality and factoring confused, I don't knnow either.
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
>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
>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