Re: "P vs. NP" and the future of public key crypto

newstome_at_comcast.net
Date: 01/13/04 

Date: Tue, 13 Jan 2004 04:05:37 GMT

Tom St Denis <tomstdenis@iahu.ca> wrote:
>
> <newstome@comcast.net> wrote in message
> news:G2EMb.36569$xy6.88928@attbi_s02...
>
>> Nope -- 2^113 is quite a bit larger than 300^12 (the functions n^12
>> and 2^n cross at about n=75, so the n^12 algorithm would actually be
>> faster for any n>75).
>
> That was a typo. It's ln(2^1024) ~ 709 where 709^12 ~ 2^113.

Sorry -- misread your post.

>> And incidentally, that algorithm you're referring to might be much
>> faster. If a certainly (widely believed to be true) conjecture holds,
>> it's at most O(n^6). And how do you know that's the best algorithm?
>> Maybe PRIMES can be solved in n^3 time....
>
> That's just our point though. Just because something is in P doesn't mean
> it's fast. By your logic how do you know there isn't a faster NP solution
> [e.g. faster than GNFS without the factoring in P]? So why bother using
> crypto at all!!!

I understand your point, but you seem to be missing mine. You're
right that just being in P doesn't mean something is fast. In fact,
by the time hierarchy theorem, there are problems whose fastest
solution is n^10000 -- in other words, in P but not efficient in a
practical sense. But my point is that you just don't see *natural*
problems like that. Your PRIMES example is no counterexample to this,
because it's most likely an n^6 algorithm. You might not think that's
terribly fast, but you can bet the farm that an n^6 factoring
algorithm would be *very* influential.... in both a practical and
theoretical sense. 

-- 
That's News To Me!
newstome@comcast.net

Relevant Pages

  • Re: Provability
    ... for the Poincare conjecture which has been proven. ... we can write down an algorithm which does ... If some algorithm A_t is a polynomial-time algorithm for ... but in principal the Levin ...
    (sci.math)
  • Re: Important Paper for Anti-Relativityists
    ... discrete system of interacting particles by an algorithm. ... The conjecture is explained in two ... Newton's physics and modern physics." ...
    (sci.physics)
  • Re: riemann hypothesis needed to factor numbers?
    ... Goldbach conjecture and the Riemann hypothesis. ... I don't think RH implies the existence of a fast factoring algorithm. ... I think there are fast primality testing algorithms which depend on RH, but we already have fast-enough algorithms that don't. ... I think that such algorithms would tend to be fast in practice for the same reason that the nontrivial zeros of the zeta function are on the critical line "in practice". ...
    (sci.math)
  • Re: Important Paper for Anti-Relativityists
    ... discrete system of interacting particles by an algorithm. ... method of predicting measurements from the model. ... The conjecture is explained in two ... Newton's physics and modern physics." ...
    (sci.physics)
  • Re: RC4 on AMD64
    ... > Look how long it took to find some of the (easy to avoid) ... > the complexity of the algorithm. ... Tom's conjecture: Anyone can come up with wild conclusions. ... look how easy it was to prove security against LC/DC and so ...
    (sci.crypt)
Quantcast