Context: I am wondering if we can adapt Knuth's Master mind algorithm with suitable modifications for efficient integer factoring.
Background: In [Knuth76], Donald Knuth provides an algorithm for solving the standard Master Mind game in 5 moves or less. See linked paper for details.
Consider this generalization of the Master Mind game.
Let $n$ be an arbitrary-sized integer that is not a square and an odd composite number. Let $p_1, p_2, p_3, \cdots p_k$ be primes such that $\prod_i p_i > n$ and $\gcd(p_i, n) = 1$. The digits of the codeword represent the residues of a factor of $n$ i.e., if $n = ab$, then the $k$-th codeword digit is the residue $a \bmod p_i$ that is further bijectively mapped to the range $[1,p_{total}]$.
Let $p_{total} = \sum_{i=1}^k p_i$. i.e., the set of values that a code digit may take is from the range $R = [1, p_{total}]$. We map the residue class modulo $p_i$ to a distinct non-overlapping subrange of $R$. For eg: the residue class of $p_1$ (excluding 0) may be mapped to $[1,p_1-1]$ and similarly the residue class of $p_2$ (excluding 0) may be mapped to $[p_1, p_1 + p_2 - 1]$ and so on.
We can then view the generalized Master Mind game as guessing a $k$-digit code with digits in $[1,p_{total}]$ similar to guessing the 4-digit code with values in the range $[1,6]$.
I realize if we use $p_{max} = \max_{i=1}^k p_i$, take digits to be from the range $[1,p_{max}]$ and allow repetitions of codedigits (subject to digit constraints based on $p_i$) similar to the standard game, it might be another variant of the Master Mind game. As an example, let us consider $n = a\times b = 19 \times 31 = 589$ and see how the game proceeds.
Let $p_1 = 3, p_2 = 7$. These satisfy $p_1 p_2 \gt \min(a,b)$.
This is equivalent to a mastermind game with two digit code with values from $[1,6]$.
In the standard Master mind game, after each guess by the codebreaker, the codemaker responds with the number of "black" hits and number of "white" hits. From Knuth's paper:
Questions:
Q1: For the generalized Master Mind game, is there a way we can build an oracle that can provide responses like the codemaker does in the standard Master Mind game? i.e., a function that takes $n$ and the guess $g$ as inputs and returns the number of "black hits" and number of "white hits"? We can of course do this if the codemaker fixes the cofactor $a$ of $n$ to one among the possible divisors of $n$. The challenge is to build an oracle without committing to a specific cofactor $a$ or at the least use the most expansive criteria such as $a \le \sqrt n$.
I am conflicted about committing to a specific cofactor as the code and tailor the oracle's responses based on it or if we should treat the divisors of $n$ as a set and the oracle responds with number of "black" and "white" hits based on some heuristic. The reason is we don't know the factors of $n$
Q2: (Conjecture) Assuming the existence of the oracle described in Q1, then there exists a generalization of Knuth's Master Mind algorithm that solves the generalized Master Mind problem in $p_{total}$ steps or less. Can we prove or disprove this conjecture? Note that this conjecture can be treated as an algorithm for a modified Master Mind game with the only change being code digits taken from range $[1,p_{total}]$ and independent of Q1 (or integer factoring). So, any references to this generalization is also appreciated.
Update on Q2: I got the following previous related work on generalized Mastermind game from [Goodrich09]. This settles Q2. Conjecture is false. Correct estimate for guesses is $2N\lceil\log N\rceil+2N +\lceil K/N\rceil+2$ as defined below:
The original Mastermind game was invented in 1970 by Meirowitz, as a board game having holes for sequences of length N = 4 and K = 6 colored pegs. Knuth subsequently showed that this instance of the Mastermind game can be solved in five guesses or less. Chvatal studied the combinatorics of general Mastermind, showing that it can be solved in polynomial time, in the $K ≥ N$ case, using $2N\lceil \log K\rceil + 4N$ guesses, and Chen et al. showed how this bound can be improved, in this case, to $2N\lceil\log N\rceil+2N +\lceil K/N\rceil+2$ guesses. Stuckman and Zhang showed that it is NP-complete to determine if a sequence of guesses and responses in general double-count Mastermind is satisfiable.
References:
[Knuth76]: Donald E. Knuth. The Computer as Master Mind. J. Recreational Mathematics, 9 (1976-77), 1-6. (Online version here: https://www.cs.uni.edu/~wallingf/teaching/cs3530/resources/knuth-mastermind.pdf)
[Goodrich09]: Michael T. Goodrich. On the Algorithmic Complexity of the Mastermind Game with Black-Peg Results, (2009). (ArXiv online: https://arxiv.org/pdf/0904.4911.pdf)