zbMATH — the first resource for mathematics

Reconstructing truncated integer variables satisfying linear congruences. (English) Zbl 0654.10006
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.

11Y16 Number-theoretic algorithms; complexity
11A07 Congruences; primitive roots; residue systems
68Q25 Analysis of algorithms and problem complexity
94A60 Cryptography
Full Text: DOI