Given $a,b,c,d\in\mathbb Z$ with $ad+bc=p$ a prime there is an $m\in\mathbb Z$ with $-\lceil1+\sqrt{p}\rceil< r_1,r_2<\lceil1+\sqrt{p}\rceil$ and $$r_1\equiv mac\bmod p$$ $$r_2\equiv mbd\bmod p$$ where $r_1,r_2$ are interpreted as in $[-\frac p2,\frac p2]$ by Dirichlet's pigeonhole principle.

  1. Is there any closed form for such an $m$ and hence $r_1$ and $r_2$ as well?

  2. Can we canonize an expression that provides an unique $m$ that works for a given $a,b,c,d$ at least under unimodular condition of $ad-bc=1$ (there may be multiple $m$'s however I am asking if we can isolate an expression that works always providing an unique $m$)?

  3. Say if 1. and 2. fails then at least is there a $\mathsf{polylog}(|a|+|b|+|c|+|d|)$ time algorithm to find such an $m$ that does not involve linear integer programming (with linear integer programming there is Lenstra's method which is not very practical)?

  • $\begingroup$ Doesn't e.g. $|r_1|\lt\lceil1+\sqrt{p}\rceil$ immediately subsume $r_1\in [-p/2, p/2]$? $\endgroup$ – Steven Stadnicki Oct 6 at 18:49
  • 1
    $\begingroup$ The range is to stress that the modulus is not defined from $0$ to $p-1$. $\endgroup$ – 1.. Oct 6 at 19:36

For 3. one might use the $LLL$ algorithm to find the shortest vector to the row space of the equations $$\begin{bmatrix}bd&-ac&-p\\1&0&0\\0&1&0\end{bmatrix}\begin{bmatrix}r_1\\r_2\\k\end{bmatrix}=\begin{bmatrix}0\\r_1\\r_2\end{bmatrix}.$$

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.