View Single Post
Old 2005-08-07, 20:37   #2
akruppa's Avatar
Aug 2002

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.


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
akruppa is offline   Reply With Quote