[Ecm-dev] Proposal from George. Literally.
Paul Zimmermann
Paul.Zimmermann at loria.fr
Lun 9 Mai 14:49:47 CEST 2005
Dear Jakub,
>> Recognizing such a form is easy if k=1 and b is not too large,
>> but for general k I have to think about it.
>
> As long as the user passes the number as an expression of this form
> (k*b^n+c), the expression parser could return the relevant parameters to
> the callee. We'd probably have to keep some flags in the save file
> entries so the DWT works when resuming. None of this would be hard to do.
I hope it helps...
I think that finding k*b^n+c form is relatively easy for small b. I
include short C++ and GMP program performing that task. The main idea is
as follows.
For given N we want N to divide k*b^n+c.
Let b and n be fixed. Let B = b ^ n mod N.
We search for small k, t, c such that
N * t = k * B + c.
We can rewrite this equality as
N/B - k/t = c / (B * t).
Assuming B = O(N), k = t = c = O(1) we have
N/B - k/t = O(1/N).
That means we have to find very good approximation of N/B by rational
k/t. This could be done using continued fraction method.
Jakub Pawlewicz
Unfortunately this is not so easy. Even for k=1 we can have t as large as N.
Indeed, the multiplication of "big residues" (modulo k*b^n+c) will cost
M(t*N), which has to be compared to M(N)+D(N) for classical arithmetic,
not taking into account the special form. Assuming D(N)=M(N), i.e. the
division is as fast as the multiplication, and M(N)=log(N)^2, the special
form will be faster for t*N <= N^sqrt(2).
Also, assuming b and n fixed is not reasonable with the "k" extension.
For base-2 Cunningham numbers (where k=1) you already have to check
several thousands values of n. I'm sure there is a faster way, still
using continued fractions.
Paul
Plus d'informations sur la liste de diffusion Ecm-discuss