Re: triple algorithms

On 28 Feb 2008 10:28:52 -0800
Paul Rubin <http://phr.cx@xxxxxxxxxxxxxx> wrote:

That's what I was saying. We know that factorization can be
done in polynomial time. We just don't have the computer to do
it.

Factorization can also be done in constant time, by that
criterion.

With the difference that we don't know a realistic algorithm, and
that there isn't any evidence that it _may_ be possible.

Ok, if you replace "can be done" with "might be doable" then your
second sentence quoted is correct.

Yes, sorry for being inaccurate, but that wasn't even my point. My
point is, as explained in another post, that there is evidence towards
the possibility of a practically runnable polynomial time factoring
algorithm. The _evidence_ is my point.

As Guy Macon pointed out, in the sense of not having a computer to do
it, even constant time algorithms are possible. But we don't have any
evidence that they are.


Regards,
Ertugrul.


--
http://ertes.de/

.

Relevant Pages

  • Re: Quantum slip - Quantum conspiracy
    ... >This evidence comes from Hirvensalo where it is shown that ... >NP-complete problems can be solved in polynomial time ...
    (sci.crypt)
  • Re: triple algorithms
    ... polynomial time. ... Factorization can also be done in constant time, by that criterion. ...
    (sci.crypt)
  • Re: triple algorithms
    ... polynomial time. ... Factorization can also be done in constant time, by that criterion. ... there isn't any evidence that it _may_ be possible. ...
    (sci.crypt)
  • Re: triple algorithms
    ... polynomial time. ... Factorization can also be done in constant time, by that criterion. ...
    (sci.crypt)
  • Re: JSH: Easy math, easy solution
    ... >website and do their prime factorization challenge. ... All of these steps can be performed in polynomial time on a classical ... time using both a quantum computer and a classical computer. ...
    (sci.math)