Let's say $p=16301$. How do I best find sets of small values for $a$, $b$ and $c$ for an equation like

$$a p^3+b p^2+c p=11263 \mod\ 2^{16}.$$

I can use the lindep command in PARI/GP which uses PSLQ to find solutions for

$$a p^3+b p^2+c p+d 11263+e 2^{16}=0,$$

but this doesn't work very well because I want to force the coefficient $d$ to be $-1$ and I don't care about how big $e$ gets. The PARI/GP command qflll takes a matrix so there's probably more knobs to tweak and it performs similar magic but I don't know how to structure the problem to give the results I want. For example $a=6$, $b=5$ and $c=4$ is the answer I'm looking for.

For the real application of this maths, the problem would be larger in every way so a simple search is not suitable.

  • $\begingroup$ If there is method for finding small solutions for integer (not modular) equations, then how far will you get by reducing the powers $p^j$ modulo $2^{16}$, say to an interval $(-2^{15},2^{15}]$, and then "guessing" the value of $e$. After reducing the powers of $p$, if $a,b,c$ are small, then $e$ has to be small as well... This approach may not scale well, when you increase the number of terms, though. $\endgroup$ – Jyrki Lahtonen Dec 16 '11 at 9:54
  • $\begingroup$ Yes, this is what I do and I get useful results for about 17 terms with numbers around 2^128. Every solution for which d is not +1 or -1 has to be thrown away though and this is what kills the efficiency. $\endgroup$ – Richard Dec 16 '11 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.