Reducción del factoraje a la búsqueda del orden

Question

Teorema

Deje que $N$ ser un número general de impar, que escrito como su factorización principal es $N = {p_1}^{ \alpha_1 } {p_2}^{ \alpha_2 } \dots {p_s}^{ \alpha_s }$ . Si $x$ se elige uniformemente al azar de $\mathbb {Z}^{*}_N$ (grupo de números coprime a $N$ ) y $r$ es el orden de $x$ modulo N. Entonces \begin {ecuación} \mathbb {P} [r] \text { es par y }x^{r/2} \not\equiv -1 \text { mod } N] \geq 1 - \frac {1}{2^{s}} \end {ecuación}

Prueba

Tenemos que mostrar eso, \begin {ecuación*} \mathbb {P} [r] \text { es impar o }x^{r/2} \equiv -1 \text { mod } N] \leq \frac {1}{2^s} \end {ecuación*}

El teorema del resto de China establece que $\mathbb {Z}^{*}_N \cong \mathbb {Z}^{*}_{{p_1}^{ \alpha_1 }} \times \mathbb {Z}^{*}_{{p_2}^{ \alpha_2 }} \times \dots \times \mathbb {Z}^{*}_{{p_s}^{ \alpha_s }}$ de lo que podemos deducir que la elección $x$ uniformemente al azar de $\mathbb {Z}^{*}_N$ es equivalente a elegir $x_i$ uniformemente al azar de $\mathbb {Z}^{*}_{{p_j}^{ \alpha_j }}$ .

Deje que $r_j$ ser el orden de $x_j$ modulo ${p_j}^{ \alpha_j }$ y dejar $2^{m_j}$ ser la mayor potencia de $2$ que divide $r_j$ . Así que $k_j 2^{m_j} = r_j$ y $k_j$ impar.

Supongamos que $r$ es impar, lo que implica que $r_j$ debe ser impar para cada $j$ (así que $m_j = 0$ ), que se produce con probabilidad $2^{-s}$ (de un resultado anterior).

Ahora asume que $r$ es parejo, pero $x^{r/2} \equiv -1 \text { mod } N$ . Luego $x^{r/2} \equiv -1 \text { mod } {p_j}^{ \alpha_j }$ . Esto implica que $r_j$ no divide $\dfrac {r}{2}$ para ver esta suposición $r_j \Big | \dfrac {r}{2} \implies cr_j = \dfrac {r}{2}$ y por lo tanto $x_j^{r/2} \equiv x_{j}^{cr_j} \equiv (x_{j}^{r_j})^c \equiv 1 \text { mod } {p_j}^{ \alpha_j } \not\equiv -1 \text { mod } {p_j}^{ \alpha_j }$ dando una contradicción.

Por lo tanto, debemos tener que todos $m_j$ son iguales a un valor común $m$ .

Está probando esta declaración final donde estoy atascado. Las notas, que estoy usando dicen;

"Porque $r_j$ todos se dividen $r$ y de hecho $r$ es un múltiplo común de la $r_j$ así que si uno de los $m_j$ tiene un poder extra de $2$ eliminando esto, los otros deberían seguir dividiéndose $\dfrac {r}{2}$ . Pero hemos demostrado que esto no es cierto."

Mi intento de prueba (WLOG $r_1$ tiene un poder extra de $2$ ) \begin {alineado*} r &= c r_1 r_2 \dots r_s \text {(ya que la r es un múltiplo común)} \\ r &= c (k_1 2^{m+1}) r_2 \dots r_s \\ \dfrac {r}{2} &= c (k_1 2^{m}) r_2 \dots r_s \end {alineado*} y por lo tanto $r_j, \Big | \dfrac {r}{2}$ para $j = 2 \dots s$ la contradicción.

Sin embargo, seguramente podemos repetir esta prueba cuando todos $m_j$ son iguales y obtienen la misma contradicción? Entonces, ¿en qué me equivoco?

Answer 1

Cuando escribes $$r = c r_1 r_2 \cdots r_s \quad \text {(since r is common multiple)}$$ $c$ no es generalmente un número entero, por lo que no sigue directamente de $$\frac {r}{2} = c (k_1 2^{m_1-1})r_2 \cdots r_s$$ que $r_2 \mid \frac {r}{2}$ . También se basa en los hechos que $2^{m_1} \mid r$ y $m_1>m_2$ (el último es el verdadero WLOG cuando no todos $m_j$ son iguales).

Si todos $m_i=m_2$ entonces $2^{m_2}$ es el poder más alto de $2$ que divide el múltiplo menos común de la $r_i$ y así puede ser el poder más alto de $2$ que divide $r$ (que puede ser cualquier múltiplo común, posiblemente el LCM), en cuyo caso $r_2 \not \mid \frac {r}{2}$ . Sólo se garantiza que $r_2 \mid \frac {r}{2}$ si $m_i>m_2$ para algunos $i$ .

Para ilustrarlo, considere $N=13 \times 29 \times 53$ y $x=2$ de donde $$p_1=13,p_2=29,p_3=53 \\ r_1=12,r_2=28,r_3=52 \\ m_1=m_2=m_3=2 \\ r = \frac {1}{16} r_1 r_2 r_3$$ El poder más alto de $2$ que divide $r$ es $2^2$ y ninguno de los $r_1,r_2,r_3$ divide $r/2$ .