[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