Algoritmo de curva elíptica de Lenstra

Question

Actualmente estoy tratando de entender el Algoritmo de la Curva Elíptica de Lenstra para la factorización de enteros. Como fuente utilizo "Rational Points on Elliptic Curves" de Joseph H. Silverman y John Tate.

Describen el algoritmo como sigue:

Tengo algunas preguntas sobre algunos de los pasos:

Al paso 1) : ¿Por qué el $gcd(n,6)$ sea $1$ ? ¿Y por qué no debería $n$ ser de la forma $m^r$ ?

Al paso 4) : ¿Por qué debe $gcd(4b^3 + 27c^2, n)=1$ ¿Retiene? He encontrado una frase en el artículo de Lenstra (H.W.Lenstra Jr. 'Facoting Integers with Elliptic Curves'), pero no veo por qué es cierta:

"si $6(4a^3+27b^2)\in (\mathbb{Z}/n\mathbb{Z})^*$ entonces $E$ se llama curva elíptica sobre $\mathbb{Z}/n\mathbb{Z}$ y en este caso $E(\mathbb{Z}/n\mathbb{Z})$ tiene una ley de grupo abeliano natural"

Al paso 6) : ¿Por qué es el punto $kP$ de la forma $(\frac{a_k}{d_k^2}, \frac{b_k}{d_k^3})$ ? Vi un Lemma que decía:

" $P=(x,y)\in E(\mathbb{Q})$ entonces $\exists e\in\mathbb{N}$ , $m,l\in\mathbb{Z}$ con $gcd(e,l)=gcd(e,m)=1$ y $x=(\frac{m}{e^2})$ , $y=(\frac{l}{e^3})$ ."

Pero aquí no tenemos información sobre $a_k, b_k$ y $d_k$ ¿lo hacemos?

Me encantaría que alguien me ayudara a entender este algoritmo.
Todo lo mejor, Luca

Answer 1

Voy a tratar de responder a esto yo mismo en la medida en que he entendido lo que sucede en el algoritmo.

Paso 1: Aquí debemos tener que $gcd(n,6)$ es $1$ para que podamos trabajar con la forma normal de Weierstraß que sólo funciona en característica no igual a $2$ o $3$ . Creo que la razón para $n$ no de la forma $m^r$ es la eficiencia. La prueba de tomar la raíz cuadrada o $n^\frac{1}{r}$ es más rápido que pasar por todo el algoritmo.

Paso 4: Aquí necesitamos $gcd(4b^3+27c^2,n)$ sea 1 para que $n$ y el discriminante de la curva no tienen factores comunes. Entonces, reduciendo la curva módulo $p$ si lo encontramos, tendremos una curva no sinular.

Paso 6: Calculamos $kP$ en $\mathbb{Z}/n\mathbb{Z}$ (cómo lo hacemos se explica más adelante e incluye algunos casos, ya que debemos ver que podemos calcular el $\lambda$ en la fórmula de sumar puntos, ya que el denominador podría no tener un inverso en $\mathbb{Z}/n\mathbb{Z}$ ). Así que las coordenadas de $kP$ son números racionales. Y ahí tenemos un lema en Silverman:
Si $P=(X,Y)\in E(\mathbb{Q})$ entonces $\exists e\in\mathbb{N}$ y $m,n\in\mathbb{Z}$ con $gcd(e,n)=gcd(e,m)=1$ y $X=\frac{m}{e^2}$ y $Y=\frac{m}{e^3}$ .
Así que podemos escribir $kP$ de esta forma. Hacemos esto para ver en el paso 7 si hemos encontrado nuestro factor no trivial de n, o si tenemos que empezar de nuevo.
Tenga en cuenta que queremos $kP$ para ser el punto en el infinito. Si nuestro punto elegido $P=(x_1,y_1)$ tiene un orden infinito, y obtenemos $kP$ es este punto en el infinito, entonces debe haber un factor primario $p$ de $n$ , de tal manera que $E(\mathbb{F}_p)$ divide a k. Entonces los puntos de $E(\mathbb{F}_p)$ tienen orden de dividir $k$ . Y por lo tanto, si $kP$ es el punto en el infinito entonces $p$ divide el denominador de las coordenadas de $kP$ Por lo tanto $d_k$ .

Espero que esto no haya sido escrito de forma demasiado caótica y pueda ayudar a alguien más.
Si hay fallos en mi explicación, ¡escriba un comentario!