[Eparoh]

Hola a todos, estoy intentando entender la demostración del "Fact 1" en este artículo: https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf
Expondré aquí la demostración de todas formas, para marcar el punto que no veo.

Proposición: Sea \( (n,e) \) la clave pública en un cifrado de RSA y \( d \) la calve privada. Conociendo \( e \) y \( d \) es posible factorizar \( n \).

La demostración es como sigue:

Como \( ed \equiv{} 1 \mod \phi(n) \) (con \( \phi \) la función de Euler) entonces expresando \( k=ed-1 \) tenemos que es un múltiplo de \( \phi(n) \) y, como éste último es par (pues si es \( n=pq \) entonces \( \phi(n)=(p-1)(q-1) \)) tenemos que \( k \) es par y podemos expresar \( k=2^tr \) con \( t \geq 1 \) y \( r \) impar.

Elegimos ahora \( 2\leq g \leq n-1 \), si \( \gcd(g,n)>1 \) entonces al ser \( n=pq \), tenemos que \( g \) es un factor de \( n \) y concluimos.
Por otro lado, si \( \gcd(g,n)=1 \) entonces por el teorema de Euler y al ser \( k \) un múltiplo de \( \phi(n) \) tenemos que \( g^k \equiv{} 1 \mod n \) y por tanto, \( g^{k/2} \) será una raíz cuadrada de la unidad módulo \( n \).
Observemos ahora que por el teorema chino de los restos, uno tiene 4 raíces cuadradas de la unidad módulo \( n \) que son \( 1 \), \( -1 \) y las soluciones de los sistemas

\( \begin{cases} x \equiv{} 1 & \mod p \\ x \equiv{} -1 & \mod q \end{cases} \)    y    \( \begin{cases} x \equiv{} -1 & \mod p \\ x \equiv{} 1 & \mod q \end{cases} \)

Si es \( z \) solución de este primer sistema observamos que \( p|z-1 \) y que \( z-1 \equiv{} -2 \mod q \) luego \( q \not | z-1 \) y así, \( \gcd(z-1,n)=p \).
Análogamente, si es \( z \) solución del segundo sistema, entonces \( \gcd(z-1,n)=q \).

Por tanto, para factorizar \( n \) basta encontrar una raíz cuadrada, no trivial, de uno módulo \( n \).

Ahora, llega el punto que no entiendo.
El artículo establece que dado \( g \) coprimo con \( n \) aleatorio, la probabilidad de encontrar una  raíz cuadrada, no trivial, de uno módulo \( n \) en el conjunto

\( g^{k/2} \mod n, g^{k/4} \mod n, \cdots, g^{k/2^t} \mod n \)

es mayor o igual a \( 1/2 \).

Suponiendo esto cierto, es ya claro que escogiendo \( m \) números entre \( 2 \) y \( n-1 \) la probabilidad de factorizar \( n \) es mayor que \( 1-1/2^m \) lo cual nos garantiza que podemos factorizar \( n \) es una cantidad relativamente pequeña de pasos.

Sin embargo, de donde sale esta probabilidad, ¿cómo podemos probar que efectivamente al escoger \( g \) de forma aleatoria en al menos la mitad de los casos existe una raíz cuadrada, no trivial, de uno módulo \( n \) en el conjunto descrito?

Espero que alguien pueda responderme, pues llevo toda la noche peleándome con este punto de la demostración y no consigo llegar a nada.

Un saludo, y muchas gracias por las respuestas.

[geómetracat]

Es un problema muy chulo. Te explico cómo reducirlo a un problema más estándar de probabilidad/combinatoria. Quizás haya una manera bastante más sencilla, porque esto no es muy "straightforward", pero es lo único que se me ha ocurrido.

Pongamos \( p-1=2^ax, q-1=2^by \), con \( x,y \) impares. Entonces:
 \( \Bbb Z_n^* \cong \Bbb Z_p^* \times \Bbb Z_q^* \cong \Bbb Z_{p-1} \times \Bbb Z_{q-1} \cong \Bbb Z_{2^a} \times \Bbb Z_{2^b} \times \Bbb Z_x \times \Bbb Z_y \).
El primer y el último isomorfismo son el teorema chino del resto (junto con el hecho de que el grupo de unidades de un producto es el producto del grupo de unidades), y el segundo isomorfismo es el hecho de que el grupo de unidades de \( \Bbb Z_p \) con \( p \) primo es cíclico de orden \( p-1 \). Por tanto, elegir un \( g \in Z_n^* \) es lo mismo que elegir una tupla \( (n_1,n_2,n_3,n_4) \in \Bbb Z_{2^a} \times \Bbb Z_{2^b} \times \Bbb Z_x \times \Bbb Z_y \).

Ahora, fíjate que en el conjunto \( \{g^{k/2}, \dots, g^{k/2^t}=g^r\} \) hay como mucho una raíz de la unidad distinta de \( 1 \), que será precisamente el primer número de ese conjunto que sea distinto de \( 1 \). En otras palabras, hay una aplicación bien definida que asigna a cada \( g \) una raíz de la unidad (se le asigna \( 1 \) si \( g^r=1 \)). Ahora bien, bajo el isomorfismo \( \Bbb Z_n^* \cong \Bbb Z_{2^a} \times \Bbb Z_{2^b} \times \Bbb Z_x \times \Bbb Z_y \), si \( g \) corresponde a la tupla \( (n_1,n_2,n_3,n_4) \), \( g^r \) corresponde a \( (rn_1,rn_2,rn_3,rn_4) = (rn_1,rn_2,0,0) \) (las últimas entradas son cero porque \( (g^r)^{2^t} =1 \) y \( 2^t \) es coprimo con \( x \) y con \( y \)). Por otro lado, como \( r \) es impar, la aplicación \( \Bbb Z_{2^a} \times \Bbb Z_{2^b} \rightarrow \Bbb Z_{2^a} \times \Bbb Z_{2^b}    \) dada por \( (n_1,n_2) \mapsto (rn_1,rn_2) \) es un isomorfismo, de manera que el número de \( g \)'s que corresponden a \( (n_1,n_2) \) es el mismo que el número de \( g \)'s tales que \( g^r \) corresponde a \( (n_1,n_2) \).

Juntando todas estas observaciones, llegamos a que la probabilidad pedida es la misma que la probabilidad de que, escogiendo al azar un par \( (n_1,n_2) \in \Bbb Z_{2^a} \times \Bbb Z_{2^b} \), tengamos que \( 2^z(n_1,n_2) \) sea igual a \( (2^{a-1},0) \) o a \( (0,2^{b-1}) \) para algún \( z \geq 0 \). Esto depende únicamente de las mayores potencias de \( 2 \) que dividan a \( n_1 \) y a \( n_2 \) respectivamente. Ahora ya es cuestión de hacer un poco de combinatoria.

No sé si lo he explicado muy bien, porque es un tanto enredado. Cualquier duda pregunta de nuevo.

[Eparoh]

Muchas gracias por la respuesta.
Puede que este un poco espeso, pero no veo porque razón los \( rn_3 \) y \( rn_4 \) son nulos.
Tampoco comprendo la equivalencia a la que llegas, ¿por qué ésta probabilidad es la misma que buscabamos?
Respecto a la combinatoria final, tampoco estoy muy seguro de como hacerla, pero volveré a intentarlo cuando entienda bien la equivalencia anterior.
Un saludo.

[geómetracat]

Puede que este un poco espeso, pero no veo porque razón los \( rn_3 \) y \( rn_4 \) son nulos.

Porque sabes que \( (2^trn_3,2^trn_4)=(0,0) \) (esto porque \( g^{2^tr}=1 \)) y como \( x,y \) son impares multiplicar por \( 2^t \) es un isomorfismo.

Tampoco comprendo la equivalencia a la que llegas, ¿por qué ésta probabilidad es la misma que buscabamos?

Por un lado, escoger un \( g \) al azar es lo mismo que escoger un \( (n_1,n_2,n_3,n_4) \) al azar. Lo que hemos visto es que para la probabilidad que nos interesa (que es la probabilidad de que la única posible raíz cuadrada de la unidad distinta de \( 1 \) en \( g^r, g^{2r}, g^{2^2r}, \dots, g^{2^tr} \) sea una de las dos raíces no triviales) es lo mismo que la probabilidad de escoger un \( (n_1,n_2,n_3,n_4) \) tal que uno de los \( 2^z(rn_1,rn_2,rn_3,rn_4) \) con \( z=0,1,\dots,t \) sea de la forma \( (2^{a-1},0,0,0) \) o \( (0,2^{b-1},0,0) \), porque estas son las tuplas que corresponden bajo el isomorfismo a las dos raíces no triviales. Como \( rn_3=rn_4=0 \), podemos olvidarnos directamente de los dos últimos factores. Es decir, tenemos que la probabilidad buscada es la misma que la de, escogiendo un par \( (n_1,n_2) \) al azar, uno de los \( 2^z(rn_1,rn_2) \) sea \( (2^{a-1},0) \) o \( (0,2^{b-1}) \). Pero como multiplicar por \( r \) es un isomorfismo, es lo mismo tomar \( (n_1,n_2) \) al azar que tomar directamente \( (rn_1,rn_2) \) al azar.

Añadido: Por completitud, pongo la combinatoria calculando la probabilidad, que no había pensado antes por pereza. Lo dejo en spoiler por si tú (o quien lea esto) lo quiere pensar.

Spoiler

Es más fácil calcular la probabilidad del suceso complementario, es decir, la probabilidad de que tomando un par \( (n_1,n_2) \in \Bbb Z_{2^a} \times \Bbb Z_{2^b} \), ninguno de \( (2^zn_1,2^zn_2) \) sean \( (2^{a-1},0) \)
ni \( (0,2^{b-1}) \).
Sin pérdida de generalidad, suponemos \( a \leq b \). Dado \( (n_1,n_2) \) lo escribimos \( (2^il,2^jl') \) con \( 0 \leq i \leq a, 0\leq j \leq b \) y \( l,l' \) impares (tomamos ahora como representantes de las clases \( 1,2, \dots, 2^a \) y \( 1, 2, \dots, 2^b \) respectivamente, porque es más fácil para los cálculos). La única manera de que \( 2^z(2^il,2^jl') \) no sea de la forma \( (2^{a-1},2^b) \) ni \( (2^a,2^{b-1}) \) es que tengamos \( j = b-a + i \), ya que es la única manera de que ambos factores lleguen a \( 2^a \) (respectivamente \( 2^b \)) a la vez (es decir que cuando \( 2^{z+i}=2^a \) también tengamos \( 2^{z+j}=2^b \)).
Ahora bien, para cada \( i \) fijado, \( n_1 = 2^il \)
con \( l \) impar y hay \( \phi(2^{a-i}) \) posibilidades para \( l \) (impares que hagan que \( 2^il \leq 2^a \)). Por el mismo razonamiento, hay \( \phi(2^{b-j})= \phi(2^{b-b+a-i}) = \phi(2^{a-i}) \) posibilidades para \( n_2 \). Por tanto, sumando para todo \( i \), el número de casos favorables es:
\( \sum_{i=0}^a \phi(2^{a-i})^2 \).
Por otro lado, el número de casos posibles es \( 2^{a+b} \), que es el número total de tuplas, sin restricciones.
Así, la probabilidad del suceso complementario del que estamos interesados es:
\( \frac{ \sum_{i=0}^a \phi(2^{a-i})^2}{2^{a+b}} = \frac{1 + 1 + 4 + 4^2 + \dots + 4^{a-1}}{2^{a+b}}= \frac {1 + \frac{4^a -1}{3}}{2^{a+b}} = \frac{4^a+2}{3\cdot 2^{a+b}} \).
Finalmente, la probabilidad que estábamos buscando desde el principio será:
\( P = 1 - \frac{4^a+2}{3\cdot 2^{a+b}}  \).
Falta ver que siempre es mayor o igual que \( 1/2 \). Para esto, fíjate que el mínimo de \( P \) se alcanza para \( b=a \) (recuerda que \( a\leq b \) por hipótesis), en cuyo caso queda \( P \geq 1 - \frac{1}{3} \left(1 + \frac{2}{4^a}\right) \), y esta última expresión es máxima cuando \( a=1 \), que es el valor mínimo de \( a \). En este caso, la expresión es \( 1/2 \), así que \( P \geq 1/2 \) y la igualdad se da únicamente en el caso \( a=b=1 \).

[cerrar]

Bueno, como ves la cosa está lejos de ser "straightforward". Esto probablemente quiere decir que hay una forma más directa de ver la cota \( 1/2 \), porque lo que he hecho aquí es calcular la probabilidad exacta. También puede pasar que este argumento fuera el que tenía en mente el autor y le diera pereza explicarlo, cosa que desgraciadamente es bastante habitual.

[Eparoh]

Hola, creo que lo he entendido todo, salvo un par de detalles.
La primera duda que tengo es que, tras el primer isomorfismo de \( \Bbb Z_n^* \) en \( \Bbb Z_{2^a} \times \Bbb Z_{2^b} \times \Bbb Z_x \times \Bbb Z_y \), se que las raíces cuadradas de la unidad módulo \( n \) serán \( (0,0,0,0), (2^{a-1},2^{b-1},0,0),(2^{a-1},0,0,0),(0,2^{b-1},0,0) \), y es claro que la primera corresponde al \( 1 \) pero, ¿cómo sabemos que la segunda corresponde al \( -1 \)?

Y mi última duda es sobre el spoiler, así que lo pondré también en spoiler.

Spoiler

La única manera de que \( 2^z(2^il,2^jl') \) no sea de la forma \( (2^{a-1},2^b) \) ni \( (2^a,2^{b-1}) \) es que tengamos \( j = b-a + i \), ya que es la única manera de que ambos factores lleguen a \( 2^a \) (respectivamente \( 2^b \)) a la vez (es decir que cuando \( 2^{z+i}=2^a \) también tengamos \( 2^{z+j}=2^b \)).

No veo para nada porque razón es eso cierto.
Es decir, por lo que dices, si \( j \not = b-a + i \) entonces existe un \( z=0,1, \cdots, t-1 \) tal que \( 2^z(2^il,2^jl')=(2^{a-1},2^b) \) o \( 2^z(2^il,2^jl')=(2^a,2^{b-1}) \), pero no entiendo porque esto es cierto con el razonamiento que sigues.

[cerrar]

Bueno, como ves la cosa está lejos de ser "straightforward". Esto probablemente quiere decir que hay una forma más directa de ver la cota \( 1/2 \), porque lo que he hecho aquí es calcular la probabilidad exacta. También puede pasar que este argumento fuera el que tenía en mente el autor y le diera pereza explicarlo, cosa que desgraciadamente es bastante habitual.

Aun soy estudiante, y he leido relativamente pocos papers pero por desgracía ya he podido comprobar en varios de ellos como se omiten detalles que no son para nada triviales o directos como menciona el autor 
Me ha gustado mucho la demostración. Supongo que es algo habitual transformar problemas combinatorios complicados en otros más sencillos a través del uso de herramientas algebraicas, pero nunca dejará de fascinarme cuando en una demostración se realizan este tipo de transformaciones que casi de forma mágica lo simplifica todo.
Gracias por las respuestas 

[geómetracat]

La primera duda que tengo es que, tras el primer isomorfismo de \( \Bbb Z_n^* \) en \( \Bbb Z_{2^a} \times \Bbb Z_{2^b} \times \Bbb Z_x \times \Bbb Z_y \), se que las raíces cuadradas de la unidad módulo \( n \) serán \( (0,0,0,0), (2^{a-1},2^{b-1},0,0),(2^{a-1},0,0,0),(0,2^{b-1},0,0) \), y es claro que la primera corresponde al \( 1 \) pero, ¿cómo sabemos que la segunda corresponde al \( -1 \)?

Porque, viéndolo en \( \Bbb Z_p^* \times \Bbb Z_q^* \) vía los isomorfismos, corresponde a \( (-1,-1) \) mientras que las otras dos que no son el \( 1 \) corresponden a \( (1,-1) \) y a \( (-1,1) \).

Y mi última duda es sobre el spoiler, así que lo pondré también en spoiler.

Spoiler

La única manera de que \( 2^z(2^il,2^jl') \) no sea de la forma \( (2^{a-1},2^b) \) ni \( (2^a,2^{b-1}) \) es que tengamos \( j = b-a + i \), ya que es la única manera de que ambos factores lleguen a \( 2^a \) (respectivamente \( 2^b \)) a la vez (es decir que cuando \( 2^{z+i}=2^a \) también tengamos \( 2^{z+j}=2^b \)).

No veo para nada porque razón es eso cierto.
Es decir, por lo que dices, si \( j \not = b-a + i \) entonces existe un \( z=0,1, \cdots, t-1 \) tal que \( 2^z(2^il,2^jl')=(2^{a-1},2^b) \) o \( 2^z(2^il,2^jl')=(2^a,2^{b-1}) \), pero no entiendo porque esto es cierto con el razonamiento que sigues.

[cerrar]

Spoiler

Supongamos que \( j \neq b-a+i \). Entonces, cuando vamos multiplicando por potencias de \( 2 \) sucesivas, vamos obteniendo:
\( (2^il,2^jl'), (2^{i+1}l,2^{j+1}l'), (2^{i+2}l,2^{j+2}l'), \dots \)
Sea \( k \) el primer número tal que \( 2^{i+k}=2^a \) o \( 2^{j+k}=2^b \) (\( k \) puede ser \( 0 \)). Supongamos por ejemplo que se da el primer caso, \( 2^{i+k}=2^a \), luego \( k = a-i \). Si tuviéramos también que \( 2^{j+k}=2^b \), tendríamos \( k = b -j \) e igualando \( j = b-a+i \). Lo mismo si se da el segundo caso.
Esto quiere decir que al ir multiplicando por \( 2 \) llegamos a un momento en que tenemos algo del estilo \( (2^nl,0) \) con \( n<a \) o \( (0,2^nl) \) con \( n<b \) (aquí uso \( 0=2^a \) y \( 0=2^b \) en los grupos respectivos, porque es más sencillo verlo con el \( 0 \)). Pero una vez llegamos a una tupla de este estilo está claro que al ir multiplicando por \( 2 \) llegaremos a \( (2^{a-1}l,0)=(2^{a-1},0) \) o a \( (0,2^{b-1}l)=(0,2^{b-1}) \).
Recíprocamente, si se cumple \( j=b-a+i \), para el \( k \) definido arriba tenemos \( (2^a,2^b)=(0,0) \) y por la definición de \( k \) las anteriores tuplas no tienen ningún componente \( 0 \), de manera que no se alcanza una de las dos raíces no triviales.
 

[cerrar]

Aun soy estudiante, y he leido relativamente pocos papers pero por desgracía ya he podido comprobar en varios de ellos como se omiten detalles que no son para nada triviales o directos como menciona el autor 

Es una desgracia, pero es muy habitual ver papers con cosas del tipo "it is straightforward", "as it is easy to see...", "it is well-known that..." y cosas por el estilo. Muchas veces esas cosas no son fáciles y las pone el autor para ahorrarse los detalles de algunos argumentos. Otras veces son argumentos estándar del campo, pero si no estás metido es muy difícil descubrir a qué se refieren. Si sigues con las mates ya lo irás viendo. En estas situaciones lo ideal sería preguntar a algún especialista en el campo, si tienes alguien a mano.

De todas maneras ya te digo, quizás hay una manera sencilla de ver directamente la cota, o quizás es un argumento bien conocido en el campo de la criptografía (campo que a mí me pilla muy lejos).

Me ha gustado mucho la demostración. Supongo que es algo habitual transformar problemas combinatorios complicados en otros más sencillos a través del uso de herramientas algebraicas, pero nunca dejará de fascinarme cuando en una demostración se realizan este tipo de transformaciones que casi de forma mágica lo simplifica todo.
Gracias por las respuestas 

A mí también me ha gustado mucho pensarlo, la verdad. Sí, el truco en muchos problemas combinatorios es intentar simplificarlo encontrando problemas combinatorios equivalentes hasta que salga algo que puedas contar con relativa facilidad.