View Single Post
 2005-08-07, 20:37 #2 akruppa     "Nancy" Aug 2002 Alexandria 25×7×11 Posts We've been thinking about something similar for GMP-ECM, so we can identify numbers suitable for George's DWT stage 1. I think writing numbers in base b, b=2,3,... might work. After all, b^p = 100....00 in base b. Since c is likely going to be small, it will only affect the lowest couple of digits, and the multiplication by k will only affect the highest couple of digits. So for b=2...(highest base you want to check), write N in base b (check Knuth vol.2 about how to do it quickly), see if there are a lot of zeros in the middle, if there are take the low non-zero digits as c, see how often you can divide b out of N-c to get p and take the remainder as k. Alex Edit: in fact, this is something that could go into phi.c. The code to tweak the poly coefficients should be general enough to handle non-unit k and c. Edit2: this will only detect numbers with positive c. For negative c, look for a lot of b-1 digits in the middle. Neither will work if known factors have been divided out of N already. Last fiddled with by akruppa on 2005-08-07 at 21:48