[Ecm-dev] Proposal from George. Literally.

Jakub Pawlewicz pan at mimuw.edu.pl
Sam 7 Mai 02:08:05 CEST 2005


>> 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
-------------- section suivante --------------
Une pi?ce jointe non texte a été nettoyée...
Nom: kbnc_detect.cpp
Type: text/x-c++src
Taille: 1231 octets
Desc: non disponible
Url: http://lists.gforge.inria.fr/pipermail/ecm-discuss/attachments/20050507/f67f73ce/attachment.cpp 


Plus d'informations sur la liste de diffusion Ecm-discuss