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

Re: [PrimeNumbers] Re: Polynomial Test for Prime Numbers

Expand Messages
  • Peter Kosinar
    ... Wrong. That d not be polynomial anymore. x^x 2^x = a lot worse than exponentail. Or, if you prefer it in your original language, Log[n]^Log[n] =
    Message 1 of 3 , Jan 22, 2011
    • 0 Attachment
      > We can increase the bound and the test remains polynomial, for example
      > try to Log [n] ^Log [n] instead of Log[n]^2

      Wrong. That'd not be polynomial anymore. x^x > 2^x = a lot worse than
      exponentail. Or, if you prefer it in your original language,

      Log[n]^Log[n] = 2^Log[n]*(Log[Log[n]]) = n^Log[Log[n]] = much worse than
      trial factoring :-)

      Peter

      [Non-text portions of this message have been removed]
    Your message has been successfully submitted and would be delivered to recipients shortly.