Frieze, Alan M.; Håstad, Johan; Kannan, Ravi; Lagarias, Jeffrey C.; Shamir, Adi Reconstructing truncated integer variables satisfying linear congruences. (English) Zbl 0654.10006 SIAM J. Comput. 17, No. 2, 262-280 (1988). The authors develop an algorithm for computing small integer solutions of systems of linear congruences if existing. They make use of the lattice basis reduction algorithm of A. K. Lenstra, H. W. Lenstra jun. and L. Lovasz [Math. Ann. 261, 515–534 (1982; Zbl 0488.12001)] to prove that the algorithm is polynomial time. The algorithm is used for the reconstruction of variables if part of their bit pattern is known thus yielding applications in cryptography. Reviewer: Michael Pohst (Berlin) Cited in 2 ReviewsCited in 28 Documents MSC: 11Y16 Number-theoretic algorithms; complexity 11A07 Congruences; primitive roots; residue systems 68Q25 Analysis of algorithms and problem complexity 94A60 Cryptography Keywords:computational number theory; prediction of linear congruential generators whose outputs are truncated; breaking of simplest version of Blum’s protocol for exchanging secrets; algorithm; small integer solutions; systems of linear congruences; lattice basis reduction algorithm; polynomial time; reconstruction of variables; applications in cryptography Citations:Zbl 0488.12001 PDFBibTeX XMLCite \textit{A. M. Frieze} et al., SIAM J. Comput. 17, No. 2, 262--280 (1988; Zbl 0654.10006) Full Text: DOI