Wheel factorization: Efficient?

[3.14159]

Originally Posted by 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.

Largely taken? 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.

[CRGreathouse]

Originally Posted by 3.14159

Primality tests do not need any factoring to work. Albeit trial factoring is used to eliminate obvious composites.

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.

[3.14159]

Originally Posted by 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.

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

[CRGreathouse]

Originally Posted by 3.14159

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

I refuse to give you a source for my imagination.

Originally Posted by 3.14159

Also: I don't use factor-rich bases because they sieve too slowly and leave too many candidates behind

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.)

[CRGreathouse]

Originally Posted by 3.14159

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

Wrong. They're used in general-purpose packages all the time. See, for example,
http://pari.math.u-bordeaux.fr/cgi-b...2380&root=pari

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.

[science_man_88]

Originally Posted by 3.14159

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.

what should I explain today ? give me a list.

[3.14159]

Originally Posted by 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.

.. Dammit. You're right.

[axn]

Originally Posted by CRGreathouse

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.

Originally Posted by 3.14159

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.

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.

[3.14159]

Originally Posted by CRGreathouse

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

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.

Originally Posted by 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.

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.

Originally Posted by 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.)

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

[CRGreathouse]

Originally Posted by axn

To be honest, the factors of base has very little effect on prime search, once you have done sieving on them**.

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).

[CRGreathouse]

Originally Posted by 3.14159

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

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.