1
$\begingroup$

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.

  • 0
    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.2011-12-16

0 Answers 0