# Is it possible to reverse this sequence of permutations?

Let $S = (a_1, a_2, ..., a_N)$ be a finite (arbitrarily long) sequence of elements, and let $p_1, p_2, ..., p_n$ be the first $n$ prime numbers, with $n \ge 3$.

We apply a sequence of permutations to $S$ as follows.

First, we take every element in $S$ whose index is congruent with 1 modulo 2, and we rotate them within themselves $A^2_1$ positions (where $A^2_1$ is an integer in $[0, N/2)$). For instance, if $S = (a,b,c,d,e,f)$, and $A^2_1=2$, the result would be $(\mathbf c,b,\mathbf e,d,\mathbf a,f)$.

In the second place, we take every element in the sequence obtained whose index is congruent with $0$ (that is, the rest), and rotate them within themselves $A_0^2$ positions (where $A^2_0$ is an integer in $[0,N/2)$); that will be $S_1$. Following the previous example, rotating with $A^2_0 = 1$ would bear $S_1 = (c,\mathbf f,e,\mathbf b,a,\mathbf d)$.

Now, we take every element in $S_1$ with index congruent with 1 modulo 3, and we rotate them within themselves $A^3_1$ positions; afterwards, every element with index congruent with 2 modulo 3, $A^3_2$ positions, and finally, every element with index congruent with 0 modulo 3, $A^3_0$ positions. $A_i^3$ is an integer in $[0,N/3)$. Continuing the example, assuming $A^3_1 = 1, A^3_2 = 0, A^3_0 = 1$, we would obtain $(b,f,d,c,a,e)$.

This process is repeated for every prime up to $p_n$, and let $S_n$ be the result.

(Edited: see below) My question is: assuming $n$ and $S_n$ are known, how much additional information would be necessary to calculate the coefficients? (Edited: see below) By additional information I mean, for example, knowing the initial positions (in $S$) of some elements in $S_n$. I have been working for days on this, but my current option, which is straightforward using systems of equations, does not seem t otake me anywhere since I don't know which coefficients are being used in each case. Is there any other approach that I should consider?

Apologies for my English, and sorry if this is not the correct stackexchange site for this question.

EDIT: As Alexander pointed, coefficients would not be unique (see his example below), so to state it more accurately: would it be possible to obtain the original $S$ given $n, S_n$, and some additional information?

This problem is related to a cryptography project, where I intend to cypher a message by rearranging it, using coefficients as a key. This means that, even if the original permutation (or any complete set of coefficients) were impossible to find, any way to determine information on them, or bounding them, would greatly hurt the scheme. I know this is not the place for crypto problems, but maybe explaining the objective would be useful to anyone trying to answer.

-

If I understand correctly, we can take $$(a_1,\ldots,a_{12})$$ and pick primes $2,3$. Then we can set $A_0^2=A_1^2=3$ and $A_0^3=A_1^3=A_2^3=2$ and the permutation produced by the algorithm is the identity permutation, the same as if we had chosen $A_0^2=A_1^2=A_0^3=A_1^3=A_2^3=0$.
So even if you have $S_n$, $n$, and the initial position of each $a_i$, you can still in general have multiple solutions. I would say there is no way to determine the coefficients $A_i^j$ uniquely.
I realize that you said $n\geq 3$, but the above example is illustrative. Note that even for $n\geq 3$ and even if you insist that $N=\prod_{i=1}^np_i$ (which is the minimum value of $N$, since $N$ must be divisible by each $p_i$) this does not change. When $n=3$ and $N=30$, we can set $A_0^2=A_1^2=3$ and $A_0^3=A_1^3=A_2^3=8$ and $A_0^5=A_1^5=A_2^5=A_3^5=A_4^5=0$ and obtain the identity permutation, as well as $A_0^2=A_1^2=A_0^3=A_1^3=A_2^3=6$ and $A_0^5=A_1^5=A_2^5=A_3^5=A_4^5=0$.
The permutations are unique for the case where $n=2$ and $N=6$, in which case the possible permutations correspond to the unique subgroup of $S_6$ of order $72$. But this is the only such case.