¿Es posible revertir esta secuencia de permutaciones?

Question

Vamos $ S = (a_1, a_2, ..., a_N) $ ser un número finito (arbitrariamente larga) de la secuencia de elementos, y deje $p_1, p_2, ..., p_n $ ser el primero $n$ números primos, con $n \ge 3$.

Aplicamos una secuencia de permutaciones de a $S$ como sigue.

En primer lugar, tomamos cada elemento en $S$ cuyo índice es congruente con 1 módulo 2, y lo hacemos girar dentro de sí mismos $A^2_1$ posiciones (donde $A^2_1$ es un número entero en $[0, N/2)$). Por ejemplo, si $S = (a,b,c,d,e,f)$, e $A^2_1=2$, el resultado sería la $(\mathbf c,b,\mathbf e,d,\mathbf a,f)$.

En segundo lugar, tomamos cada elemento en la secuencia obtenida cuyo índice es congruente con $0$ (es decir, el resto), y girar dentro de sí mismos $A_0^2$ posiciones (donde $A^2_0$ es un número entero en $[0,N/2)$); que se $S_1$. Siguiendo con el ejemplo anterior, la rotación con $A^2_0 = 1$ oso $S_1 = (c,\mathbf f,e,\mathbf b,a,\mathbf d)$.

Ahora, tomamos cada elemento en $S_1$ con índice congruentes con 1 modulo 3, y lo hacemos girar dentro de sí mismos $A^3_1$ posiciones; después, cada elemento con el índice congruentes con 2 modulo 3, $A^3_2$ posiciones, y finalmente, cada elemento con el índice congruentes con 0 módulo 3, $A^3_0$ posiciones. $A_i^3$ es un número entero en $[0,N/3)$. Continuando con el ejemplo, suponiendo $A^3_1 = 1, A^3_2 = 0, A^3_0 = 1$, obtendríamos $(b,f,d,c,a,e)$.

Este proceso se repite para cada primer hasta el $p_n$, y deje $S_n$ ser el resultado.

(Editado: ver más abajo) Mi pregunta es: asumiendo $n$ $S_n$ son conocidos, cuánta información adicional que sería necesario para calcular los coeficientes? (Editado: véase a continuación) información adicional me refiero, por ejemplo, conocer las posiciones iniciales (en $S$) de algunos elementos en $S_n$. He estado trabajando durante días sobre esto, pero mi opción actual, que es sencillo de utilizar los sistemas de ecuaciones, no parece t otake mí en cualquier lugar ya que no sé que los coeficientes que se utilizan en cada caso. Hay otro enfoque que debo considerar?

Pido disculpas por mi inglés, y lo siento si este no es el correcto stackexchange sitio para esta pregunta.

EDIT: Como Alexander señaló, los coeficientes no sería el único (consulte el ejemplo de abajo), por lo que para decirlo con más precisión: sería posible obtener el original de $S$$n, S_n$, y alguna información adicional?

Este problema está relacionado con un proyecto de criptografía, donde tengo la intención de cypher un mensaje por modificaciones, utilizando coeficientes como una clave. Esto significa que, incluso si el original de la permutación (o cualquier conjunto completo de los coeficientes) eran imposibles de encontrar, de cualquier manera, para determinar la información sobre los mismos, o de delimitación de ellos, haría mucho daño el esquema. Sé que este no es el lugar para crypto problemas, pero tal vez explicando el objetivo de ser útil a cualquier persona tratando de responder.

Answer 1

Si entiendo correctamente, podemos tomar $$(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$.

Así que incluso si usted tiene $S_n$, $n$, y la posición inicial de cada una de las $a_i$, todavía se puede, en general, tienen múltiples soluciones. Yo diría que no hay ninguna manera de determinar los coeficientes $A_i^j$ únicamente.

Me doy cuenta de que usted dice $n\geq 3$, pero el ejemplo anterior es ilustrativo. Tenga en cuenta que incluso para$n\geq 3$, e incluso si usted insistir en que $N=\prod_{i=1}^np_i$ (que es el mínimo valor de $N$, ya que el $N$ debe ser divisible por cada uno de los $p_i$) esto no cambia. Al$n=3$$N=30$, podemos establecer $A_0^2=A_1^2=3$ $A_0^3=A_1^3=A_2^3=8$ $A_0^5=A_1^5=A_2^5=A_3^5=A_4^5=0$ y obtener la identidad de permutación, así como de $A_0^2=A_1^2=A_0^3=A_1^3=A_2^3=6$$A_0^5=A_1^5=A_2^5=A_3^5=A_4^5=0$.

Las permutaciones son únicos para el caso de que $n=2$$N=6$, en cuyo caso las posibles permutaciones corresponden al subgrupo único de $S_6$ orden $72$. Pero este es el único caso.