What is the formula for factoring credits?

[petrw1]

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

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

[S485122]

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

[petrw1]

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?

[petrw1]

Originally Posted by S485122

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

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.

[S485122]

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.

[petrw1]

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

[S485122]

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ⁿ/(2*exponent). I say proportionnal because some the k values are eliminated before trying, see the The Math page on the GIMPS site. The trial factoring times indeed decrease when the exponent increases.

[cheesehead]

Originally Posted by petrw1

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

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⁶⁴ to 2⁶⁵ as it does to TF exponent 36xxxxxx from 2⁶⁴ to 2⁶⁵, because the lower exponent has twice as many potential 2kp+1 factors in that range as the higher exponent has.

[petrw1]

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?

[cheesehead]

Originally Posted by petrw1

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.

As you now understand, trial-factoring over that range would take ... a very ... long ... time. (I'm not sure exactly what AdvancedFactor does.)

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.

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 all composite candidates. Homework question: Why do I say in this context that composite 2kp+1 candidates are not possible factors?

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?

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⁶⁰ -> 2⁶¹) as M4244xxxx has in that range."

[petrw1]

Originally Posted by cheesehead

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

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.