Loading ...
Sorry, an error occurred while loading the content.

Re: Poll of Yahoos ?

Expand Messages
  • djbroadhurst
    ... Yes, that *is* a telling bit of history, Paul. And the super-polynomial algorithm (APRCL) is probably faster than the polynomial (ECPP) for the forseeable
    Message 1 of 1 , Jun 21, 2002
    • 0 Attachment
      > until recently primality proving was as hard as factoring.
      > It's now in P.

      Yes, that *is* a telling bit of history, Paul.

      And the super-polynomial algorithm (APRCL) is
      probably faster than the polynomial (ECPP) for
      the forseeable future. (Or at least that's
      what both Jason and Marcel believe.)

      > By x/y-polynomial I mean
      > O(exp((log N)^{1-x/y}(log log N)^{x/y})).

      APRCL is supposed to be
      O(exp(log log N * log log log N))
      which is at x/y=1-eps on your NFS scale,
      not so?

      My feeling is that factoring might get
      up to x/y=3/4, or even 1-eps, but really
      should *not* be in P. It jolly well ought
      to be harder than primality proving, because
      it *finds* something interesting, rather than
      telling you a one-bit answer. And my scots
      primary school teachers indoctrinated me
      with a protestant work ethic, it seems...

      David
    Your message has been successfully submitted and would be delivered to recipients shortly.