Presieving using B1 bounds

[JuanTutors]

This is a question about prefactoring before either a DC or a first time test.

1. Suppose M was TF'd to 2^n, the B1 value for P-1 factoring is known, and an LL/PRP test was done on M. Before doing a DC on M, it is possible to take that B1 value to do an additional presieve of the values between 2^n and 2^(n+1), do a second TF, and then do a DC. My question is, is that beneficial time-wise at all?

I'm not sure what fraction of the coefficients between 2^n and 2^(n+1) are B1-smooth, how long computationally it would take to presieve the coefficients, and how that compares to the time it takes to DC.

2. I guess the same question holds about doing a second TF after the P-1 factoring before doing the first-time LL/PRP test.

[ixfd64]

Part 44 of this post may be of interest to you: https://mersenneforum.org/showpost.p...23&postcount=6

[kriesel]

Originally Posted by ixfd64

Part 44 of this post may be of interest to you: https://mersenneforum.org/showpost.p...23&postcount=6

Note, #44 revised / expanded just now for completeness.

[kriesel]

Originally Posted by JuanTutors

This is a question about prefactoring before either a DC or a first time test.

1. Suppose M was TF'd to 2^n, the B1 value for P-1 factoring is known, and an LL/PRP test was done on M. Before doing a DC on M, it is possible to take that B1 value to do an additional presieve of the values between 2^n and 2^(n+1), do a second TF, and then do a DC. My question is, is that beneficial time-wise at all?

I'm not sure what fraction of the coefficients between 2^n and 2^(n+1) are B1-smooth, how long computationally it would take to presieve the coefficients, and how that compares to the time it takes to DC.

2. I guess the same question holds about doing a second TF after the P-1 factoring before doing the first-time LL/PRP test.

Knowing B1 may be enough input info for what you suggest about additional TF. It is not enough to extend the P-1 factoring to higher bounds. Generally the stage one P-1 file is not saved after P-1 is completed. Even if it is saved, it is likely to be on someone else's computer on the other side of the planet, and user B has no email address or other path to obtain it from user A.
The partial overlap of TF and P-1 provides some partial double-check between factoring methods. It has little percentage impact on overall GIMPS throughput.

[JuanTutors]

Wow, I had a feeling that the numbers would be around those numbers. The 25% I expected, but I didn't expect the 0.19% to be so big, and I didn't expect the transition would be such an enormous amount of work.

What about something as simple as this: Say a computer (gpu likely) is doing TF from scratch, meaning from 2p+1, 4p+1, .... What if it does an extremely fast P-1 test with B1=97 before trial factoring. That should take max 2 seconds of computation. Then the computer eliminates all k values that are smooth for B1=97. This B1 value need not be reported nor its residue stored. Does that speed up anything? I did choose B1=97 somewhat arbitrarily. Some math could be done to find an optimal B1 initial value, but I suspect that that B1 would be exceedingly small, maybe closer to 1000.

[kriesel]

Read the rest, not just #44 of the trial factoring concepts, and related material. B1 very small is a waste of time.


Or, go ahead and code what you propose, test it, announce it.

[JuanTutors]

Originally Posted by kriesel

Read the rest, not just #44 of the trial factoring concepts, and related material. B1 very small is a waste of time.


Or, go ahead and code what you propose, test it, announce it.

I just read a paper on it. If one were to sieve 128-smooth numbers from k=1 to k=2^56, one would will save 1 second per year on average, not counting the sieving step, which makes the time negative. Only about 1% of numbers between 1 and 2^25 are 97-smooth, and about 1.6% of numbers between 1 and 2^25 are 128-smooth. I don't think the time spent presieving and time saved not factoring ever meet.