Reducing guesses in factoring with known bits

Definitions and mathematical statement

In a standard partially known factor setting, the input contains an integer $N=pq$ and specified binary digits of one or both factors. For example, \[ p=\sum_i p_i2^i,\qquad q=\sum_j q_j2^j,\qquad p_i,q_j\in\{0,1\}, \] with some indexed digits fixed and others unknown. The source does not specify whether both factors are prime, balanced, or subject to particular bit patterns; this notation describes possible input data without imposing those restrictions.

A lattice attack may enumerate candidate values of selected unknown digits before applying a lattice/small-root step to the remaining unknowns. Guessing $b$ binary digits by exhaustive enumeration gives $2^b$ candidates, so reducing the number of guessed bits and reducing the total number of guesses are related but different quantitative descriptions.

The problem asks to reduce the guesses required by such lattice attacks. It does not name a baseline attack, known-bit positions or quantity, factor-size regime, lattice dimension, running-time allowance, success guarantee, or target bound. Contiguous leading bits, trailing bits, arbitrary scattered bits, and information from both factors are different instances. Reducing enumeration by increasing another cost also requires an explicit comparison criterion. Thus this is an improvement programme for a source-specific attack family, not a theorem that arbitrary partially known factors can be recovered in a stated time.

Short English statement

Reduce the guessing overhead in lattice-based factoring when some factor bits are known. A precise result must fix the bit pattern, baseline attack and permitted computational tradeoffs.

Sources

• Local UnsolvedMath registry, permanent ID 8800021, exact source code catalogue entry, "Reducing guesses in factoring with known bits"; attributed to Alexander May, no proposed year supplied. Registry status open, classification OPEN-TRIAGE.
• IPAM Workshop on Number Theory and Cryptography---Open Problems (2006), attachment 6222, PDF page 13, printed slide 9, https://www.ipam.ucla.edu/programs/workshops/workshop-i-number-theory-and-cryptography-open-problems/?tab=schedule. Supplied pdf-and-legacy-ppt visual audit accessed July 29, 2026. Provenance records 17 PDFs and two legacy PPT decks inspected with repeated builds/solved definitions excluded; no PDF/PPT was accessed here.
• The supplied summary reports case-specific guess reductions, including settings with partially unknown bits of both factors, but no verified general resolution of the slide programme. It gives no exact algorithm, parameter bounds or references.
• Provenance flags current primary-literature status and redistribution terms NEEDS_REVIEW.