Loading ...
Sorry, an error occurred while loading the content.

16049Re: [PrimeNumbers] Sieving primo-factorials

Expand Messages
  • Décio Luiz Gazzoni Filho
    Feb 8, 2005
    • 0 Attachment
      On Tuesday 08 February 2005 22:54, you wrote:
      > Décio Luiz Gazzoni Filho wrote:
      > > 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.

      I think the situation isn't so clear-cut for primes of this form. Consider the
      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
      case.

      > If you don't have something better like a sieve then always use pfgw -f
      > The recent development versions of pfgw will factor around 50% of the
      > candidates with the default trial factor limit.

      Given that we need to look for large factors, shouldn't we ditch trial
      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
      algorithmic advantage.

      Are there any implementations of these algorithms using Woltman's FFTs?

      > <snip>
      >
      > 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
      > ..modf=1
      > ..modp=1
      > ..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 +/-

      Actually one can do better:
      -use Legendre's theorem to enumerate the factors of n;
      -subtract 1 for each prime up to n, thus obtaining the prime factorization of
      n!/n#;
      -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,
      e_4, ...

      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)

      Décio


      [Non-text portions of this message have been removed]
    • Show all 9 messages in this topic