Factoring from nonconsecutive known bits

Definitions and mathematical statement

Let $N$ be a positive composite integer with an intended nontrivial factorization $N=ab$, $a,b>1$. Write \[ a=\sum_{i\ge0}a_i2^i,\qquad b=\sum_{j\ge0}b_j2^j,\qquad a_i,b_j\in\{0,1\}. \] Nonconsecutive known bits can be encoded by finite position sets $I,J\subseteq{\mathbb{N}}_0$ and supplied values $(a_i)_{i\in I}$, $(b_j)_{j\in J}$, with gaps allowed between positions. This notation is a two-factor input model, not a source-imposed restriction to semiprimes or balanced prime factors.

The task is to develop methods using such scattered partial information to factor $N$, or recover the intended factors when that is required. The source does not prescribe how many bits are known, their distribution, whether bits of one or both factors are given, or whether factor lengths are known. It does not restrict the factors to primes, fix a balanced-size promise, or specify treatment of multiple consistent factorizations.

A precise algorithmic target must state those input promises, whether positions are adversarial or random, the desired success guarantee, and a running-time bound in terms of input size. No efficient algorithm for every arbitrary bit pattern is demanded without sufficient leakage assumptions: the record gives no universal threshold or complexity theorem. The central request is to handle nonconsecutive information rather than silently replacing it with a known contiguous block.

Short English statement

Use scattered known binary digits of unknown factors to factor an integer. The amount and placement of information and the factor-size assumptions must be specified for a quantitative algorithm.

The supplied summary reports substantial practical understanding of random scattered-bit recovery but distinguishes arbitrary prescribed patterns and Coppersmith-style methods as unresolved in full generality. Its practical threshold language is not an unconditional worst-case guarantee. The partial-progress label and 2006 workshop problem are retained with current primary-literature review required.

Sources

• Local UnsolvedMath registry, permanent ID 8800020, source code catalogue entry, "Factoring from nonconsecutive known bits," proposed by Alexander May. Dataset curation and metadata: Ulam AI and UnsolvedMath Contributors, CC BY 4.0.
• IPAM, Workshop on Number Theory and Cryptography --- Open Problems (2006), Attachment 6222, PDF page 12, printed slide 8, schedule locator https://www.ipam.ucla.edu/programs/workshops/workshop-i-number-theory-and-cryptography-open-problems/?tab=schedule; pdf-and-legacy-ppt visual-audit extraction, accessed 2026-07-29.
• The supplied summary names Coppersmith-style methods and random-bit recovery without precise primary references, theorem hypotheses, or threshold values.
• Source provenance reports inspection of 17 PDFs and two legacy PPT decks among 19 surviving attachments, excluding repetitions and solved definitions; this is supplied provenance, not a new inspection claimed here.
• Current primary-literature status audit and redistribution terms NEEDS_REVIEW for the publicly accessible author/publisher copy, separately from the dataset licence.