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

Re: [PrimeNumbers] Re: 8147! + 8147# - 1 is 3-PRP

Expand Messages
  • Décio Luiz Gazzoni Filho
    Jim, ... First off, due to the fact that my CPU has hyperthreading, the 40 minutes figure is higher than it should, because I was running two instances of PFGW
    Message 1 of 9 , Jan 30, 2005
      Jim,

      On Sunday 30 January 2005 14:31, you wrote:
      > As for your 80s vs 40 min, I will see what I can do to get that as
      > close to 80s as possible. You list that VERY few factors are known,
      > and thus, the time should be very close to the original 80s time.
      > However, if you ARE testing a number which
      > N-1 is HIGHLY composite, with lots of unique factors (primorials are
      > the absolute best example), then PFGW will run MUCH slower for a full
      > blown proof. But if there is a factor base which is small, and which
      > the full product is larger than N^(1/3), then the N-1 test should
      > (and soon will) run at very close to the speed of a prp test. Thus
      > k*b^n+1 (or -1) tests should run at pretty close to the same speed
      > as the PRP test (when I finish the test code rewrite). There is a
      > huge overhead associated with the testing code being "incorporated"
      > into the expression parser. When we ripped the PRP code out of the
      > expression parser, and built it as a stand alone function, I believe
      > we got from 5 to 25% improvement in speed. I am hoping that the
      > testing code will contain even more overhead than this.

      First off, due to the fact that my CPU has hyperthreading, the 40 minutes
      figure is higher than it should, because I was running two instances of PFGW
      at the same time, while the initial PRP test (the one that took 80 seconds),
      was done while I was asleep and PFGW had the CPU all to its own.

      Now, I don't think you'll ever reach the 80 seconds figure, because as
      Crandall & Pomerance point out, the best you can do is be twice as slow as a
      strong PRP test. Probably even slower; I don't know any exponentiation method
      that could be used for Lucas PRP testing which is better than Lucas chains
      (at 2 ceil(log_2 n) modmuls), whereas even the simplest binary method for
      integer exponentiation will require 1.5 log_2 n modmuls on average, and
      sliding window methods can do even better. So probably 3 or 4 times is more
      realistic. Nevertheless, I don't think hyperthreading alone slowed stuff down
      7-10 times, as seen in my case. I suppose PFGW was also doing more than
      simply PRP testing my integer -- i.e. maybe it was trying to factor the
      integer or something. Maybe that accounts for the remaining difference?

      Anyway, thanks for the concern.

      Décio


      [Non-text portions of this message have been removed]
    Your message has been successfully submitted and would be delivered to recipients shortly.