[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