scientific article; zbMATH DE number 1985302

MaRDI QIDQ4429166zbMATH OpenFDO

Authors Don Coppersmith, Jon Lee

Publication date 24 September 2003

zbMATH Keywords

facetsfactoringpolytopes

Mathematics Subject Classification ID

Factorization; primality (11A51) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Review text

The authors study indivisibility polytopes, i.e., polytopes of binary \(n\)-strings that encode positive integers that are not divisible by \(p\). First they present a detailed analysis of a class of polytopes called ``clipped cubes. This analysis includes a characterization of their facets, a characterization as the set of solutions of a totally dual integral system of linear inequalities, a characterization of adjacency of extreme points, a description of how to find short edge paths, a polynomial time algorithm for optimizing a linear function over a clipped cube, relationships with fractional generalized covering polyhedra and balanced matrices, the computation of their volume, and alternative models. Indivisibility polytopes comprise dyadic (\(p=2^k\)) and nondyadic cases. The latter are clipped cubes, the former are not. Linear inequality descriptions and characterizations of extreme point adjacency for dyadic and further results on nondyadic indivisibility polytopes are proved. An application of indivisibility polytopes in factoring large integers is outlined. Finally, properties of facet defining inequalities of divisibility polytopes, i.e., polytopes of binary \(n\)-strings that encode positive integers that are divisible by \(p\) are investigated. For the entire collection see [Zbl 1013.00014].

Recommendations

• Cropped cubes
• Polytopes of partitions of numbers
• Some efficiently solvable problems over integer partition polytopes
• Decomposition of polytopes and polynomials
• Integral polytopes and polynomial factorization

Cited in

(10)

• Indivisible plexes in Latin squares
• Cropped cubes
• Idealness and 2-resistant sets
• Volume computation for sparse Boolean quadric relaxations
• Bounded remainder polyhedra
• The Role of Indivisibles in Mengoli’s Quadratures
• Indivisibles and Latitude of Forms
• scientific article; zbMATH DE number 1810571 (Why is no real title available?)
• Solving multiplicative programs by binary-encoding the multiplication operation
• Embedding divisor and semi-prime testability in f-vectors of polytopes

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4429166)