Navegando Z / pZ

Question

Vamos a considerar un tonto mirando pregunta primero. Considere la posibilidad de Z/pZ. Dicen que me permite hacer las dos operaciones x->x+1 y x->2*x. Luego, comenzando desde 0, no puedo expresar todo elemento de y y de Z/pZ en O(log p) pasos; por otra parte, puedo averiguar cómo hacerlo en tiempo O(log p).

La respuesta es trivial: acaba de levantar y a un entero, y se expresan en la base 2.

Ahora, ¿qué sucede si consideramos que x->r*x en lugar de x->2*x?

(Suponga que r es de orden al menos >> log p, ya que de lo contrario las cosas no funcionan.)

Que es: se puede expresar cada elemento y de Z/pZ en O(log p) pasos empezando desde 0 y utilizando las operaciones x->x+1 y x->r*x? Si es así, se puede averiguar cómo expresar ese elemento en el que se forma en O(log p) (o O((log p)^c)) pasos?

Answer 1

Deje $r$ ser la "base" e $x$ el número a representar.

Deje $m = \log_{2} (p) + \epsilon$. Construcción de la matriz $L$: $$\begin{pmatrix} x & \lambda & 0 & & ... & & 0 \\\\ 1 & 0 & \lambda & & & & 0 \\\\ \bar{r} & & & \lambda & & & \\\\ ... & & & & & & \\\\ \bar{r^m} & & & & & & \lambda \\\\ p & & & & & & 0 \end{pmatrix}$$ donde $\bar{r^i}$ es $(r^i \mod p)$. Dada una representación: $$x = \sum_{i = 0}^{m} a_i r^i (\mod p)$$ o más precisamente: $$x = \sum_{i = 0}^{m} a_i \bar{r^i} - tp$$ donde $a_i \in \{0,1\}$, se multiplica la matriz de la izquierda de la fila: $$\left( \begin{array}{ccc} 1 & -a_0 & -a_1 & ... & -a_m & t \end{array} \right)$$ y obtener la corta fila: $$\left( \begin{array}{ccc} 0 & \lambda & -a_0 \lambda & -a_1 \lambda & ... & -a_m \lambda \end{array} \right)$$ desde esperamos que el número de no cero $a_i$'s en alrededor de $\log_2(p)/2$, esperamos que la norma de esta fila será: $$\sqrt{\lambda^2 \sum_{i = 0}^{m} a_i^2} \sim \lambda \sqrt{\log_2(p)/2}$$ Tenga en cuenta que: $$|\det(L)|^{1/(m+3)} = (p \lambda^{m+2})^{1/(m+3)}$$ Al mismo tiempo queremos mantener la fila de resumen, queremos hacer otras filas de largo. Así que elegir: $$\lambda \sim p \sqrt{\log_2(p)/2}$$

Va al revés, aplicando el algoritmo LLL a $L$, para un par de pequeñas $\epsilon$, debe producir una representación.

Este algoritmo heurístico y no estoy seguro de cómo probar algo más fuerte. Trate de buscar los papeles en la mochila problema, ya que es bastante similar.