We're all ignorant about something. Most things, even.

[quote=petrw1;107198]In your context is the "k" composite OR the 2kp+1 composite?[/quote]The latter.

[quote]For the latter, all non-prime numbers can be factored into 2 or more prime factors. SO, if we find a composite factor then by definition it can be further factored into primes.[/quote]Correct. You're on the right track.

In general, _if_ we are given a composite 2kp+1 that _is_ a factor of a Mersenne number, then what can be deduced/predicted about the factors of that 2kp+1 number?

[QUOTE=cheesehead;107200]In general, _if_ we are given a composite 2kp+1 that _is_ a factor of a Mersenne number, then what can be deduced/predicted about the factors of that 2kp+1 number?[/QUOTE]

All factors of a Mersenne Prime must be of the format 2kp+1 so if we have a 2kp+1 factor that is composite it must be the product of 2 or more smaller 2kp+1 factors ... but being smaller they should have already been found.

For example 2^29-1 = 536870911 has 2kp+1 factors of:
233 * 2304167
1103 * 486737
2089 * 256999
The first of each pair are prime.

However, 2304167, 486737 and 256999 are composite (and the product of smaller 2kp+1 factors):
2304167 = 1103 * 2089
486737 = 233 *2089
256999 = 233 * 1103

but still of the form 2kp+1
2304167 has a k of 39727
486737 has a k of 8392
256999 has a k of 4431

Exactly.

So then it should never get to the composite 2kp+1 factors; does it not stop as soon as it finds a factor? ... or does it complete the assignment (i.e. up to 68 bits) and report all factors found?

[quote=petrw1;107344]So then it should never get to the composite 2kp+1 factors; does it not stop as soon as it finds a factor?[/quote]Yes to the latter (but see the [sup]*[/sup] note below).

As to the former; Prime95's trial factoring _does_ sieve out many composite candidate factors without actually trying them.

Remember, the reason we want Prime95 TF to skip testing composite candidates is not that it's proceeded past the point of having found a factor; it's that:

_if_ the composite candidate were a factor, Prime95 would already have found a smaller factor earlier,

but Prime95 didn't find a smaller factor earlier,

and we're assuming we don't ever fool Prime95 by falsely telling it that a smaller bit level has already been tested,

so we know for sure that the composite candidate cannot be a factor either, so we'd prefer Prime95 not to even test it.

However, there's a cost associated with both sieving out a composite candidate and testing a candidate for factorhood. As more and more composites are sieved-out, the cost of sieving the remaining ones rises. At some point, the cost of further sieving exceeds the cost of performing the (hopeless) trial divisions by composites, so Prime95 proceeds with the latter.

[quote] ... or does it complete the assignment (i.e. up to 68 bits) and report all factors found?[/quote]Once Prime95's TF finds a factor, it stops[sup]*[/sup].

([sup]*[/sup]However, in some circumstances Prime95 proceeds to check for another, slightly smaller factor.

Why?

For reasons of computational efficiency the candidates are tested in groups by equivalence class, not in strictly increasing order within a bit level. It used to be that whenever Prime95 found a factor, it would check whether there might be a smaller factor in a different equivalence class within the same bit level, because it would be of some mathematical value to be certain that it reported the smallest factor.

However, as TF testing got to higher and higher bit levels, the time required for this additional testing for certainty of finding the smallest factor grew and grew. George decided to change the Prime95 default so that it did not perform this added look for slightly-smaller factor. It's still available as a keyword option.

One downside to this change is that when one says that Prime95 TF searches for candidates in strictly increasing order, as I have done earlier, it's a [I]bit[/I] of a lie. The candidate are tested in strictly increasing order _of bit level_, and in strictly increasing order _within each congruence class within a bit level_, but not in strictly increasing order overall while in the midst of a bit level. So -- I've lied to you, in this particular regard, and I'll probably do it again, for sake of simplicity of discussion because it usually makes no practical difference. Mea culpa.

But this added searching-back-through-the-same-bit-level does not make any difference regarding composite factors! Any factor of a composite factor could not be in the same bit level!)

[QUOTE=cheesehead;107413]For reasons of computational efficiency the candidates are tested in groups by equivalence class[/QUOTE]

I'm almost afraid to ask for a definition of "equivalence class" as I suspect it will get too deep into mathematical theory for me to comprehend...

[quote=petrw1;107415]I'm almost afraid to ask for a definition of "equivalence class" as I suspect it will get too deep into mathematical theory for me to comprehend...[/quote]I should have written "congruence class" instead of "equivalence class". It has to do with modular arithmetic.

See [URL]http://math.usask.ca/encryption/lessons/lesson05/page2.html[/URL]

A congruence class is the set of integers which have the same remainder when divided by a given number (which is called the [I]modulus[/I]). E.g., 221, 641, and 851 are in the same congruence class modulo 30. When divided by 30, 221 has a remainder of 11, and so does 641 and 851. 11, 221, 641, and 851 are [I]congruent[/I] to each other, modulo 30. 851, 641, 221, and 11 are all of the form 30k+11 for some integer k.

When trying to screen out composite numbers, congruence classes are useful for avoiding all numbers divisible by certain small primes.

Example: 30 = 2 * 3 * 5. All numbers congruent to 12 modulo 30 are divisible by both 2 and 3 (they're all of the form 30k+12). All numbers congruent to 15 modulo 30 are of the form 30k+15 and are divisible by both 3 and 5.

So, if you are screening out composites, you automatically exclude all numbers divisible by either 2, 3, or 5 if you look only at numbers that are not congruent, in modulo 30, to a multiple of 2, 3, or 5. The congruence classes 1 mod 30, 7 mod 30, 11 mod 30, 13 mod 30, 17 mod 30, 19 mod 30, 23 mod 30, and 29 mod 30 all have that property. Out of the thirty congruence classes mod 30, 22 are guaranteed to have only composite numbers, so you need look only at the other 8 (corresponding to the remainders 1, 7, 11, 13, 17, 19, 23, and 29 when divided by 30).

You may notice that in that list, the remainders besides 1 are all prime. That's not necessarily true of other modula. In modulo 210 (= 2 * 3 * 5 * 7), the congruence classes that are not multiples of 2, 3, 5, or 7 include 1 mod 210, ... [B]121[/B] mod 210, ... [B]209[/B] mod 210. Both the remainders 121 and 209 are composite, but both are divisible [I]only[/I] by factors outside the set {2, 3, 5, 7}. There are also other congruence classes mod 210 besides 121 and 209 whose characteristic remainders are composite but not divisible by any member of the set {2, 3, 5, 7}.

In sieving, it's all right to consider congruence class 121 mod 210 because although 210k+121 is divisible by 11 when k = 0, it's not composite for all k. For k = 1, 210*1+121 = 331. If one wanted to skip all multiples of 11, one could use modulo 2310 = 2 * 3 * 5 * 7 * 11, and consider only those congruence classes corresponding to remainders not divisible by {2, 3, 5, 7, 11}. Here, congruence class 121 mod 2310 would be skipped because all 2310k+121 are multiples of 11, but class 221 would be examined because [I]not[/I] all 2310k+221 are guaranteed to be composite even though 221 = 13 * 17.

It appears bonus points are awarded when a factor is found ... :question:

I just completed 42744671 (F68) and expected 0.115 points.

However, it found a factor at 67 bits and I was awarded 0.135 points. :surprised even though I would have spent only about half the time it should have taken to factor to 68 bits. :w00t:

[QUOTE=petrw1;109034]It appears bonus points are awarded when a factor is found ... :question:

I just completed 42744671 (F68) and expected 0.115 points.

However, it found a factor at 67 bits and I was awarded 0.135 points. :surprised even though I would have spent only about half the time it should have taken to factor to 68 bits. :w00t:[/QUOTE]

A factor earns you 2.32 (or was it 2.032?) times the credit as what you would've received if you'd just factored to the bit level where the factor was found.

[QUOTE=axn1;109042]A factor earns you 2.32 (or was it 2.032?) times the credit as what you would've received if you'd just factored to the bit level where the factor was found.[/QUOTE]

According to the formula I was given earlier in this forum by S485122 I calculate that factoring to 67 bits without finding a factor should have given me about 0.0563 credits (no guarantees I implemented the formula exactly correct). For finding a factor at 67 bits I got 0.13326 credits ... 2.355 times more.