I believe I know the answer, can somebody with knowledge of the source please confirm for me: How does mfaktc handle discovering composite factors?
(I've been using [url=https://www.mersenne.ca/exponent/110393069]M110393069[/url] for testing which has a thousand composite factors)
I believe mfaktc simply returns the composite factor as-discovered with no attempt to determine if said factor is composite or prime, correct?

Assuming thus, a two-part question:
a) how practical would it be for mfaktc to detect that a discovered factor is composite?
b) if factor is composite, how practical would it be for mfaktc to split the factor into primes?

[QUOTE=James Heinrich;544955]I believe I know the answer, can somebody with knowledge of the source please confirm for me: How does mfaktc handle discovering composite factors?
(I've been using [URL="https://www.mersenne.ca/exponent/110393069"]M110393069[/URL] for testing which has a thousand composite factors)
I believe mfaktc simply returns the composite factor as-discovered with no attempt to determine if said factor is composite or prime, correct?

Assuming thus, a two-part question:
a) how practical would it be for mfaktc to detect that a discovered factor is composite?
b) if factor is composite, how practical would it be for mfaktc to split the factor into primes?[/QUOTE]Wow, literally, 1013 distinct composite factors known, and 10 distinct prime factors. I thought at first the "thousand composite factors" was hyperbole.
With this in mfaktc.ini,[CODE]# possible values for StopAfterFactor:
# 0: Do not stop the current assignment after a factor was found.
# 1: When a factor was found for the current assignment stop after the
# current bitlevel. This makes only sense when Stages is enabled.
# 2: When a factor was found for the current assignment stop after the
# current class.
#
# Default: StopAfterFactor=1

StopAfterFactor=1
[/CODE] Factor=110393069,63,64 quickly returned the following:
[CODE][Sat May 09 10:09:03 2020]
UID: Kriesel/dodo-rtx2080super, M110393069 has a factor: 17743732831822018159 [TF:63:64:mfaktc 0.21 75bit_mul32_gs]
[Sat May 09 10:09:03 2020]
UID: Kriesel/dodo-rtx2080super, M110393069 has a factor: 13307799624252889361 [TF:63:64:mfaktc 0.21 75bit_mul32_gs]
[Sat May 09 10:09:03 2020]
UID: Kriesel/dodo-rtx2080super, found 2 factors for M110393069 from 2^63 to 2^64 [mfaktc 0.21 75bit_mul32_gs]
[/CODE]So yes, it returns composite factors, and the server breaks them down into prime factors along with or as part of its factor verification.
There's some question how many factors in one bit level increment mfaktx will find and report.
For this remarkable test exponent, more than two factors in a bit level is not an issue until 3 factors at 121-122 bits which would take quite a while to run as a test;
4 124-125
5 154-155
6,7 183-184
8+ not found yet

Such high bit levels are not supported in mfaktx, although they could be attempted with Factor5 or Ernst's Mfactor and lots of cores and patience. (Mfaktc max 95 bit factors, mfakto max 92 bits)

More than one factor per class may be an issue. If so, its overall impact on the GIMPS project is small. See [URL]https://www.mersenneforum.org/showpost.php?p=520982&postcount=5[/URL]
Although, up to 10 factors / class may be provided for. [URL]https://www.mersenneforum.org/showpost.php?p=410784&postcount=35[/URL]

[QUOTE=TheJudger;205332]Hi,

good news:
Yesterday I've added more than 200 known factors to the selftest.
Every single factor was verified using my code. :)
[B]In some cases it misses factors when there are mutliple factors in one class close together[/B] but this is not critical. The is a known problem since the first version... This has nothing to do with the calculations itself, it is just how the results are returned from the GPU to the CPU.
-----
Raw speed on my GTX 275 for M66362159 above 64 bits: ~74M candidates per second.

Siever received a nice performace improvement for free by adding "-funroll-all-loops" to the gcc options. :) (only useful for CPU-limited scenarios)

Oliver[/QUOTE](bold emphasis above is mine)
Is the issue of multiple factors in one class closely spaced causing some to be missed still present in mfaktc v0.21?
Please suggest some exponent/bitlevel combinations for test of the multiple-factors-per-class case.

[QUOTE=kriesel;544964]Wow, literally, 1013 distinct composite factors known, and 10 distinct prime factors. I thought at first the "thousand composite factors" was hyperbole.[/QUOTE]No exaggeration. :smile:
There are three exponents with 11 known factors (thereby 2036 composite factors), and nine exponents with 10 known factors, but of those really only M110393069 is in the "normal" exponent range.
[url]https://www.mersenne.ca/manyfactors.php[/url]


[QUOTE=kriesel;544964]So yes, it returns composite factors, and the server breaks them down into prime factors along with or as part of its factor verification.[/QUOTE]Yes, that is what currently happens, but I'm exploring the possibility of getting all the factoring software (Prime95, mfaktx, gpuowl, etc) modified to (ideally) return only prime factors, even when discovered as a composite.
Per your example, Factor=110393069,63,64 should ideally return something like:[code]M110393069 has a composite factor: 13307799624252889361 [TF:63:64:mfaktc 0.21 75bit_mul32_gs]
M110393069 has a factor: 1545502967 [TF:63:64:mfaktc 0.21 75bit_mul32_gs]
M110393069 has a factor: 8610659383 [TF:63:64:mfaktc 0.21 75bit_mul32_gs]
M110393069 has a composite factor: 17743732831822018159 [TF:63:64:mfaktc 0.21 75bit_mul32_gs]
M110393069 has a factor: 1545502967 [TF:63:64:mfaktc 0.21 75bit_mul32_gs]
M110393069 has a factor: 11480879177 [TF:63:64:mfaktc 0.21 75bit_mul32_gs]
found 3 prime factors for M110393069 from 2^63 to 2^64 [mfaktc 0.21 75bit_mul32_gs][/code]
Out of necessity, the server does break down any composite factors submitted, but it would be better if this could be done at the client level (without removing the server-level checks of course).


[QUOTE=kriesel;544965]Is the issue of multiple factors in one class closely spaced causing some to be missed still present in mfaktc v0.21? Please suggest some exponent/bitlevel combinations for test of the multiple-factors-per-class case.[/QUOTE]
There is no shortage of examples of exponents with multiple known factors that share a 4620-class, to quote just the ones from 100M:[code]100028477
100062071
100071661
100104131
100118399
100250341
100269131
100296149
100297643
100331219
100444901
100475647
100499617
100621361
100683689
100709621[/code]If you need a more extensive test-case list email me and I can give you a large list.
Exponents with three factors sharing a class are rare, these are the only four I found and they're all quite small:[code]150551
329009
4965187
12671587[/code]Of course, if this bug causes factors to be missed, then they wouldn't be in my list. :unsure:

[QUOTE=James Heinrich;544972]
There is no shortage of examples of exponents with multiple known factors that share a 4620-class, to quote just the ones from 100M:[code]100028477
...
100709621[/code]If you need a more extensive test-case list email me and I can give you a large list.
Exponents with three factors sharing a class are rare, these are the only four I found and they're all quite small:[code]150551
329009
4965187
12671587[/code]Of course, if this bug causes factors to be missed, then they wouldn't be in my list. :unsure:[/QUOTE]Thanks for the lists, however, what I was trying to express was an interest in any known cases of mersenne numbers with prime exponents within mersenne.ca exponent range, preferably within mersenne.org range (p<10[SUP]9[/SUP]) with multiple factors known for {same-exponent & same-bit-level & same-class-number} trifecta / slot-machine-jackpot, of bit size no larger than GIMPS would TF to normally on a gpu, which would be 76 to 92 bits or so depending on exponent. (Think intersection of 5 or 6 sets.)
That's what it would take for mfaktc or mfakto to encounter the case where normal use leads to two factors in the same class of the same bit level of the same exponent in the same run, and theoretically finding and reporting two or more factors from that single exponent, bit level, class pass.

For an exponent p, p prime, a bit level x-1 to x, x <= normal GIMPS factoring depth for p, a class any ONE of 420 or 4620, multiple factors found. Possibly even multiple factors within one block given to one of the many gpu multiprocessors.

Instead of at the mfaktc console output,[CODE]May 09 10:09 | 2271 49.5% | 0.001 n.a. | 1600.63 82485 n.a.%
M110393069 has a factor: 17743732831822018159
May 09 10:09 | 2272 49.6% | 0.001 n.a. | 1600.63 82485 n.a.%
...
May 09 10:09 | 2860 62.4% | 0.001 n.a. | 1600.63 82485 n.a.%
M110393069 has a factor: 13307799624252889361
May 09 10:09 | 2872 62.5% | 0.001 n.a. | 1600.63 82485 n.a.%[/CODE]it might look something like
[CODE]May 09 10:09 | 2271 49.5% | 0.001 n.a. | 1600.63 82485 n.a.%
M110393069 has a factor: 17743732831822018159
M110393069 has a factor: [U][I]‭17743733851853975719‬[/I][/U]
May 09 10:09 | 2272 49.6% | 0.001 n.a. | 1600.63 82485 n.a.%
[/CODE](That second, underlined one is completely fictitious)
I roughly estimated (in the attachment at [URL]https://www.mersenneforum.org/showpost.php?p=520982&postcount=5[/URL]) that we should find hundreds or thousands of such over the full scope of mersenne.org TF. If we can't identify any coincident class, bit level, exponent multiple factor finds, given how much TF has already been done, we're probably missing some (relatively few) factors this way.

[QUOTE=kriesel;544983]Thanks for the lists, however, what I was trying to express was an interest in any known cases of mersenne numbers with prime exponents within mersenne.ca exponent range, preferably within mersenne.org range (p<10[SUP]9[/SUP]) with multiple factors known for {same-exponent & same-bit-level & same-class-number} trifecta[/quote]Sorry, I forgot to filter it to same-bitlevel. That makes the list much shorter (and longer to search) but I still found 4 examples in the ~100M range:[code]106266857
109013999
109088341
109405193[/code]I only searched in 100M<110M, if you want I can expand the search to find all the examples in GIMPS range, but that'll about an hour of hammering the database.

edit: it actually didn't take as long as I feared, here's the complete list of 215 GIMPS-range exponents with same-bits-and-class factors:[code]
Factor=630907,49,50
Factor=666493,58,59
Factor=754463,49,50
Factor=976301,49,50
Factor=3902347,37,38
Factor=5279899,42,43
Factor=12953419,49,50
Factor=13904749,45,46
Factor=14298527,54,55
Factor=14749391,68,69
Factor=15162197,41,42
Factor=16892969,62,63
Factor=21474083,40,41
Factor=21633289,51,52
Factor=23740537,55,56
Factor=26936579,39,40
Factor=28247707,56,57
Factor=29235029,60,61
Factor=33838793,61,62
Factor=40917917,47,48
Factor=42416729,59,60
Factor=45632189,45,46
Factor=47916989,60,61
Factor=49678099,65,66
Factor=55346957,62,63
Factor=68168081,62,63
Factor=68989909,52,53
Factor=74542373,65,66
Factor=80374999,54,55
Factor=88079011,45,46
Factor=95469713,66,67
Factor=95669209,63,64
Factor=97267133,46,47
Factor=106266857,63,64
Factor=109013999,53,54
Factor=109088341,53,54
Factor=109405193,54,55
Factor=119525743,49,50
Factor=121156699,51,52
Factor=122522789,57,58
Factor=122617237,53,54
Factor=148380737,50,51
Factor=153225187,64,65
Factor=155676707,54,55
Factor=157910509,60,61
Factor=158599201,57,58
Factor=160739149,64,65
Factor=168830449,50,51
Factor=169014941,59,60
Factor=170473691,59,60
Factor=171953321,64,65
Factor=186375971,45,46
Factor=188904787,54,55
Factor=191462893,61,62
Factor=194559377,59,60
Factor=200995609,48,49
Factor=208394701,58,59
Factor=211943939,65,66
Factor=214423889,62,63
Factor=229769411,48,49
Factor=230055593,63,64
Factor=232507777,62,63
Factor=234028031,43,44
Factor=238430009,65,66
Factor=247462603,50,51
Factor=247575857,61,62
Factor=248693219,61,62
Factor=249720929,58,59
Factor=257601991,53,54
Factor=269222717,59,60
Factor=291566903,51,52
Factor=296611769,63,64
Factor=304843843,50,51
Factor=307436693,63,64
Factor=311095511,64,65
Factor=329514313,51,52
Factor=333341903,57,58
Factor=339049663,45,46
Factor=344226053,50,51
Factor=349871771,44,45
Factor=350800537,49,50
Factor=351511079,59,60
Factor=359812081,48,49
Factor=363424847,47,48
Factor=371542393,49,50
Factor=376397243,45,46
Factor=384190957,46,47
Factor=384327743,56,57
Factor=384394709,55,56
Factor=385356109,53,54
Factor=387013937,60,61
Factor=400835159,51,52
Factor=401102021,52,53
Factor=403918327,54,55
Factor=404784839,61,62
Factor=406884479,53,54
Factor=408071501,44,45
Factor=408188827,69,70
Factor=412778909,60,61
Factor=413747153,54,55
Factor=414824231,60,61
Factor=419128607,57,58
Factor=448196831,55,56
Factor=452020073,43,44
Factor=454609277,63,64
Factor=457729901,62,63
Factor=459228547,54,55
Factor=460167947,47,48
Factor=466220519,57,58
Factor=482584937,63,64
Factor=483370357,59,60
Factor=492464549,64,65
Factor=496423661,55,56
Factor=506824429,48,49
Factor=506895563,62,63
Factor=512880491,57,58
Factor=521816593,53,54
Factor=524087329,46,47
Factor=526005499,49,50
Factor=526014143,58,59
Factor=530664289,46,47
Factor=555551489,67,68
Factor=556353643,48,49
Factor=562335937,54,55
Factor=563680291,55,56
Factor=573868573,47,48
Factor=575599867,46,47
Factor=576806761,57,58
Factor=589429417,55,56
Factor=589746037,46,47
Factor=600953513,59,60
Factor=603618313,60,61
Factor=609388763,48,49
Factor=610146851,63,64
Factor=611741059,63,64
Factor=617863849,48,49
Factor=625400089,54,55
Factor=625521709,61,62
Factor=636713333,56,57
Factor=638366929,60,61
Factor=640381303,50,51
Factor=648452527,62,63
Factor=650749717,53,54
Factor=650927363,54,55
Factor=658195159,50,51
Factor=660280373,60,61
Factor=663891329,53,54
Factor=664600039,61,62
Factor=669290053,57,58
Factor=670620989,49,50
Factor=673902499,53,54
Factor=676343021,64,65
Factor=676611721,43,44
Factor=677065223,54,55
Factor=682014161,64,65
Factor=684732073,59,60
Factor=686029517,63,64
Factor=689997797,44,45
Factor=694678529,45,46
Factor=699891781,54,55
Factor=705410129,61,62
Factor=712472153,47,48
Factor=716225651,48,49
Factor=718763291,43,44
Factor=722281877,48,49
Factor=722671237,63,64
Factor=729992177,57,58
Factor=734571463,52,53
Factor=736663073,57,58
Factor=740774491,47,48
Factor=744550061,60,61
Factor=763981891,64,65
Factor=769814911,49,50
Factor=772482437,52,53
Factor=773120087,48,49
Factor=773476307,46,47
Factor=775692791,44,45
Factor=786451073,61,62
Factor=793651759,54,55
Factor=799473617,45,46
Factor=821119861,52,53
Factor=822585289,48,49
Factor=824575069,46,47
Factor=827289787,49,50
Factor=827753587,69,70
Factor=829322971,53,54
Factor=829364051,62,63
Factor=838613569,48,49
Factor=843158347,48,49
Factor=845831837,57,58
Factor=853745551,47,48
Factor=854811127,58,59
Factor=865444469,50,51
Factor=871148027,53,54
Factor=873514913,58,59
Factor=888502117,56,57
Factor=891816469,51,52
Factor=897478951,45,46
Factor=900842653,63,64
Factor=915151613,65,66
Factor=918760987,57,58
Factor=920280619,49,50
Factor=922496633,58,59
Factor=927602177,54,55
Factor=940010633,50,51
Factor=941381677,52,53
Factor=947056163,54,55
Factor=948726797,63,64
Factor=956418803,47,48
Factor=965694907,62,63
Factor=968105849,44,45
Factor=981595297,50,51
Factor=985010921,51,52
Factor=986248531,45,46
Factor=996709397,46,47
[/code]

[QUOTE=James Heinrich;544987]Sorry, I forgot to filter it to same-bitlevel. That makes the list much shorter (and longer to search) but I still found 4 examples in the ~100M range:[code]106266857
109013999
109088341
109405193[/code]I only searched in 100M<110M, if you want I can expand the search to find all the examples in GIMPS range, but that'll about an hour of hammering the database.

edit: it actually didn't take as long as I feared, here's the complete list of 215 GIMPS-range exponents with same-bits-and-class factors:[code]
Factor=630907,49,50
...
Factor=996709397,46,47
[/code][/QUOTE]
About 10 of those coincident factor cases are above 65 bits, and my rough estimate was 124 such for more-classes and completed to GIMPS bit levels TF; 1243 for less-classes.

Thanks, while you were getting the big list, I ran the first test case. Console output

[CODE]May 09 17:02 | 3607 78.1% | 0.216 n.a. | 7.70 82485 n.a.%
M106266857 has a factor: 15207927026741198039
M106266857 has a factor: 16752154502925095159
May 09 17:02 | 3615 78.2% | 0.217 n.a. | 7.66 82485 n.a.%[/CODE]Results file
[CODE][Sat May 09 17:02:15 2020]
UID: Kriesel/dodo-rtx2080super, M106266857 has a factor: 15207927026741198039 [TF:63:64:mfaktc 0.21 75bit_mul32_gs]
UID: Kriesel/dodo-rtx2080super, M106266857 has a factor: 16752154502925095159 [TF:63:64:mfaktc 0.21 75bit_mul32_gs]
[Sat May 09 17:02:57 2020]
UID: Kriesel/dodo-rtx2080super, found 2 factors for M106266857 from 2^63 to 2^64 [mfaktc 0.21 75bit_mul32_gs]
[/CODE]

[QUOTE=James Heinrich;544972]No exaggeration. :smile:
There are three exponents with 11 known factors (thereby 2036 composite factors), and nine exponents with 10 known factors, but of those really only M110393069 is in the "normal" exponent range.
[url]https://www.mersenne.ca/manyfactors.php[/url]


Yes, that is what currently happens, but I'm exploring the possibility of getting all the factoring software (Prime95, mfaktx, gpuowl, etc) modified to (ideally) return only prime factors, even when discovered as a composite.
Per your example, Factor=110393069,63,64 should ideally return something like:[code]M110393069 has a composite factor: 13307799624252889361 [TF:63:64:mfaktc 0.21 75bit_mul32_gs]
M110393069 has a factor: 1545502967 [TF:63:64:mfaktc 0.21 75bit_mul32_gs]
M110393069 has a factor: 8610659383 [TF:63:64:mfaktc 0.21 75bit_mul32_gs]
M110393069 has a composite factor: 17743732831822018159 [TF:63:64:mfaktc 0.21 75bit_mul32_gs]
M110393069 has a factor: 1545502967 [TF:63:64:mfaktc 0.21 75bit_mul32_gs]
M110393069 has a factor: 11480879177 [TF:63:64:mfaktc 0.21 75bit_mul32_gs]
found 3 prime factors for M110393069 from 2^63 to 2^64 [mfaktc 0.21 75bit_mul32_gs][/code]
Out of necessity, the server does break down any composite factors submitted, but it would be better if this could be done at the client level (without removing the server-level checks of course).
[/QUOTE]

I have some knowledge here (I found one of the factors of 110393069).

It's really easy to detect if a factor is composite because all factors are of the form (2*k*p+1) so if the factor is composite it must be of the form (2*k_1*p+1)*(2*k_2*p+1) which restricts k_1 and k_2 to be very small so it's easy to just check if the returned factor is divisible by (2*i*p+1) for i <= 1000. I asked about adding this to mfaktc but mfaktc doesn't have good client side big int support so I never coded it up.

I think this was asked about in [url]https://www.mersenneforum.org/showpost.php?p=267892&postcount=1148[/url]

Silly question: what's the difference between a block and a grid?

I've seen these terms used interchangeably, but my understanding is that they are different things.

[QUOTE=kriesel;544965](bold emphasis above is mine)
Is the issue of multiple factors in one class closely spaced causing some to be missed still present in mfaktc v0.21?[/QUOTE]

Yes, using atomics on CC 2.0 devices or newer. Current artificial limit is 10 factors within class in a single "stage".

Oliver

[QUOTE=TheJudger;545754]Yes, using atomics on CC 2.0 devices or newer. Current artificial limit is 10 factors within class in a single "stage".

Oliver[/QUOTE]Thanks. I think the probability of more than 10 factors for a single exponent/bitlevel/class is very low. I compute the odds of 6 factors per bit level and exponent to be rather small. [url]https://www.mersenneforum.org/showthread.php?p=520982#post520982[/url]