Pick Your Poisson: P-1 Bounds

[LaurV]

Originally Posted by storm5510

Fact or fiction?

Fact. However, P-1 will duplicate the work every time (wasting resources, unless you have former saved files, and your software knows how to resume with extended B1, some time ago I posted a pari program who did that, the current P-1 programs we use for Gimps do not know how to resume, you will still need a couple of multiplications and squarings, it is not just "continue from here"), while ECM will not waste (almost) any of the work, because each curve is randomized. Running two or more ECM curves with the same B1 will walk different paths and later curves may find factors missed by the first, while P-1 walks the same path every time, so when you extend B1, you re-do the former work to the former B1 from scratch.
Edit: sorry, I didn't see the other page. Most probably already replied, please ignore my post if so.

[LaurV]

Originally Posted by James Heinrich

If you have the savefile from a previous P-1 run and wish to extend the bounds, Prime95 will just need to run the portion between the old bound and the new bound.

That's not exactly true. If for example, you extend the B1 from 20 to 40, there are only few primes to add, 23, 29, 31, 37, but you also need to add the new powers of the former primes, one of each 2, 3, and 5, for respectively 32, 27, and 25, those are power-limits of the primes you "overtook" on the way. To my knowledge, P95 doesn't do this (maybe newer versions do?)
Because in the first case, LCM(B1) was 2^4*3^2*5*7*11*13*17*19, while in the second case you have 2^5*3^3*5^2*7*11*13*17*19*23*29*31*37, and you have to compensate for all the missing primes.

[preda]

Hi, recently I revisited the P-1 calculator that's included with GpuOwl's source code https://github.com/preda/gpuowl/blob/master/pm1/pm1.cpp

The calculator is a small stanalone C++ program; to try it out check out gpuowl's source and invoke "make" in the pm1/ subfolder.

In the calculator update, an error was fixed that was resulting in a bit of over-optimistic second-stage probabilities. In addition to that, a new simpler bounds cost model is implemented, and hopefully a more useful and informative output is generated.

How to use it: invoke the executable "pm1" with an exponent and a "factored-to" bits, e.g.:
./pm1 105M 76

This will output a few B1/B2 choices, one per line -- people should chose among them depending on how badly they desire to find P-1 factors. The first line is the most efficient option, which should be chosen if one only cares about efficiency with little additional value assigned to a factor.

$ ./pm1 105M 76

B1= 2.0M B2= 25M | 4.421% (2.265% + 2.156%) | work 1.371% (0.427% + 0.944%) | B2/B1=12, misses 9.64% of B2-smooth factors
B1= 3.0M B2= 50M | 5.210% (2.616% + 2.594%) | work 2.496% (0.641% + 1.856%) | B2/B1=17, misses 9.92% of B2-smooth factors
B1= 4.5M B2= 80M | 5.836% (2.996% + 2.840%) | work 3.863% (0.961% + 2.902%) | B2/B1=18, misses 9.12% of B2-smooth factors
B1= 6.0M B2=120M | 6.374% (3.281% + 3.093%) | work 5.567% (1.282% + 4.285%) | B2/B1=20, misses 8.81% of B2-smooth factors
B1= 8.0M B2=150M | 6.733% (3.580% + 3.153%) | work 6.978% (1.709% + 5.269%) | B2/B1=19, misses 7.89% of B2-smooth factors
B1= 9.0M B2=180M | 6.982% (3.707% + 3.275%) | work 8.207% (1.923% + 6.285%) | B2/B1=20, misses 7.83% of B2-smooth factors

Each line contains the bounds, the chances of finding a factor, the estimated amount of P-1 overhead when no factor is found, the ratio B2/B1 and the percent of B2-smooth factors that are not (B1,B2)-smooth, i.e. would be missed because of a too-low B1.

The bounds are by default computed based on the new "merged PRP+P-1" first stage cost; but there is an option -legacy which can be passed to estimate bounds for the classic P-1:

./pm1 105M 76 -legacy

B1= 0.5M B2= 20M | 3.627% (1.274% + 2.354%) | work 1.540% (0.721% + 0.819%) | B2/B1=40, misses 21.49% of B2-smooth factors
B1= 0.8M B2= 40M | 4.381% (1.573% + 2.808%) | work 2.733% (1.154% + 1.579%) | B2/B1=50, misses 20.20% of B2-smooth factors
B1= 1.2M B2= 70M | 5.056% (1.861% + 3.195%) | work 4.413% (1.730% + 2.683%) | B2/B1=58, misses 18.94% of B2-smooth factors
B1= 1.7M B2=100M | 5.562% (2.132% + 3.431%) | work 6.206% (2.451% + 3.755%) | B2/B1=59, misses 17.38% of B2-smooth factors
B1= 2.0M B2=130M | 5.892% (2.265% + 3.628%) | work 7.703% (2.884% + 4.819%) | B2/B1=65, misses 17.06% of B2-smooth factors
B1= 2.5M B2=160M | 6.216% (2.455% + 3.761%) | work 9.465% (3.605% + 5.860%) | B2/B1=64, misses 16.04% of B2-smooth factors

[preda]

The program also allows to specify a fixed B1 or B2, and in that situation displays options for the other bound. Examples below with fixed B1=1M, or fixed B2=50M (note, the values below are good with the merged PRP+P1 first stage, unless -legacy is used)

105M 76 -B1 1M
B1= 1.0M B2= 25M | 4.132% (1.728% + 2.404%) | work 1.205% (0.214% + 0.991%) | B2/B1=25, misses 15.55% of B2-smooth factors
B1= 1.0M B2= 40M | 4.502% (1.728% + 2.773%) | work 1.783% (0.214% + 1.569%) | B2/B1=40, misses 18.01% of B2-smooth factors
B1= 1.0M B2= 70M | 4.948% (1.728% + 3.220%) | work 2.906% (0.214% + 2.692%) | B2/B1=70, misses 20.67% of B2-smooth factors
B1= 1.0M B2= 90M | 5.152% (1.728% + 3.423%) | work 3.639% (0.214% + 3.425%) | B2/B1=90, misses 21.76% of B2-smooth factors
B1= 1.0M B2=120M | 5.386% (1.728% + 3.658%) | work 4.722% (0.214% + 4.508%) | B2/B1=120, misses 22.95% of B2-smooth factors
B1= 1.0M B2=140M | 5.512% (1.728% + 3.784%) | work 5.435% (0.214% + 5.222%) | B2/B1=140, misses 23.55% of B2-smooth factors

105M 76 -B2 50M
B1= 2.0M B2= 50M | 5.033% (2.265% + 2.768%) | work 2.328% (0.427% + 1.901%) | B2/B1=25, misses 12.98% of B2-smooth factors
B1= 3.0M B2= 50M | 5.210% (2.616% + 2.594%) | work 2.496% (0.641% + 1.856%) | B2/B1=17, misses 9.92% of B2-smooth factors
B1= 4.5M B2= 50M | 5.364% (2.996% + 2.368%) | work 2.751% (0.961% + 1.790%) | B2/B1=11, misses 7.25% of B2-smooth factors
B1= 5.0M B2= 50M | 5.400% (3.099% + 2.302%) | work 2.836% (1.068% + 1.768%) | B2/B1=10, misses 6.63% of B2-smooth factors
B1= 6.0M B2= 50M | 5.459% (3.281% + 2.178%) | work 3.007% (1.282% + 1.725%) | B2/B1= 8, misses 5.61% of B2-smooth factors
B1= 7.0M B2= 50M | 5.505% (3.440% + 2.065%) | work 3.178% (1.495% + 1.682%) | B2/B1= 7, misses 4.82% of B2-smooth factors

Specifying both B1 and B2 also works, and displays the probabilities for those bounds.

Some observations from my playing with these numbers are:
- the bounds are remarkably resilient over a large range of values -- i.e. they produce similar outcomes, with similar cost; there is not a huge difference between "the best" bounds and just some other bounds.
- the rules of thumb for P1 at the wavefront might be: pick any B1 between 2M and 6M, pick any B2 between 10xB1 and 40xB1, and you should be fine.

The effect of the new "merged first stage" is to increase the B1 by about a factor of 4, and to increase a tiny bit the B2.

The probabilities of finding a factor in first-stage or second-stage are roughly equal.

A new way of seeing the bounds probability is to focus on B2 (instead of B1); basically P-1 is run to B2, with some penalty applied from a low B1 in the form of some missed factors if they happen to have multiple sub-factors in the [B1, B2] range. The percentage of such missed factors caused by the distance B1-to-B2 is now displayed.

[preda]

For what it's worth, on R7 I'm personally running with B1=9M, B2=180M for 102M-103M exponents (factored to 76bits).