mersenneforum.org P-1 bounds calculation for Wagstaff numbers
 Register FAQ Search Today's Posts Mark Forums Read

2011-05-13, 11:24   #1
axn

Jun 2003

144616 Posts
P-1 bounds calculation for Wagstaff numbers

I would've thought that the bounds calculation for P-1 would be same for same-sized Mersennes and Wagstaff numbers considering that they have the same properties for their potential factors (i.e. 2kp+1). But, alas no!
Quote:
 Originally Posted by ecm.c if (k == 1.0 && b == 2 && c == -1) kk = kk / 2.0 / n;
Only mersennes get the adjustment. This should be extended to Wagstaffs also.

Thoughts?

 2011-05-14, 18:23 #2 chris2be8     Sep 2009 42268 Posts It sounds a good idea. Are there any other classes of number with potentially useful properties for their factors? Chris K
2011-05-14, 21:20   #3
diep

Sep 2006
The Netherlands

11·71 Posts

Quote:
 Originally Posted by axn I would've thought that the bounds calculation for P-1 would be same for same-sized Mersennes and Wagstaff numbers considering that they have the same properties for their potential factors (i.e. 2kp+1). But, alas no! Only mersennes get the adjustment. This should be extended to Wagstaffs also. Thoughts?
Would be great if adjustment happens as well for Wagstaff!

2011-05-14, 21:26   #4

"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts

Quote:
 Originally Posted by axn I would've thought that the bounds calculation for P-1 would be same for same-sized Mersennes and Wagstaff numbers considering that they have the same properties for their potential factors (i.e. 2kp+1). But, alas no! Only mersennes get the adjustment. This should be extended to Wagstaffs also. Thoughts?
In each case, check whether the P-1 (or whatever) software actually takes useful account of those properties of potential factors!

For instance, with Mersennes the P-1 routine automatically throws the Mersenne exponent (p, or "n" in the quoted ecm.c code) into the computation wherever appropriate, regardless of B1/B2.

If the same were not done for Wagstaffs (or chris2be8's "any other classes of number"), it would be inappropriate to adjust the bounds calculation as if it were.

Last fiddled with by cheesehead on 2011-05-14 at 21:30

 2011-05-15, 02:16 #5 Prime95 P90 years forever!     Aug 2002 Yeehaw, FL 3×13×197 Posts If someone posts the list of numbers that have the "2kp+1" property I'd be happy to add it to prime95.
2011-05-15, 06:09   #6
axn

Jun 2003

2·3·5·173 Posts

Quote:
 Originally Posted by Prime95 If someone posts the list of numbers that have the "2kp+1" property I'd be happy to add it to prime95.
IIUC, b^n+/-1 ==> k=1, |c|=1 should cover all of them. I'd really appreciate it if someone could confirm this.

Quote:
 Originally Posted by cheesehead In each case, check whether the P-1 (or whatever) software actually takes useful account of those properties of potential factors! For instance, with Mersennes the P-1 routine automatically throws the Mersenne exponent (p, or "n" in the quoted ecm.c code) into the computation wherever appropriate, regardless of B1/B2. If the same were not done for Wagstaffs (or chris2be8's "any other classes of number"), it would be inappropriate to adjust the bounds calculation as if it were.
Good point. A quick test using P95 indicates that this is the case for Wagstaff. I will check the code to see if I can confirm. At any rate, if it is not the case, it doesn't really hurt to throw in the exponent there just for the heck of it _regardless_ of the form of the number

 2011-05-15, 07:01 #7 axn     Jun 2003 144616 Posts From ecm.c Code: /* For Mersenne numbers, 2^n-1, make sure we include 2n in the calculated */ /* exponent (since factors are of the form 2kn+1). For Fermat numbers, */ /* 2^n+1 (n is a power of 2), make sure the exponent is included in the */ /* calculated exponent as factors are of the form kn+1. Otherwise, do */ /* nothing special -- start with one. */ if (lower == 0 && k == 1.0 && b == 2 && c == -1) itog (2*n, g); else if (lower == 0 && k == 1.0 && b == 2 && c == 1) itog (n, g); else setone (g); So, it appears that Wagstaff numbers benefit from the Fermat logic. But, it is probably simpler to get rid of the condition and always use 2*n.
2011-05-15, 21:25   #8
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

3·13·197 Posts

Quote:
 Originally Posted by axn So, it appears that Wagstaff numbers benefit from the Fermat logic. But, it is probably simpler to get rid of the condition and always use 2*n.
But does it use this info in calculating the optimal P-1 bounds?

2011-05-16, 03:30   #9
axn

Jun 2003

2·3·5·173 Posts

Quote:
 Originally Posted by Prime95 But does it use this info in calculating the optimal P-1 bounds?
Nope. The relevant piece of code is posted in the OP. Only the mersennes get this (not even Fermats).

2011-12-13, 10:26   #10
axn

Jun 2003

144616 Posts

*BUMP*

I have made some modifications to ecm.c. If you can verify and incorporate it into next release of P95, that'll be great.

Changes include:
1. Changing the check criteria for the 2*p extra factor to k=1, abs(c)=1. [Updated both the probability calculation, as well as where the factor is introduced during P-1 exponentiation.]
2. Introduced a base conversion factor to calculate the total number of squarings during an LL (prp) test for bases other than 2. This will fix up the cost calculation for P-1.

Note:- I have not made any changes to any comments. I haven't compiled, let alone tested, any of these changes.
Attached Files
 ecm.txt (187.9 KB, 830 views)

 2018-07-24, 06:27 #11 GP2     Sep 2003 5×11×47 Posts I took a look at the source code for version 29.4 b7 and it seems the original code mentioned in the first post in this thread is still there (in guess_pminus1_bounds and guess_pminus1_probability). Was there ever any consensus reached about whether it should be changed? Empirically, Wagstaff factors do seem to follow the same 2kp + 1 pattern.

 Similar Threads Thread Thread Starter Forum Replies Last Post AntonVrba Math 96 2009-02-25 10:37 fivemack Factoring 4 2008-02-24 00:39 devarajkandadai Math 1 2007-03-19 04:53 jchein1 Math 7 2006-11-26 13:29 axn Software 2 2006-03-04 16:49

All times are UTC. The time now is 18:53.

Fri Dec 3 18:53:16 UTC 2021 up 133 days, 13:22, 0 users, load averages: 0.95, 0.92, 1.00