We've been thinking about something similar for GMPECM, 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 nonzero digits as c, see how often you can divide b out of Nc 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 nonunit k and c.
Edit2: this will only detect numbers with positive c. For negative c, look for a lot of b1 digits in the middle. Neither will work if known factors have been divided out of N already.
Last fiddled with by akruppa on 20050807 at 21:48
