16049Re: [PrimeNumbers] Sieving primo-factorials
- Feb 8, 2005On Tuesday 08 February 2005 22:54, you wrote:
> Décio Luiz Gazzoni Filho wrote:I think the situation isn't so clear-cut for primes of this form. Consider the
> > As you may recall, I resumed Mike Oakes' search for primo-factorials,
> > primes of the form n! +/- n# +/- 1.
> > Maybe I'll keep on searching for n > 10000, but I don't feel very
> > inclined to do so unless I can do better than PRP-ing all the candidates.
> What? You prp all the candidates?
> _Never_ do that.
values I computed for Mertens' theorem: even if trial factoring up to 1e9
were just a little more costly than PRP-ing the integer, then nothing is
gained. But apparently trial factoring to 127e6 is already 3/4 as costly as
the PRP test itself. So I don't think trial factoring makes sense in this
> If you don't have something better like a sieve then always use pfgw -fGiven that we need to look for large factors, shouldn't we ditch trial
> The recent development versions of pfgw will factor around 50% of the
> candidates with the default trial factor limit.
factoring for Pollard rho and maybe a little Pollard p-1?
Unfortunately using PARI/GP or GMP-ECM for the job would be hopeless, as GMP
is much slower than George Woltman's code, and this would probably negate any
Are there any implementations of these algorithms using Woltman's FFTs?
> <snip>Actually one can do better:
> I doubt a "true" sieve is possible for this form but a custom made
> individual trial factoring program would probably be a lot faster than pfgw
> -f. A simple algorithm keeping track of moduli after each multiplication by
> n: (dots to prevent space deletions)
> for each prime p below trial factor limit
> ..for n from 1 to nmax
> ....modf = modf*n mod p
> ....if n is prime then modp = modp*n mod p
> ....if modf+/-modp+/-1 is 0 mod p then mark n as factored for that +/-
-use Legendre's theorem to enumerate the factors of n;
-subtract 1 for each prime up to n, thus obtaining the prime factorization of
-evaluate this by modular powering, call it a;
-compute b = a +/- 1, according to the form desired;
-compute c = a*n# mod p;
-finally, the result is given by b*c +/- 1 mod p (again the sign is chosen
according to the form desired).
To see why this is faster, consider that the prime factorization of a typical
n!/n# factor is
2^e_1 3^e_2 5^e_3 7^e_4 ...
Then your method does e_1 + e_2 + e_3 + e_4 + ... multiplications, while mine
does something like O(log e_1) + O(log e_2) + O(log e_3) + O(log e_4) + ...,
these being the cost of modular exponentiations with exponent e_1, e_2, e_3,
Also, one might cache results from a computation to another. If one caches the
intermediate computations for n! +/- n# +/- 1 mod p, at most two modmuls are
required to find (n+1)! +/- (n+1)# +/- 1 mod p.
In fact, this is a very good idea. I'm off to implement it in PARI/GP. Thanks
very much for the motivation (: (though I still believe that Pollard rho and
perhaps p-1 would be more efficient)
[Non-text portions of this message have been removed]
- << Previous post in topic Next post in topic >>