Given a prime $P$, an integer $A$ $(0\leq A<P$), and a set of legal positions (encoded as a binary mask $\text{mask}$), is there an efficient algorithm to find a number $B$ that has the same modulus as $A$ and (when $B$ is represented in its binary form) has ones only in legal positions. In other words, $B$ satisfies the following two constraints:


1. $A = B\mod P$
2. `B & (~mask) == 0`


A related problem that might be simpler is **restricting the illegal positions (~mask)** to be sparse. In this situation, a brute force search seems can finish in $O(2^k)$ steps where $k = \text{number of ones in (~mask)}$ by trying $A +P t$ for random $t$.


**Some thoughts**:


The problem seems can be reduced to **solving a linear equation on a finite field with bound constraints** if we consider the assignment of bits for $B$ in each continuous regions of ones in the $\text{mask}$ as a set of independent variables $v\_i$ with bound constraints $0\leq v\_i < 2^{s\_i}$ where $s\_i$ is the length of continuous ones.


For example, suppose the $\text{mask}$ is `1110011100111`; it is equivalently to solve the following linear equation $\mod P$:


$$A = v\_1 + 2^5\times v\_2 + 2^{10}\times v\_3\mod P$$
with constraints:
$$ 0\leq v\_1, v\_2, v\_3 < 2^3$$


But I don't know if this problem can be solved efficiently.


(Edit:
The original problem seems too hard without any restrictions. I am not sure if the following extra background makes this problem easier.
We can assume that all legal positions are below $O(\log(P))$ instead of $O(P)$. For example, we may have $P\sim 2^{64}$, and the mask is about $128$ bits long.)



Algorithm to find a number B with same modulus as A with prime P and specific binary positions set to zero
If you interpret the bit mask as encoding a finite set $S = \{2^{b\_i}\}$ of powers of $2$, you are precisely asking whether there exists a subset of $S$ which sums to $A$ modulo $p$. This is known as the modular subset-sum problem, for algorithms, see for example
<https://arxiv.org/pdf/2008.10577.pdf>


Since there are primes such that all elements of $\mathbb{Z}/p$ can be written as powers of $2$, this problem also does not seem to be easier than modular subset-sum. If I read the introduction to the linked paper correctly, there are conjectural lower bounds on the runtime that look like $p^{1-\varepsilon}$, so it doesn't seem to get better than polynomial in $p$.


(EDIT: The modular subset-sum problem is phrased as an existence statement, whereas you want to find an explicit subset. At least for the dynamic programming algorithm sketched in the beginning of the linked paper, which gets you $O(dp)$ time where $d$ is the digit sum of your mask, this should not be a problem, since instead you can tag every element of the intermediate sum set $S\_i$ by one choice of subset (or $B$) that gets you there. I haven't checked whether the other algorithms are similarly constructive)


