Integer programming and cryptography (Q799477)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Integer programming and cryptography |
scientific article |
Statements
Integer programming and cryptography (English)
0 references
1984
0 references
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)].
0 references
cryptography
0 references
polynomial-time algorithm
0 references
integer linear programming problem
0 references
triangle in the plane
0 references
integer coordinates
0 references
