Analytically controlling sizes in modular arithmetic to demonstrate Dirichlet pigeonhole application

MathOverflow Asked on December 27, 2020

Given $a,b,c,dinmathbb Z$ with $ad+bc=p$ a prime there is an $minmathbb Z$ with $-lceil1+sqrt{p}rceil<
$$r_1equiv macbmod p$$
$$r_2equiv mbdbmod 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)?

One Answer

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&0end{bmatrix}begin{bmatrix}r_1\r_2\kend{bmatrix}=begin{bmatrix}0\r_1\r_2end{bmatrix}.$$

Correct answer by 1.. on December 27, 2020

Add your own answers!

Ask a Question

Get help from others!

© 2024 All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP