Lattice points are points in any prescribed space all of whose components are integers. Often the underlying space is ordinary n-dimensional Euclidean space Eⁿ, where a lattice point becomes simply an n-tuple of integers. Hermann Minkowski pointed out nearly 100 years ago that deep and important arithmetical results can be made almost intuitively obvious by simple geometrical considerations of figures in Eⁿ. This approach had numerous applications to pure mathematics (for example, a startlingly simple theory of units in algebraic number fields) and to applied mathematics (for example, a rich theory of the best approximation of irrational numbers by rational numbers). In more recent times, the problem of integer programming is the problem of determining whether a prescribed convex polyhedron contains a lattice point. In general, this problem is NP-complete. Just as the general linear programming problem is in P, however, so the integer programming problem in any fixed dimension is in P.

The principal result of this paper is to show the existence of a polynomial-time algorithm for the solution of the general lattice point counting problem for polyhedra in E³ and E⁴, with conjectural excursions to E⁵. The method of proof hinges on the reduction to counting a particular type of simplex. The paper is well written and carefully documented. I am convinced that no polynomial-time algorithm exists for counting B₄(n), as mentioned by the author; that is, the RSA cryptosystem is probably safe from this particular avenue of proposed penetration.