## Re: [PrimeNumbers] Whats the best primality check?

Expand Messages
• ... 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
> 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
> 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.