0
$\begingroup$

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.)

Improve this question
$\endgroup$
1
  • $\begingroup$ Dear NSA, nice try. $\endgroup$
    – Andrej Bauer
    Commented Jul 10, 2023 at 9:22

1 Answer 1

Reset to default
2
$\begingroup$

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)

Improve this answer
$\endgroup$
3
  • $\begingroup$ The linked algorithm has running time polynomial in $P$, which is exponential in the size of the input. So it's hardly "efficient". $\endgroup$
    – Emil Jeřábek
    Commented Jul 10, 2023 at 8:40
  • 2
    $\begingroup$ Good point, I somehow was not thinking about the complexity in $p$ (probably because primes in my life are usually small ;) ). But for general $p$ the problem seems equivalent to modular subset-sum, so I guess one shouldn't expect much faster algorithms. $\endgroup$
    – Achim Krause
    Commented Jul 10, 2023 at 8:50
  • $\begingroup$ Thanks a lot! Achim. I feel the same as Emil --- the time is still not practically usable for moderately sized prime like $P=2^{64}-2^{32}+1$. So the last hope is whether the special property of binary encoding makes the problem easier than subset-sum (whose lower bounded by $p^{1-\epsilon}$. Your counter-example (the primes where all elements in $Z/p$ are some powers of 2) eliminates 99% of such hope I believe. I actually care about the situation of using a mask where legal positions are below $O(\text{log}(P)$. So there is a last 1% chance for someone to exploit this (but unlikely). $\endgroup$
    – bang
    Commented Jul 10, 2023 at 9:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .