2024/09/22 by Omer Simhi, Simhi, Omer
Mathematics · Computer Science · #Mathematics and Applications #Matrix Theory and Algorithms #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.2409.14375
Strömbergsson and Venkatesh proved that a system of homogeneous linear congruence modulo prime has a positive probability to have a short non-trivial solution. We extend this result and show that the same holds for square-free moduli. In the case of 2-variables single linear congruence, we show that there is a positive probability to have a short solution for all integer moduli as well as positive probability for having short non-trivial solutions which are primitive in a suitable sense.