El cubo en un módulo diferente de la computación

Question

Dado un número natural $n$, queremos encontrar otro número natural $m$ coprime a $n$, de tal forma que en la entrada de $y=x^3 \pmod n$ cualquier $x \in \mathbb{Z}_n^* \cap \mathbb{Z}_m^*$, debemos ser capaces de calcular $x^3 \pmod m$.

Tenga en cuenta que puede ser computacionalmente imposible primer lugar, calcular la raíz cúbica de a $y$ modulo $n$. Por lo tanto, el algoritmo debe elegir inteligentemente $m$ de tal manera que más tarde puede calcular $x^3 \pmod m$.

Answer 1

Esta pregunta es difícil o imposible de contestar, porque cada elemento de a $\mathbb{Z}_n^*$ tiene infinidad de representantes, muchos de los cuales son diferentes de mod $m$.

Por ejemplo, decir que mod 5 tenemos $y=2^3=8=3$ (mod 5), por lo $x=2$. Ahora, tenga en cuenta que 7 es coprime con 5. Observe también que $3,8,13$ son todos los representantes de los 3 (mod 5). Pero 3 (mod 7) es de 3, 8 (mod 7) es 1, y 13 (mod 7) es de 6. Por lo $x^3$ no está definido aún mod 7.

Usted no puede solucionar este problema mediante la elección de otro número de mods, porque si dos números son coprime, entonces usted siempre obtener diferentes respuestas como esta.

Pero si estás trabajando con programas de ordenador o algo así, es posible que sólo se considere el caso donde se toma el más pequeño positivo representante; en ese caso, es posible decir algo, pero depende del origen de su problema.