How likely should "very unlikely" be?

SethTro · 2023-03-03, 04:05

Looking at two recent factors found 13007 and 20149. Both of the found factors are below the estimated t-level and below the "TF below 2^X is very unlikely to find new factors due to ECM effort."

13007's estimated t-level is 49.5 and below 2^160 is very unlikely, yet the factor had 154.2 bits and no newer curves have been submitted.
20149's estimated t-level is 40.9 and below 2^130 is very unlikely, yet the found factor had 127.9 bits. In this case the factor was found as part of 1500 curves so the estimated t-level was likely lower when it was found.

Searching other factors of small exponents from the last year I found several other factors matching this pattern.

11329, 127 bit factor found, < 130 bits "very unlikely", no curves since
13007, 154 bit factor found, < 160 bits "very unlikely", no curves since
11981, 121 bit factor found, < 130 bits "very unlikely", many curves (~2k) since
20411, 114 bit factor found, < 130 bits "very unlikely", many curves (~2k) since
22133, 120 bit factor found, < 130 bits "very unlikely", part of 2k curves
22409, 122 bit factor found, < 130 bits "very unlikely", part of 2k curves
22751, 122 bit factor found, < 130 bits "very unlikely", part of 2k curves
28837, 106 bit factor found, < 114 bits "very unlikely", no curves since
30313, 107 bit factor found, < 114 bits "very unlikely", no curves since
30703, 122 bit factor found, < 125 bits "very unlikely", no curves since
...

It looks like many of these were found when fbaur started working on t45 or by nordi working on t40.

Drilling in on 22133 mersenne.org says the estimated t-level is 40.7 and hides it's calculation that "approx chance of missed factor: <135.2-bit: 37%; <118.6-bit: 0.5%" while prominently displaying "very unlikely < 2^130 (t39)".
It seems that "very unlikely" might mean as high as 20% here.

In general I assume factoring progress, and t-level, is under reported if calculated only from the ECM curves submitted. Ryan, one-off gmp-ecm work, P-1, and P+1 all remove factors that ECM would otherwise found. so it's a little surprising to find so many examples of recent exponents being found several digits below their calculated t-level.

Looking at this a different way, in the 600 exponents in the range I reviewed (15,000 - 31,000) we'd expect to find 13% of them to have a t35-t40 factor and for 35% of the time for it have been missed at t40 meaning finding 27 factors below the calculated t-level and <1 factor below t35. So possibly nordi, fbaur, and others raised the ecm level by 5 digits for this range over the last year and the t-level probabilities are working as expected.

Rubiksmath · 2023-03-03, 04:13

I mean the very first ECM factor that I found was for M222613, an 87.2 bit factor when the T-level was approximately 30.3=98 bits. In general, mersenne.ca is more conservative with T-level estimates and usually estimates a bit or two lower T level than mersenne.org. Don't know if that has anything to do with it.

Edit: I do often make mistakes when working out the amount of bits in numbers because I often make the mistake that the smallest 35 digit number is 10^35, in fact it is 10^34, so a mistake like that does have potential to overestimate the number of bits by 3. If that mistake was being made on mersenne.org it would overestimate T-level by a bit but I think its more likely the T-level estimating functions are different between mersenne.org and mersenne.ca.

Prime95 · 2023-03-03, 05:28

The "very unlikely" text was added to strongly discourage users from doing TF when ECM is much more appropriate.

We're happy to change the algorithm and/or message as long as that goal is still met.

Andrew Usher · 2023-03-03, 13:27

I agree that it is being set too high, but also that it is a reasonable message to have. My suggestion would be to use the 0.5% level already calculated and round it down - that's 99.5% of the chance removed by ECM, which is near what most people would consider 'very unlikely' to mean - and if it would be below 68 (roughly T25), omit the message, as it is misleading to admit the possibility of doing TF below TJAOI level.

Actually, knowing about TJAOI and his factoring limit is just as important to avoiding useless TF, but there are very few unfactored exponents where that comes into play, and everyone doing factored exponents, it seems, already knows.

2023-03-03, 04:05	#1
SethTro "Seth" Apr 2019 2·3·83 Posts	How likely should "very unlikely" be? Looking at two recent factors found 13007 and 20149. Both of the found factors are below the estimated t-level and below the "TF below 2^X is very unlikely to find new factors due to ECM effort." 13007's estimated t-level is 49.5 and below 2^160 is very unlikely, yet the factor had 154.2 bits and no newer curves have been submitted. 20149's estimated t-level is 40.9 and below 2^130 is very unlikely, yet the found factor had 127.9 bits. In this case the factor was found as part of 1500 curves so the estimated t-level was likely lower when it was found. Searching other factors of small exponents from the last year I found several other factors matching this pattern. 11329, 127 bit factor found, < 130 bits "very unlikely", no curves since 13007, 154 bit factor found, < 160 bits "very unlikely", no curves since 11981, 121 bit factor found, < 130 bits "very unlikely", many curves (~2k) since 20411, 114 bit factor found, < 130 bits "very unlikely", many curves (~2k) since 22133, 120 bit factor found, < 130 bits "very unlikely", part of 2k curves 22409, 122 bit factor found, < 130 bits "very unlikely", part of 2k curves 22751, 122 bit factor found, < 130 bits "very unlikely", part of 2k curves 28837, 106 bit factor found, < 114 bits "very unlikely", no curves since 30313, 107 bit factor found, < 114 bits "very unlikely", no curves since 30703, 122 bit factor found, < 125 bits "very unlikely", no curves since ... It looks like many of these were found when fbaur started working on t45 or by nordi working on t40. Drilling in on 22133 mersenne.org says the estimated t-level is 40.7 and hides it's calculation that "approx chance of missed factor: <135.2-bit: 37%; <118.6-bit: 0.5%" while prominently displaying "very unlikely < 2^130 (t39)". It seems that "very unlikely" might mean as high as 20% here. In general I assume factoring progress, and t-level, is under reported if calculated only from the ECM curves submitted. Ryan, one-off gmp-ecm work, P-1, and P+1 all remove factors that ECM would otherwise found. so it's a little surprising to find so many examples of recent exponents being found several digits below their calculated t-level. Looking at this a different way, in the 600 exponents in the range I reviewed (15,000 - 31,000) we'd expect to find 13% of them to have a t35-t40 factor and for 35% of the time for it have been missed at t40 meaning finding 27 factors below the calculated t-level and <1 factor below t35. So possibly nordi, fbaur, and others raised the ecm level by 5 digits for this range over the last year and the t-level probabilities are working as expected. Last fiddled with by SethTro on 2023-03-03 at 04:06

2023-03-03, 04:13	#2
Rubiksmath Sep 2022 5³ Posts	I mean the very first ECM factor that I found was for M222613, an 87.2 bit factor when the T-level was approximately 30.3=98 bits. In general, mersenne.ca is more conservative with T-level estimates and usually estimates a bit or two lower T level than mersenne.org. Don't know if that has anything to do with it. Edit: I do often make mistakes when working out the amount of bits in numbers because I often make the mistake that the smallest 35 digit number is 10^35, in fact it is 10^34, so a mistake like that does have potential to overestimate the number of bits by 3. If that mistake was being made on mersenne.org it would overestimate T-level by a bit but I think its more likely the T-level estimating functions are different between mersenne.org and mersenne.ca. Last fiddled with by Rubiksmath on 2023-03-03 at 04:20

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Is "mung" or "munged" a negative word in a moral sense?	Uncwilly	Lounge	15	2020-04-14 18:35
GQQ: a "deterministic" "primality" test in O(ln n)^2	Chair Zhuang	Miscellaneous Math	21	2018-03-26 22:33
Stockfish game: "Move 8 poll", not "move 3.14159 discussion"	MooMoo2	Other Chess Games	5	2016-10-22 01:55
Aouessare-El Haddouchi-Essaaidi "test": "if Mp has no factor, it is prime!"	wildrabbitt	Miscellaneous Math	11	2015-03-06 08:17
Would Minimizing "iterations between results file" may reveal "is not prime" earlier?	nitai1999	Software	7	2004-08-26 18:12

2023-03-03, 05:28	#3
Prime95 P90 years forever! Aug 2002 Yeehaw, FL 17×487 Posts	The "very unlikely" text was added to strongly discourage users from doing TF when ECM is much more appropriate. We're happy to change the algorithm and/or message as long as that goal is still met.

2023-03-03, 13:27	#4
Andrew Usher Dec 2022 1FB₁₆ Posts	I agree that it is being set too high, but also that it is a reasonable message to have. My suggestion would be to use the 0.5% level already calculated and round it down - that's 99.5% of the chance removed by ECM, which is near what most people would consider 'very unlikely' to mean - and if it would be below 68 (roughly T25), omit the message, as it is misleading to admit the possibility of doing TF below TJAOI level. Actually, knowing about TJAOI and his factoring limit is just as important to avoiding useless TF, but there are very few unfactored exponents where that comes into play, and everyone doing factored exponents, it seems, already knows.