What is the formula for factoring credits?
 

I just learned how easy it is to calculate LL/DC credits using the status chart :geek:

Now that leaves me curious how factoring credits are calculated. Is it just as easy to determine from a similar chart somewhere? :unsure:

The formula is the following and can be infered from the sources of Prime95.

Factoring Credit : Constant * (2^"HowFarFactored"-2^"HowFarItHadAlreadyBeenFactored")/Exponent

Constant for factoring up to 62 5,00000E-17
Constant for factoring up to 63-64 2,17250E-14
Constant for factoring up to 65 and above 1,63100E-14

So for factoring an exponent N from 62 to 68 bits :

(5 E-17 * (2^64 - 2^62) / N) + (2,1725 E-14 * (2^68-2^64) / N)

Jacob

Thanks.

So as I understand it, if I have a Factoring assignment this computes the credits; however, if I have a LL assignment that first determines the exponent needs to be factored more I assume I will get the Factoring credits for this factoring work and then the LL credits once the LL test is done....correct?

As well, I assume what you are talking about here is P-1 factoring. Are credits also awarded for ECM factoring or is that NOT part of the GIMPS initiative?

[QUOTE=S485122;106209]
So for factoring an exponent N from 62 to 68 bits :

(5 E-17 * (2^64 - 2^62) / N) + (2,1725 E-14 * (2^68-2^64) / N)

Jacob[/QUOTE]

Maybe I misunderstand, but as I read your explanation I think the formula should be:

1.63100E-14 * (2^68 - 2^62) / N

I used the constant 1.631E-14 because I am going up to 68 bits, and I am factoring an exponents already factored up to 62 bits.

This gives me a number that matches the credits I actually received lately.

I did mix up the constants :-(

I meant :

2,1725 E-14 * (2^64 - 2^62) / N + 1.631 E-14 * (2^68-2^64) / N = (300566,636 + 4512995,937) / N = 4813562,574 / N

Your formula gives 4738645,735 / N

The difference between your formula and the one I think is the correct one is less than two percent because the first term about 15 times smaller than the second.

You appear to be correct ... the points I got for the last number I factored matches the points your formula came up with.

HOWEVER ... one thing that strikes me as odd is: Since the formula divides by "N", the BIGGER the exponent(N) the FEWER the points that will be awarded (within specified ranges) ?!?! This seems backwards to me :confused:

This is because the bigger the exponent the fewer the potential factors in each interval (63 bits, 64 bits...) Since the factors are of the form 2*k*exponent+1 the number of k to be tried is proportionnal to 2[sup]n[/sup]/(2*exponent). I say proportionnal because some the k values are eliminated before trying, see the [url=http://mersenne.org/math.htm]The Math[/url] page on the GIMPS site. The trial factoring times indeed decrease when the exponent increases.

[quote=petrw1;106763]HOWEVER ... one thing that strikes me as odd is: Since the formula divides by "N", the BIGGER the exponent(N) the FEWER the points that will be awarded (within specified ranges) ?!?! This seems backwards to me :confused:[/quote]Yes, many (maybe most) people think the same thing when they first contemplate a formula for trial factoring credit.

But, for the reason that Jacob gave, it takes about twice as long to TF exponent 18xxxxxx from 2[sup]64[/sup] to 2[sup]65[/sup] as it does to TF exponent 36xxxxxx from 2[sup]64[/sup] to 2[sup]65[/sup], because the lower exponent has twice as many potential [i]2kp+1[/i] factors in that range as the higher exponent has.

Hmmm.....this might clarify something for me.

About a month ago, just for fun, and after learning about the undocumented feature AdvanceFactor, I thought I would try Advancing M1061 from 60 to about 75 BITS. I naively assumed that if I could factor a 40M exponent from 62 to 68 in a day that I could advance M1061 from 60 to 75 bits in a matter of minutes. Well I started it and when it took a few hours to do 1% of 61 BITS I assumed it must be doing a completely different, very intense method of factoring for it to take that long, so I cancelled it.

Now that I, likewise am 1% wiser of the ways of GIMPS was it only that my M1061 experiment doing the same P-1 factoring but with an exponent with SIGNIFICANTLY more factors to test than a 40M range exponent? ... or is it that AND AdvanceFactor uses different a factoring method?

[quote=petrw1;106849]I thought I would try Advancing M1061 from 60 to about 75 BITS. I naively assumed that if I could factor a 40M exponent from 62 to 68 in a day that I could advance M1061 from 60 to 75 bits in a matter of minutes.[/quote]As you now understand, [I]trial-factoring[/I] over that range would take ... a very ... long ... time. (I'm not sure exactly what AdvancedFactor does.)

[quote]Well I started it and when it took a few hours to do 1% of 61 BITS I assumed it must be doing a completely different, very intense method of factoring for it to take that long, so I cancelled it.[/quote]Trial factoring is as "intense" as it gets -- you're trying every possible factor!! No other method is that exhaustive.

Note that TF also tries many non-possible (composite) factors because that's faster than screening out [I]all[/I] composite candidates. Homework question: Why do I say [U]in this context[/U] that composite [I]2kp+1[/I] candidates are not possible factors?

[quote]was it only that my M1061 experiment doing the same P-1 factoring but with an exponent with SIGNIFICANTLY more factors to test than a 40M range exponent?[/quote]I don't know what method AdvancedFactor actually uses. If it were trial-factoring (not P-1), then the answer would be "Yes, M1061 has about 40,000 times as many potential factors in a given fixed range (such as 2[sup]60[/sup] -> 2[sup]61[/sup]) as M4244xxxx has in that range."

[QUOTE=cheesehead;106865]
Note that TF also tries many non-possible (composite) factors because that's faster than screening out [I]all[/I] composite candidates. Homework question: Why do I say [U]in this context[/U] that composite [I]2kp+1[/I] candidates are not possible factors?
[/QUOTE]

Pardon my ignorance but admittedly my interest in prime numbers far exceeds my mathematical theory prowess regarding prime numbers.

In your context is the "k" composite OR the 2kp+1 composite?

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.

For the former, I'll have to think harder.

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.