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

Re: [PrimeNumbers] Whats the best primality check?

Expand Messages
  • Phil Carmody
    ... Firstly see the proving section at http://primepages.org/ . There are several techniques, and they depend on the size of the number and any special
    Message 1 of 3 , Apr 22, 2002
    • 0 Attachment
      --- padmapani19 <padmapani19@...> wrote:
      > hi all.,
      > i am newbie here and wish to clarify something.if i have a list of
      > numbers generated using some sequence and would like to test the
      > primality of certain numbers what would be the best way of going
      > about
      > it? right now i am using to test N's primality by dividing it till
      > sqrt(N).can there be any possible improvement on this? i am sure
      > there
      > is but i dont know what it is.also if somebody would be generous
      > enough would please let me know whats the best known complexity in
      > terms of big-O notation.(for this way of primality checking by
      > division.)
      >
      > my guess is that it is subexponential(correct me if i am wrong)
      > thank you for the time and patience

      Firstly see the 'proving' section at http://primepages.org/ .

      There are several techniques, and they depend on the size of the
      number and any special properties it may have.

      If the number is tiny, then trial division can take you home, or you
      could do a provably sufficient number of SPRP tests. (Jaeschke)

      If the number has certain related forms that are substantially
      factorable (e.g. 33% of p+1 or p-1 is factorable) then you can use
      pocklingtons theorem or a variant thereof.

      Arbitrary numbers leave you with two main family of choices. Firstly
      there's the fairly predictable APR family (which is effectively an
      exhaustive evaluation of a predicatably sized set of checks).
      Secondly there's a non-deterministic, but typically hugely powerful,
      ECPP technique which tries to prove the primality of a number given
      the primality of a smaller number, recursively. Finding this ladder
      of numbers is effectively a monty-carlo technique.

      Mean big-Ohs for the above can all be found on the prime pages, but
      there are some warnings - neither the APR (APR-CL) or ECPP techniques
      behave in practice exactly as they are predicted to. They aren't far
      out, but they aren't spot on either. This could be due to epsilons on
      powers taking effect at large numbers, or due to higher constant
      lower power terms taking effect at small numbers. People are still
      gathering data.

      Phil

      __________________________________________________
      Do You Yahoo!?
      Yahoo! Games - play chess, backgammon, pool and more
      http://games.yahoo.com/
    Your message has been successfully submitted and would be delivered to recipients shortly.