[QUOTE=CRGreathouse]Primorial bases are, naturally, the best for a given size. I imagine they're largely taken? 30030, for example, would produce 5.2135 times the normal number of primes.
[/QUOTE]

Largely taken? :orly owl: Show me the distributed search for k * p(x)#^n + 1, and I'll take your word for it.

Also: I don't use factor-rich bases because they sieve too slowly and leave too many candidates behind, which wastes time testing what could have been eliminated given a prime or factor-deficient base. P.S: Why does it become harder to sieve for larger bases? I tested 510510 and it barely got past 1/7. Unacceptable.

[QUOTE=3.14159;223996]Primality tests do not need any factoring to work. Albeit trial factoring is used to eliminate obvious composites.[/QUOTE]

Factoring is pretty common in primality proving, actually. The whole Pocklington's theorem-based tests use it. The Brillhart-Lehmer-Selfridge algorithm, the modern combined p-1/p+1 method, is rather popular.

[QUOTE=CRGreathouse]Factoring is pretty common in primality proving, actually. The whole Pocklington's theorem-based tests use it. The Brillhart-Lehmer-Selfridge algorithm, the modern combined p-1/p+1 method, is rather popular.
[/QUOTE]

They are useless for most integers, as most integers are not special-form integers.

[QUOTE=3.14159;223998][QUOTE=CRGreathouse;223997]Primorial bases are, naturally, the best for a given size. I imagine they're largely taken? 30030, for example, would produce 5.2135 times the normal number of primes.[/QUOTE]
Largely taken? [image removed] Show me the distributed search for k * p(x)#^n + 1, and I'll take your word for it.[/QUOTE]

I refuse to give you a source for my imagination.

[QUOTE=3.14159;223998]Also: I don't use factor-rich bases because they sieve too slowly and leave too many candidates behind[/QUOTE]

I suspect you're counting the numbers removed from other bases on account of their small factors (2, 3, 5, etc.). That's fallacious, of course -- you can't remove these from bases which have those factors, but that means that the bases with small factors have more small candidates. They're better in that sense, not worse, even though the sieving percentages will be an easily-calculated percentage 'worse'. (The factor by which I call them better is the factor by which you call them worse.)

[QUOTE=3.14159;224002]They are useless for most integers, as most integers are not special-form integers.[/QUOTE]

Wrong. They're used in general-purpose packages all the time. See, for example,
[url]http://pari.math.u-bordeaux.fr/cgi-bin/viewcvs.cgi/trunk/src/basemath/prime.c?view=markup&revision=12380&root=pari[/url]

Also, your claim (now edited out) that p-1 or p+1 must be fully factored is incorrect; Brillhart-Lehmer-Selfridge requires that p^2-1 is about one-third factored.

[QUOTE=3.14159;223996]Primality tests do not need any factoring to work. Albeit trial factoring is used to eliminate obvious composites.

Also:


This is too vague for me. Many things are left unspecified here.[/QUOTE]

what should I explain today ? give me a list.

[QUOTE=CRGreathouse]Also, your claim (now edited out) that p-1 or p+1 must be fully factored is incorrect; Brillhart-Lehmer-Selfridge requires that p^2-1 is about one-third factored.
[/QUOTE]

:orly owl:

.. Dammit. You're right.

[QUOTE=CRGreathouse;223997]The more (small distinct) prime factors in the base, the better. A base of 12096 'protects' you from 2, 3, and 7; you find 3.5 times the expected number of primes vs. random numbers of the same size. For base 1297 you find 1.0008 times the expected number of primes.[/QUOTE]

[QUOTE=3.14159;223998]Also: I don't use factor-rich bases because they sieve too slowly and leave too many candidates behind, which wastes time testing what could have been eliminated given a prime or factor-deficient base. P.S: Why does it become harder to sieve for larger bases? I tested 510510 and it barely got past 1/7. Unacceptable.[/QUOTE]

To be honest, the factors of base has very little effect on prime search, once you have done sieving on them**. What I mean is, the expected number of candidates to search for a prime is dependent only on the average candidate size and the sieve depth. For a factor-rich base, you would naturally start with less candidates (before sieving) as compared to a factor-deficient base. The numbers such as "1 in 7 candidates left" are irrelevant -- what is relevant is the aposteriori probability, after sieving, of a candidate yielding prime.

** For a fixed-n search. For fixed-k search, different considerations come into play.

[QUOTE=CRGreathouse]I suspect you're counting the numbers removed from other bases on account of their small factors (2, 3, 5, etc.).[/QUOTE]

Nope. I merely compare the fraction of candidates that remain. Factor-rich numbers leave too many behind and as a result waste time testing obvious composites that could have been eliminated. A prime or factor-deficient base does not leave many candidates behind.

[QUOTE=CRGreathouse]That's fallacious, of course -- you can't remove these from bases which have those factors, but that means that the bases with small factors have more small candidates.[/QUOTE]

How is that fallacious? Factor-rich bases can barely manage to eliminate 90% of the candidates, while factor-deficient or prime bases can eliminate 95% of the candidates with ease.

[QUOTE=CRGreathouse]They're better in that sense, not worse, even though the sieving percentages will be an easily-calculated percentage 'worse'. (The factor by which I call them better is the factor by which you call them worse.)[/QUOTE]

How is wasted time testing obvious composites that could have been eliminated with ease "better"?

[QUOTE=axn;224007]To be honest, the factors of base has very little effect on prime search, once you have done sieving on them**.[/QUOTE]

Agreed, in terms of time per number at a given size. But the base does change the number of good candidates, and if nothing else the candidates are smaller (though this doesn't have much of an effect on time, since that just adds 1 or 2 to the denominator).

[QUOTE=3.14159;224008]Nope. [...] How is wasted time testing obvious composites that could have been eliminated with ease "better"?[/QUOTE]

You misunderstand me. I don't have time to re-explain at the moment, but you may figure it out. Read axn's post; maybe that will help.