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

Sieving primo-factorials

Expand Messages
  • Décio Luiz Gazzoni Filho
    As you may recall, I resumed Mike Oakes search for primo-factorials, primes of the form n! +/- n# +/- 1. Mike had stopped at n = 7039, and I picked up the
    Message 1 of 9 , Feb 8, 2005
    • 0 Attachment
      As you may recall, I resumed Mike Oakes' search for primo-factorials, primes
      of the form n! +/- n# +/- 1. Mike had stopped at n = 7039, and I picked up
      the search until 10000. 2 PRPs were found, 8147! + 8147# - 1 and 9627! -
      9627# - 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.

      Specifically, I'm thinking of sieving them. However, the first sieve that
      comes to mind (computing n! +/- n# +/- 1 mod 2, 3, 5, 7, ...) is largely
      ineffective for the task, since n! +/- n# have as common factors all primes
      up to n. One might argue `fine, let's sieve with primes larger than n them.'
      However, this is a very inefficient sieve: by Mertens' theorem, only 6.1%
      percent of random integers aren't divisible by primes up to 10,000, while
      2.71% percent of random integers aren't divisible by primes up to a billion
      (a very very optimistic sieve bound). Thus, using this sieve I could at best
      eliminate 55.5% (= 1 - 2.71/6.1) of candidates, certainly not a worthwhile
      effort for the time it would take to sieve up to a billion.

      Thus I am led to ask the group for other strategies to sieve this sequence of
      primes. Everything I've come up with until now relies on the following facts:

      1. n! +/- n# +/- 1 = n#*(n!/n# +/- 1) +/- 1, where n!/n# is an integer.

      2. For a given prime p, then n#*(n!/n# +/- 1) +/- 1 == 0 mod p implies
      n#*(n!/n# +/- 1) == +/-1 mod p, so that n# or -n# is an inverse mod p of
      (n!/n# +/- 1).

      3. And of course, it's easy to perform reductions modulo p, as we can easily
      enumerate the prime factors of n! using Legendre's theorem, then use

      Basically what I'm looking for is something relating the congruence classes of
      an integer and its inverse, so that I can figure out conditions n that will
      have one of n! +/- n# +/- 1 divisible by a chosen prime. If such a result
      could be found, then the sequence could actually be sieved in the usual sense
      -- discarding the integers that are divisible by a given prime p with less
      work than testing all of them.

      I'm not placing much hope on the existence of such a method, but as it's been
      repeatedly shown here, my knowledge is quite limited (:

      Décio


      [Non-text portions of this message have been removed]
    • Jens Kruse Andersen
      ... What? You prp all the candidates? _Never_ do that. If you don t have something better like a sieve then always use pfgw -f The recent development versions
      Message 2 of 9 , Feb 8, 2005
      • 0 Attachment
        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.
        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.
        -sn can be used to start factoring at n but it makes little difference on
        average.

        C:>pfgw -f -q10000!-10000#+1
        PFGW Version 20041023.Win_Dev (Beta 'caveat utilitor') [FFT v23.8]

        trial factoring to 127407975
        10000!-10000#+1 has factors: 1535323

        It first factors to 10^9 for n=34338:
        trial factoring to 1000048612
        34338!+34338#+1 has factors: 42709

        A number with 140840 digits:
        len(34338!+34338#+1): 140840

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

        Several optimisations are possible. n should of course not be primality tested
        in each loop.

        --
        Jens Kruse Andersen
      • Décio Luiz Gazzoni Filho
        ... 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
        Message 3 of 9 , 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]
        • Jens Kruse Andersen
          ... Trial factoring almost always makes sense if nothing else is used. I did consider your case carefully and you may want to think twice before dismissing me.
          Message 4 of 9 , Feb 8, 2005
          • 0 Attachment
            Décio Luiz Gazzoni Filho wrote:
            > 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.

            Trial factoring almost always makes sense if nothing else is used.
            I did consider your case carefully and you may want to think twice before
            dismissing me. I have written a lot of both sieves and individual trial
            factoring programs. My sieves hold around 70 different current prime records:
            http://hjem.get2net.dk/jka/math/myrecords.htm (2 records did not use my sieves)
            Sorry for bragging but knowing what somebody has done may be helpful when
            deciding whether to follow their advice or spend time studying their writings.

            The default trial factor depth in pfgw -f tries to be near optimal, i.e. stop
            when the "expected" factoring time matches prp time (although different prp
            times for different forms is not taken into account).

            I wrote:
            > The recent development versions of pfgw will factor around 50% of the
            > candidates with the default trial factor limit.

            A recent development version can be found at
            http://groups.yahoo.com/group/openpfgw/files/
            It has _much_ faster trial factoring of large numbers, by the way based on my
            TreeSieve code.
            Factoring to 127e6 is not 3/4 but 1/8 as costly as the prp test itself.
            That is definitely worth the effort when around 50% of candidates are factored.

            pfgw versions slower at factoring will also choose a suitable default limit for
            pfgw -f, e.g.:

            C:>pfgw -f -o -q10000!+10000#+1
            PFGW Version 20041129.Win_Stable (v1.2 RC1d) [FFT v23.8]

            trial factoring to 11300619
            10000!+10000#+1 has no small factor.

            Factoring to 11.3e6 with this version also took around 1/8 of prp time.
            Around 43% of your candidates near n=10000 will be factored by 11.3e6.
            Also definitely worth 1/8 of the prp time (less when a factor is found).

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

            Maybe, after trial factoring to some point (above 10000). It depends on the
            available programs and whether you want to set it up. Adding -f in a pfgw call
            is extremely easy and should always be done if no other factoring has been
            performed.

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

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

            Read my code again. This caching is exactly what I did, but in a practical
            order:
            > > for each prime p below trial factor limit
            > > ..for n from 1 to nmax

            If you swap the (for p, for n) order then you have to store 2 residues for every
            prime below the trial factor limit.
            That may require more than 1 GB for a high limit.

            Can you combine this fast caching method with using the prime factorization of n
            as you suggest (except for initialization if you don't start at n=1)?
            I considered the factorization method but thought my suggestion would be much
            faster.

            --
            Jens Kruse Andersen
          • Décio Luiz Gazzoni Filho
            ... I m not doubting your claims, rest assured (: Problem is, I m seeing some unusually slow timings for PFGW trial factoring. Both David and Jim wrote me
            Message 5 of 9 , Feb 8, 2005
            • 0 Attachment
              On Wednesday 09 February 2005 01:59, you wrote:
              > Décio Luiz Gazzoni Filho wrote:
              > > 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.
              >
              > Trial factoring almost always makes sense if nothing else is used.
              > I did consider your case carefully and you may want to think twice before
              > dismissing me. I have written a lot of both sieves and individual trial
              > factoring programs. My sieves hold around 70 different current prime
              > records: http://hjem.get2net.dk/jka/math/myrecords.htm (2 records did not
              > use my sieves) Sorry for bragging but knowing what somebody has done may be
              > helpful when deciding whether to follow their advice or spend time studying
              > their writings.

              I'm not doubting your claims, rest assured (:

              Problem is, I'm seeing some unusually slow timings for PFGW trial factoring.
              Both David and Jim wrote me off-list to point that out. In the context of
              slow timings and the expected removal rate, I believe my comment makes sense.

              > The default trial factor depth in pfgw -f tries to be near optimal, i.e.
              > stop when the "expected" factoring time matches prp time (although
              > different prp times for different forms is not taken into account).

              Except that it doesn't take into account the fact that n! +/- n# +/- 1 isn't
              divisible by primes up to n; Jim suggested that I try -f35 instead of the
              default, as that's near optimal according to his experiments.

              > I wrote:
              > > The recent development versions of pfgw will factor around 50% of the
              > > candidates with the default trial factor limit.
              >
              > A recent development version can be found at
              > http://groups.yahoo.com/group/openpfgw/files/
              > It has _much_ faster trial factoring of large numbers, by the way based on
              > my TreeSieve code.
              > Factoring to 127e6 is not 3/4 but 1/8 as costly as the prp test itself.
              > That is definitely worth the effort when around 50% of candidates are
              > factored.

              Yes, in that case it is.

              > pfgw versions slower at factoring will also choose a suitable default limit
              > for pfgw -f, e.g.:
              >
              > C:>pfgw -f -o -q10000!+10000#+1
              > PFGW Version 20041129.Win_Stable (v1.2 RC1d) [FFT v23.8]
              >
              > trial factoring to 11300619
              > 10000!+10000#+1 has no small factor.

              I should grab that version -- I was running the latest compiled binary for
              Linux that was available in the files area of the openpfgw group.

              > Factoring to 11.3e6 with this version also took around 1/8 of prp time.
              > Around 43% of your candidates near n=10000 will be factored by 11.3e6.
              > Also definitely worth 1/8 of the prp time (less when a factor is found).
              >
              > > 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?
              >
              > Maybe, after trial factoring to some point (above 10000). It depends on the
              > available programs and whether you want to set it up. Adding -f in a pfgw
              > call is extremely easy and should always be done if no other factoring has
              > been performed.
              >
              > > > 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;
              >
              > ...
              >
              > > 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.
              >
              > Read my code again. This caching is exactly what I did, but in a practical
              >
              > order:

              Sorry about that. I should really get some sleep. Turns out that I reinvented
              the wheel for lack of concentration to properly read your code!

              > > > for each prime p below trial factor limit
              > > > ..for n from 1 to nmax
              >
              > If you swap the (for p, for n) order then you have to store 2 residues for
              > every prime below the trial factor limit.
              > That may require more than 1 GB for a high limit.

              Correct. Although I didn't realize that I had even specified a particular loop
              order! But as I was writing my code (before receiving this email) I was
              already using the (for p, for n) order.

              > Can you combine this fast caching method with using the prime factorization
              > of n as you suggest (except for initialization if you don't start at n=1)?
              > I considered the factorization method but thought my suggestion would be
              > much faster.

              I'm writing the code right now. Hope I don't fall asleep over my keyboard
              before finishing it, though.

              Using the explicit prime factorization of n! (from Legendre's theorem) is only
              useful if you're not starting from n = 1, otherwise the result cache does the
              job. As the range n <= 10000 is already done, I believe it's worth it.

              Décio


              [Non-text portions of this message have been removed]
            • Décio Luiz Gazzoni Filho
              ... I coded the sieve (code reproduced below). Despite the fact that it segfaults with gp2c, so that I had to run it interpreted instead of compiled, it s
              Message 6 of 9 , Feb 8, 2005
              • 0 Attachment
                On Wednesday 09 February 2005 01:59, you wrote:
                > Can you combine this fast caching method with using the prime factorization
                > of n as you suggest (except for initialization if you don't start at n=1)?
                > I considered the factorization method but thought my suggestion would be
                > much faster.

                I coded the sieve (code reproduced below). Despite the fact that it segfaults
                with gp2c, so that I had to run it interpreted instead of compiled, it's
                still a speed demon. With 10 minutes of CPU time (P4 2.6 GHz here) I
                eliminated nearly 4000 composites. I shudder to think that this could
                probably have cost me somewhere in the vicinity of 10 CPU-days.

                I'm sure I commited a few egregious errors down there, not to mention some
                ugly hacks, so please refrain from flaming me (:

                I wonder, at what point should I switch back to trial factoring?

                Décio

                ---
                primorial(x) =
                {
                local(a);
                a = 1;
                forprime(p=2,x,a*=p);
                return(a);
                }

                \\ Reverse indexes the primes -- the inverse of PARI's prime() function
                init_invprime(nmax) =
                {
                local(last,k);
                global(invprime);
                invprime = vector(nmax);
                last = 1;
                k = 0;
                forprime(p=2,nmax,
                k++;
                for(i=last,p-1,
                invprime[i] = k-1;
                );
                last = p;
                );
                }

                \\ Computes the prime factorization of n!/n#
                legendre_factorial(n) =
                {
                local(v,i,k);
                \\ v[] is initialized with -1 to simulate division by n#
                v = vector(invprime[n],i,-1);
                i = 0;
                forprime(p=2,n,
                i++;
                k = 1;
                while((cont = floor(n/p^k)) > 0,
                v[i] += cont;
                k++;
                );
                );
                return(v);
                }

                sieve(nmin,nmax,pmax) =
                {
                local(v,i,j,a,b,apb,amb);
                \\ Integers of the form n! +/- n# +/- 1 are not divisible by any
                \\ prime up to n, and since the minimum value of n that we're
                \\ considering is nmin, then we'll start there. Sure, we'll waste
                \\ a little time checking whether the primes from nmin to a given n
                \\ divide n! +/- n# +/- 1, for n > nmin, but that's not too costly
                \\ anyway.
                j = 0;
                forprime(p=nmin,pmax,
                if(bitand(j++,255)==0,
                print("Sieving "p"...");
                );
                v = legendre_factorial(nmin);

                \\ a == nmin!/nmin# (mod p)
                a = Mod(1,p);
                i = 0;
                forprime(q=2,floor(nmin/2),
                a *= Mod(q,p)^v[i++];
                );

                \\ b == nmin# (mod p)
                b = Mod(1,p);
                forprime(q=2,nmin,
                b *= Mod(q,p);
                );

                \\ Now a == nmin! (mod p)
                a *= b;

                for(i=nmin,nmax,
                apb = a + b;
                amb = a - b;

                if(apb == Mod(p-1,p),
                write("composite_"nmin"_"nmax, i"! + "i"# + 1, "p);
                );
                if(apb == Mod(1,p),
                write("composite_"nmin"_"nmax, i"! + "i"# - 1, "p);
                );
                if(amb == Mod(p-1,p),
                write("composite_"nmin"_"nmax, i"! - "i"# + 1, "p);
                );
                if(amb == Mod(1,p),
                write("composite_"nmin"_"nmax, i"! - "i"# - 1, "p);
                );

                a *= Mod(i+1,p);
                if(isprime(i+1),
                b *= Mod(i+1,p);
                );
                );
                );
                }


                [Non-text portions of this message have been removed]
              • jim_fougeron
                One other issue Décio is running into, is that our binary linux builds have a static linked GMP which may or may not be optimal for a certain CPU. Now
                Message 7 of 9 , Feb 8, 2005
                • 0 Attachment
                  One other issue Décio is running into, is that our "binary" linux
                  builds have a static linked GMP which may or may not be optimal
                  for a certain CPU. Now with gmp playing a much heavier roll
                  (espcially when dealing with factoring), it might be wise to
                  have more than one build, or build linux binaries with dynamic
                  linkage of GMP.

                  Under Win32, I did this by making a truely stand along GMP system
                  for PFGW which has a built in "default" gmp (for the masses), and
                  has special built GMP dll's for the speed freaks, with DLL's
                  optimally tuned for many CPU families.

                  GMP is now used in exponetation under a certain set of sizes (depends
                  on CPU and type of number), and also in factoring. The latest
                  experimental alpha, also now has GMP in the exponentation in the
                  N-1 proofs (again for numbers under a certain set of bit sizes)

                  Thus, getting a correct GMP for the CPU running on, is becoming
                  MUCH more critical than it was in the past (although, I have always
                  considered it critical ;)

                  Jim.

                  --- In primenumbers@yahoogroups.com, Décio Luiz Gazzoni Filho
                  <decio@d...> wrote:
                  > On Wednesday 09 February 2005 01:59, you wrote:
                  > > Décio Luiz Gazzoni Filho wrote:
                  > > > 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.
                  > >
                  > > Trial factoring almost always makes sense if nothing else is used.
                  > > I did consider your case carefully and you may want to think
                  twice before
                  > > dismissing me. I have written a lot of both sieves and individual
                  trial
                  > > factoring programs. My sieves hold around 70 different current
                  prime
                  > > records: http://hjem.get2net.dk/jka/math/myrecords.htm (2 records
                  did not
                  > > use my sieves) Sorry for bragging but knowing what somebody has
                  done may be
                  > > helpful when deciding whether to follow their advice or spend
                  time studying
                  > > their writings.
                  >
                  > I'm not doubting your claims, rest assured (:
                  >
                  > Problem is, I'm seeing some unusually slow timings for PFGW trial
                  factoring.
                  > Both David and Jim wrote me off-list to point that out. In the
                  context of
                  > slow timings and the expected removal rate, I believe my comment
                  makes sense.
                  >
                  > > The default trial factor depth in pfgw -f tries to be near
                  optimal, i.e.
                  > > stop when the "expected" factoring time matches prp time (although
                  > > different prp times for different forms is not taken into
                  account).
                  >
                  > Except that it doesn't take into account the fact that n! +/- n# +/-
                  1 isn't
                  > divisible by primes up to n; Jim suggested that I try -f35 instead
                  of the
                  > default, as that's near optimal according to his experiments.
                  >
                  > > I wrote:
                  > > > The recent development versions of pfgw will factor around 50%
                  of the
                  > > > candidates with the default trial factor limit.
                  > >
                  > > A recent development version can be found at
                  > > http://groups.yahoo.com/group/openpfgw/files/
                  > > It has _much_ faster trial factoring of large numbers, by the way
                  based on
                  > > my TreeSieve code.
                  > > Factoring to 127e6 is not 3/4 but 1/8 as costly as the prp test
                  itself.
                  > > That is definitely worth the effort when around 50% of candidates
                  are
                  > > factored.
                  >
                  > Yes, in that case it is.
                  >
                  > > pfgw versions slower at factoring will also choose a suitable
                  default limit
                  > > for pfgw -f, e.g.:
                  > >
                  > > C:>pfgw -f -o -q10000!+10000#+1
                  > > PFGW Version 20041129.Win_Stable (v1.2 RC1d) [FFT v23.8]
                  > >
                  > > trial factoring to 11300619
                  > > 10000!+10000#+1 has no small factor.
                  >
                  > I should grab that version -- I was running the latest compiled
                  binary for
                  > Linux that was available in the files area of the openpfgw group.
                  >
                  > > Factoring to 11.3e6 with this version also took around 1/8 of prp
                  time.
                  > > Around 43% of your candidates near n=10000 will be factored by
                  11.3e6.
                  > > Also definitely worth 1/8 of the prp time (less when a factor is
                  found).
                  > >
                  > > > 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?
                  > >
                  > > Maybe, after trial factoring to some point (above 10000). It
                  depends on the
                  > > available programs and whether you want to set it up. Adding -f
                  in a pfgw
                  > > call is extremely easy and should always be done if no other
                  factoring has
                  > > been performed.
                  > >
                  > > > > 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;
                  > >
                  > > ...
                  > >
                  > > > 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.
                  > >
                  > > Read my code again. This caching is exactly what I did, but in a
                  practical
                  > >
                  > > order:
                  >
                  > Sorry about that. I should really get some sleep. Turns out that I
                  reinvented
                  > the wheel for lack of concentration to properly read your code!
                  >
                  > > > > for each prime p below trial factor limit
                  > > > > ..for n from 1 to nmax
                  > >
                  > > If you swap the (for p, for n) order then you have to store 2
                  residues for
                  > > every prime below the trial factor limit.
                  > > That may require more than 1 GB for a high limit.
                  >
                  > Correct. Although I didn't realize that I had even specified a
                  particular loop
                  > order! But as I was writing my code (before receiving this email) I
                  was
                  > already using the (for p, for n) order.
                  >
                  > > Can you combine this fast caching method with using the prime
                  factorization
                  > > of n as you suggest (except for initialization if you don't start
                  at n=1)?
                  > > I considered the factorization method but thought my suggestion
                  would be
                  > > much faster.
                  >
                  > I'm writing the code right now. Hope I don't fall asleep over my
                  keyboard
                  > before finishing it, though.
                  >
                  > Using the explicit prime factorization of n! (from Legendre's
                  theorem) is only
                  > useful if you're not starting from n = 1, otherwise the result
                  cache does the
                  > job. As the range n <= 10000 is already done, I believe it's worth
                  it.
                  >
                  > Décio
                  >
                  >
                  > [Non-text portions of this message have been removed]
                • Jens Kruse Andersen
                  ... Avoiding divisibility by small primes is irrelevant for the trial factor limit. After n is passed, every prime p has estimated chance 1/p of being a factor
                  Message 8 of 9 , Feb 9, 2005
                  • 0 Attachment
                    I wrote:
                    > > The default trial factor depth in pfgw -f tries to be near optimal, i.e.
                    > > stop when the "expected" factoring time matches prp time (although
                    > > different prp times for different forms is not taken into account).

                    Décio wrote:
                    > Except that it doesn't take into account the fact that n! +/- n# +/- 1 isn't
                    > divisible by primes up to n; Jim suggested that I try -f35 instead of the
                    > default, as that's near optimal according to his experiments.

                    Avoiding divisibility by small primes is irrelevant for the trial factor
                    limit. After n is passed, every prime p has estimated chance 1/p of being a
                    factor in a sufficiently "random" form without special factor properties.

                    The default -f is much better than no factoring, but experimentation can
                    sometimes find a better limit.
                    A lot of things play in so it is hard for pfgw to guess the best limit when it
                    doesn't first time a partial factoring and prp'ing of the particular number
                    (and pfgw shouldn't start doing that).
                    I wrote "different prp times for different forms is not taken into account".
                    This is one thing pfgw could do but it requires analyzing the form before
                    factoring.

                    > I should grab that version -- I was running the latest compiled binary for
                    > Linux that was available in the files area of the openpfgw group.

                    Note that development versions at openpfgw are often less tested than released
                    versions at primeform group.
                    Factors can be trivially verified so a possibility is:
                    Factor with development, verify factors, prp with release.

                    --
                    Jens Kruse Andersen
                  • jim_fougeron
                    ... The point Jens is making, can not be stressed enough. While I am very partial to the current experimental developement version of PFGW, and that is
                    Message 9 of 9 , Feb 9, 2005
                    • 0 Attachment
                      --- In primenumbers@yahoogroups.com, "Jens Kruse Andersen"
                      <jens.k.a@g...> wrote:
                      >Décio wrote:
                      >>I should grab that version -- I was running the latest compiled
                      >>binary for Linux that was available in the files area of the
                      >>openpfgw group.
                      >
                      >Note that development versions at openpfgw are often less tested
                      >than released versions at primeform group.
                      >Factors can be trivially verified so a possibility is:
                      >Factor with development, verify factors, prp with release.

                      The point Jens is making, can not be stressed enough. While I am
                      very "partial" to the current "experimental" developement version
                      of PFGW, and that is where I focus all of my developement time adding
                      new things, and enhancing performance, keep in mind that it IS
                      experimental code. The current dev version is so experimental that
                      it will not even build under Linux (due to running with 2 versions
                      of the Woltman FFT libraries while porting all of code over to use
                      the newest version of that library).

                      Also keep in mind, that the factoring code has been pretty much
                      re-written (as you see by the 10x speed improvement). However, just
                      a few days ago, I did fix a fatal bug in that code, which you can
                      demonstrate on your December Linux build, by simply doing a:
                      pfgw -f 5000#
                      That will crash, due to a division by zero problem (i.e. the WHOLE
                      tree was a factor of the number, and thus the whole tree's modulus
                      was zero). Thus, even though the tree-factorize code has been in
                      the dev version since day one (since the first "stable" 1.2 was
                      released, and the dev branch started off), it still has some nits
                      in it (thus, that is WHY it is not in the stable release, even
                      though it was running prior to the stable cut-off).

                      Also, the exponenation code, which was scattered throughout many
                      places in the source (but pretty well tested at each of those), is
                      now in a singlular function, and all of those "locations" in the
                      code call a common expmod() function. The exponentation code also
                      seems to be "pretty stable", and with only one set of code (vs a hand
                      full before), when there is a bug, fixing it is easier, due to
                      all processing filtering down into that single function. However,
                      just as was seen in the "pretty stable" tree factorize code, there
                      simply has not been enough testing to fully validate that everything
                      is correct.

                      Also, the N-1 proof has been totally re-written (porting the existing
                      stable N-1 test code was just too much of a nightmare into the v24
                      FFT library, so it was re-written). This code is WAY too fresh to
                      rely on. At the same time, the N+1 and "combined" (-tc) testing
                      code is also being re-written. Then about 20% of the "core" pfgw
                      code will be stripped out (all of the support code for the v23 FFT,
                      along with the older proving code which was integrated into the
                      expression engine).

                      That is why Jens made a "blanket" statement about when to use the
                      dev version, and when NOT to use it (or at least do not FULLY rely
                      on it). It is an experimental version. It may not work right, may
                      crash, may cause your computer to make a loud screeching sound and
                      catch fire, or might cause your TV to only receive re-runs of the
                      "Teli-Tubbies" (well, I am pretty sure the last 2 warnings can be
                      ignored :) However, many of the "recent" requests (such as faster
                      factoring, IBDWT, enhanced script features), are only available in
                      that version. Just use the version with caution, and keep me
                      informed of problems with it, and again, it should NOT be used
                      for testing at this time, without additional validation of anouther
                      application (including an older "stable" PFGW version).

                      Jim.
                    Your message has been successfully submitted and would be delivered to recipients shortly.