--- 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/