1
$\begingroup$

Let $0 \leq s_0, s_1, \ldots, s_k \leq 2^8$ be unique integers. I want to find a permutation $\sigma \in \text{S}_k$ such that the following congruence holds:

$$s_0 + s_1 \cdot 256 + s_2 \cdot 256^2 + \cdots + s_k \cdot 256^k \equiv s_0 \cdot 256^{\sigma(0)} + \cdots + s_k \cdot 256^{\sigma(k)} \pmod m$$

where $m = 2^{16} - 1$. This is equivalent to the following

\begin{align} \label{eq:1} s_0 \cdot (256^0 - 256^{\sigma(0)}) + \cdots + s_k \cdot (256^k - 256^{\sigma(k)}) \equiv 0 \pmod {2^{16} - 1} \end{align} Note that the above can be satisfied if we have \begin{align*} 256^i \equiv 256^{\sigma(i)} \pmod {2^{16} - 1} \end{align*} for all $0 \leq i \leq k$. Since $2^{16} - 1 = 256^2 - 1$, we see that $256$ has order $2 \pmod {2^{16} - 1}$, so the above is equivalent to $i \equiv \sigma(i) \pmod 2$.

However, this is only one possible way of satisfying the congruence. For example, if we take the integers $s_0 = 1, s_1 = 0, s_2 = 3, s_3 = 4, s_4 = 5, s_5 = 2, s_6 = 7, s_7 = 10$, then we see that the congruence also holds by taking $\sigma$ to be the cycle $(1\ 0\ 3\ 4\ 5\ 2\ 7\ 10)$. But note that this doesn't always work, only for certain inputs $s_0 , \ldots, s_k$.

Given $s_0, s_1, \ldots, s_k$, is there an algorithm for generating all permutations that makes the congruence true?

Update: So it turns out that any permutation with $$\sum_\limits{\substack{i \equiv 0 \pmod 2\\ \sigma(i) \equiv 1 \pmod 2}}s_i \equiv \sum_\limits{\substack{j \equiv 1 \pmod 2\\ \sigma(j) \equiv 0 \pmod 2}}s_j \pmod {2^{16} - 1}$$

also work, and this is not too hard to see.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.