Integer programming and cryptography
type: Item
instance of: scholarly article
title: Integer programming and cryptography
zbMATH Open document ID: 0548.90050
DOI: 10.1007/BF03024123
published in: The Mathematical Intelligencer
publication date: 1984-01-01T00:00:00Z
review text: Several years ago it was shown that there exists a polynomial-time algorithm for the integer linear programming problem with a fixed number of variables [see the author, Math. Oper. Res. 8, 538-548 (1983; Zbl 0524.90067)]. The present paper explains the basic idea behind this algorithm by considering the problem how to decide whether a given triangle in the plane contains a point with integer coordinates. In addition, the paper describes how A. Shamir applied the integer programming algorithm in order to break the cryptographic system proposed by R. C. Merkle and M. E. Hellman [see \textit{A. Shamir}, Proc. 23rd IEEE Symp. Found. Computer Sci., 145-152 (1982)].
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 68P25
Mathematics Subject Classification ID: 90C90
Mathematics Subject Classification ID: 94B99
zbMATH DE Number: 3874958
zbMATH Keywords: cryptography
zbMATH Keywords: polynomial-time algorithm
zbMATH Keywords: integer linear programming problem
zbMATH Keywords: triangle in the plane
zbMATH Keywords: integer coordinates
author: H. W. jun. Lenstra
MaRDI profile type: Publication
cites work: Cryptology: The mathematics of secure communication
cites work: A new linear programming algorithm - better or worse than the simplex method?
cites work: Q4198056
cites work: Integer Programming with a Fixed Number of Variables
cites work: Factoring polynomials with rational coefficients
cites work: Hiding information and signatures in trapdoor knapsacks
description: scientific article; zbMATH DE number 3874958