Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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. – Jyrki Lahtonen Dec 16 '11 at 9:54
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. – Richard Dec 16 '11 at 16:41

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.