Re: [PrimeNumbers] Re: 8147! + 8147# - 1 is 3-PRP
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.
[Non-text portions of this message have been removed]