Demostrar lema: orden de $x\ \mathrm{mod}\ N$ es par con probabilidad $1/2$

Question

En el libro Algorithms de Vazirani et al., se expone un sencillo lema sin pruebas:

Dejemos que $N$ sea un compuesto impar, con al menos dos factores primos, y sea $x$ se elija uniformemente al azar entre $0$ y $N-1$ . Si $\gcd(x,N)=1$ entonces, con una probabilidad de al menos $1/2$ la orden $r$ de $x \mod N$ está en paz.

Nota: el orden $r$ de $x$ modulo $N$ es el menor número entero positivo $r$ tal que $x^r \equiv 1\ \mathrm{mod}\ N$ .

He tratado de probar esto, sin éxito. Las únicas pistas que me dan es que puede implicar el Pequeño Teorema de Fermat o el Teorema del Resto Chino.

Se agradecería una prueba, un esbozo de prueba o incluso una referencia a una.

Answer 1

Dejemos que $1 \le x \le N - 1$ y $\gcd(x, N) = 1$ . Si $x$ tiene orden de impar $2m+1$ entonces $-x$ tiene un orden uniforme $2(2m+1)$ . Por lo tanto, para cada orden impar $x$ hay una única correspondencia $-x$ de orden par. Así que el número de elementos de orden par es al menos la mitad.

Prueba de que $-x$ tiene orden $2(2m+1)$ . Este es un caso especial del hecho de que si $a$ y $b$ son elementos de un grupo abeliano de orden $m$ y $n$ respectivamente y $\gcd(m,n)=1$ entonces $ab$ tiene orden $mn$ .

Aquí está la prueba del orden de $-x$ . Sea $n$ sea el orden de $-x$ . Entonces $1 = (-x)^n = (-1)^nx^n$ . Consideremos dos casos: $n$ es impar o $n$ está en paz.

Si $n$ es impar, entonces $x^n = -1$ , $x^{2n} = 1$ , lo que implica $2m+1$ divide $2n$ y por lo tanto $2m+1$ divide $n$ . Así que $x^n = 1 = -x^n = -1$ , lo que significa que $2 = 0 \mod N$ . Esto es imposible ya que $N$ es impar.

Si $n$ es par, entonces $1 = (-x)^n = x^n$ lo que implica que $2m+1$ divide $n$ . Desde $n$ es par, el más pequeño de tales $n$ est $2(2m+1)$ . Verificamos que $(-x)^{2(2m+1)} = 1$ .