mersenneforum.org What is the formula for factoring credits?
 Register FAQ Search Today's Posts Mark Forums Read

 2007-05-15, 17:03 #1 petrw1 1976 Toyota Corona years forever!     "Wayne" Nov 2006 Saskatchewan, Canada 519610 Posts What is the formula for factoring credits? 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?
 2007-05-16, 05:25 #2 S485122     "Jacob" Sep 2006 Brussels, Belgium 1,823 Posts 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
 2007-05-16, 18:27 #3 petrw1 1976 Toyota Corona years forever!     "Wayne" Nov 2006 Saskatchewan, Canada 519610 Posts 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?
2007-05-16, 19:17   #4
petrw1
1976 Toyota Corona years forever!

"Wayne"
Nov 2006

22·3·433 Posts

Quote:
 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.

 2007-05-17, 12:24 #5 S485122     "Jacob" Sep 2006 Brussels, Belgium 1,823 Posts 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. Last fiddled with by S485122 on 2007-05-17 at 12:35
 2007-05-22, 21:52 #6 petrw1 1976 Toyota Corona years forever!     "Wayne" Nov 2006 Saskatchewan, Canada 22·3·433 Posts 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
 2007-05-23, 05:41 #7 S485122     "Jacob" Sep 2006 Brussels, Belgium 1,823 Posts 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 2n/(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. Last fiddled with by S485122 on 2007-05-23 at 05:42
2007-05-23, 18:30   #8

"Richard B. Woods"
Aug 2002
Wisconsin USA

1E0C16 Posts

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

Last fiddled with by cheesehead on 2007-05-23 at 18:36

 2007-05-23, 19:50 #9 petrw1 1976 Toyota Corona years forever!     "Wayne" Nov 2006 Saskatchewan, Canada 22×3×433 Posts 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?
2007-05-23, 23:29   #10

"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts

Quote:
 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.)

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.
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?

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?
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 260 -> 261) as M4244xxxx has in that range."

2007-05-28, 18:02   #11
petrw1
1976 Toyota Corona years forever!

"Wayne"
Nov 2006

22×3×433 Posts

Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post afjewkes PrimeNet 2 2016-07-15 06:26 pegaso56 Information & Answers 2 2009-12-15 02:55 ET_ PrimeNet 12 2008-11-03 22:11 Graff PrimeNet 2 2008-07-25 15:21 Carlo Monari PrimeNet 2 2004-07-18 14:14

All times are UTC. The time now is 11:24.

Thu Jun 30 11:24:40 UTC 2022 up 77 days, 9:25, 0 users, load averages: 1.63, 1.51, 1.39