Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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.

share|improve this answer
    
Thank you, Alexander! Great point on lack of unicity, I hadn't noticed that. Probably, even if the coefficients are forced to be all different, unicity still won't be possible; I'll look into that! On the other hand, my (admittedly unstated... sorry!) intention with this question was to "undo" the permutation. I hurried to assume unicity of the coefficients, which I thought would be equivalent with "undoing" the transformations, but I am going to edit the question to further clarify. Thank you for your time! :) –  Carlos Jan 9 '13 at 12:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.