Q: Reasonable time to find a factor
 

Can anybody please provide some overview of what are roughly the estimated average
times to find a factor of a Mp (prime p, Mp a known composite) as a function of p or a
table of ranges and the respective times, using the best known software/algorithms
running on contemporary commodity hardware?

Something like

up to x: in microseconds
up to y: few seconds at most, usually
up to z: few days/weeks

etc

from nn bits: no one knows for sure, expected propbably at least foo bars for p == xx

Thanks in advance for any insight.

You will have to be more specific. you want to completly factorise or just find one factor? With what kind of hardware?

For example M1277, wich has no factor know so far, has an estimated factoring time of 660 cpu year (see [url]http://mersenneforum.org/showpost.php?p=486010&postcount=10[/url])
However M750,999,653 has a found factor, and it can be found ina few millisecond.

[QUOTE=firejuggler;487266]You will have to be more specific. you want to completly factorise or just find one factor? With what kind of hardware?[/QUOTE]

Not completely factorize, just find any divisor, prime or not.

HW: For example, say a middle class, 2-core Intel i5-6470 @3GHz, 16GB machine.

I assume you want to find new factors. If you have a half decent graphics cards you can use it for Trial Factoring and find multiple factors per day (depending on the range). With the CPU you can do P-1 or ECM, but it can take days to find a factor (they're usually larger than the TF factors).

[QUOTE=jnml;487267]Not completely factorize, just find any divisor, prime or not.

HW: For example, say a middle class, 2-core Intel i5-6470 @3GHz, 16GB machine.[/QUOTE]

Depends on if you have a GPU (Graphics Card) or only the CPU.

A newer CPU will produce 5-10 GhzDays (A GIMPS unit of work) per core per day.
A newer GPU doing TF will produce 500-1000 GhzDays per day.

At a high level:
- If you have a GPU use it for TF and it could find a several factors daily.
- If you only have a CPU and can allocate at least 1G+ of RAM use it for P-1 and expect a couple factors per month per core.
- If you have very little RAM to spare use the CPU for ECM and expect at best about 1 factor per month total.
- You can use the CPU for TF as well (some do); expect a couple per week.

It you want to do some deeper analysis read on....

This page [url]http://www.mersenne.ca/credit.php[/url] can calculate the GzhDays required for whatever assignment you are doing.
- Choose Trial, ECM or P-1 Factoring
- Enter the required parameters
- For TF it will give the GhzDays required and the Chance of a Factor (About 1/x where x is the TF bit level)
- For P-1 it will give the GhzDays only: Then you can use this: [url]http://www.mersenne.ca/prob.php[/url] to find the Chance of a Factor for P-1
- For ECM it gives GhzDays only. Change of a Factor for ECM is a little harder to find but it is quite low. Feedback from this forum suggests it is the least efficient method for actoring. Further it is really only worthwhile for small exponents (<20,000,000)

Using the above you can calculate for your CPU/GPU the GhzDays for assignments of interest and the corresponding Chance of a Factor.

If your are running the LL test, it does not look for factors. So, it won't find them, no matter how long you run them.

If you are doing Trial Factoring, then the time does vary based upon the size of the exponent P ins 2[SUP]P[/SUP]-1 and the bit level you are looking at. The lower the bit number, the faster the search and the higher the odds of finding a factor. The higher the exponent and the lowest possible bit level of a factor moves up. And thus larger bit numbers are processed faster on larger exponents.

Your odds of finding a factor while doing TF are about 1/bit number. They are additive, so if you are going from 40 bits to 50 bits you add 1/41 + 1/42 .... 1/49 + 1/50.

[QUOTE=Uncwilly;487292]Your odds of finding a factor while doing TF are about 1/bit number.[/QUOTE]

Please note that this is an unproven guestimate.

GPU72 has been [URL="https://www.gpu72.com/reports/factor_percentage/"]collecting empirical data[/URL] on factoring attempts vs. factors found, and the actual percentage of factors found per depth attempted tends to be less than this formula gives.

(Please also note that this query is against the raw database of a few million records, so it's rather expensive. Please give the server a few seconds to render the report.)

[QUOTE=chalsall;487294]Please note that this is an unproven guestimate.
[/QUOTE]

The estimate has a solid logical basis underlying it. Just how large the [URL="https://en.wikipedia.org/wiki/Prime_number_theorem#cite_ref-10"]error term[/URL] is isn't very well understood (our understanding hinges on that most famous of hypotheses), but we do know conclusively that it's about as good as possible first approximation.

[QUOTE=chalsall;487294]
...the actual percentage of factors found per depth attempted tends to be less than this formula gives.[/quote]

I believe this follows as well from the same underlying mathematics, see e.g. [URL="https://en.wikipedia.org/wiki/Skewes%27s_number"]Skewes' number[/URL].

Some p ( those that are both 3 mod 4 and 2p+1) show that it depends on p.

[QUOTE=chalsall;487294]Please note that this is an unproven guestimate.

GPU72 has been [URL="https://www.gpu72.com/reports/factor_percentage/"]collecting empirical data[/URL] on factoring attempts vs. factors found, and the actual percentage of factors found per depth attempted tends to be less than this formula gives.[/QUOTE]

Just a theory:

Could it also be that once P-1 is done (since it "steals" a few factors) that the TF hit ratio for subsequent TF's will be lower than expected?

Less so with a minimal P-1 (i.e. B1-B2); more so with a stronger P-1?

Your "emperical" report shows a hit ratio closer to this "unproven guestimate" for LL than for DC. I think that might be because by the time we are doing DC-TF there is a much greater chance P-1 has already been done.

[QUOTE=Dubslow;487296]The estimate has a solid logical basis underlying it.[/QUOTE]

Trust a mathematician to reject the empirical... :wink:

Empirical: TF'ing from 72 to 73; 569,553 attempts, 7,682 factors found, 1.349% success rate. Predicted: 1.370%

73 to 74: 503,758 attempts, 6,403 factors found, 1.271%. Predicted: 1.351%.

74 to 75: 380,496, 4,611, 1.212%. Predicted: 1.333...

I will agree that given an infinite sample set that /maybe/ the empirical and the theoretical would converge. On the other hand, maybe not....

"The most exciting phrase to hear in science, the one that heralds new discoveries, is not 'Eureka!' but 'That's funny...'" -- Asimov