Integer programming and cryptography (Q799477)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Integer programming and cryptography |
scientific article; zbMATH DE number 3874958
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Integer programming and cryptography |
scientific article; zbMATH DE number 3874958 |
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
