Elliptic Curve Method

[peppespe]

L'Elliptic Curve Method è un algoritmo probabilistico di fattorizzazione ideato da Lenstra nel 1985. Come si evince dal nome questi fa uso di Curve Ellittiche su campi finiti.
Originariamente tale algoritmo era stato implementato su una sola fase, poi successivi miglioramenti hanno aggiunto una seconda fase sulla quale ho dei dubbi!
Spiego brevemente le fasi dell'algoritmo: Sia n=pq un numero da fattorizzare t.c. ad esempio p è dell'ordine di 15-20 cifre mentre q è dell'ordine di 80 cifre, allora:

_______________________________________________
Precalcolo:

- scelgo un bound B1 ed un secondo boud B2 = 100B1

Es. banale : B1 = 10 e B2 = 100

- determino tutti i numeri primi nell'intervallo [B1,B2] e contemporaneamente ne determino le distanze, in modo date da ottenerne un insieme.

Es.
1) prime = 11 distanza = 0
2) prime = 13 distanza = 2
3) prime = 17 distanza = 4
4) prime = 19 distanza = 2
5) prime = 23 distanza = 4
6) prime = 29 distanza = 6
7) prime = 31 distanza = 2
8) prime = 37 distanza = 6
9) prime = 41 distanza = 4
10) prime = 43 distanza = 2
11) prime = 47 distanza = 4
12) prime = 53 distanza = 6
13) prime = 59 distanza = 6
14) prime = 61 distanza = 2
15) prime = 67 distanza = 6
16) prime = 71 distanza = 4
17) prime = 73 distanza = 2
18) prime = 79 distanza = 6
19) prime = 83 distanza = 4
20) prime = 89 distanza = 6
21) prime = 97 distanza = 8

distanze :
delta[0] = 2
delta[1] = 4
delta[2] = 6
delta[3] = 8
#distanze = 4
MAX distanza = 8

_______________________________________________
I Fase:

- scelgo un punto casuale a coordinate proiettive P(X/Z, Y/Z, 1) (mod n)
- scelgo una curva y^2 = x^3 + ax + b, t.c. a,b(mod n) la quale passa per il punto P
- calcolo un fattore k t.c. è prodotto di ogni primo elevato alla potenza massima, t.c. questi sia minore di B1

Es. k = 2^3 * 3^2 * 5 * 7 = 2520

si effettua tale operazione con la speranza di aver approssimato al meglio l'ordine della curva (il quale ovviamente non conosciamo), per cui ricordo dalla teoria dei gruppi che vale la seguente relazione :

[#E(F)]=O=(0,1,0)

ove O è il punto all'infinito.

- calcolo il punto [k]P e poiché stiamo lavorando all'interno di un anello Z[n] ed non in un campo F spero che durante tale calcolo ( P+P+P+....) si verifichi un'operazione "illegale" , come ad esempio l'impossibilità di determinare l'elemento d^(-1) , quindi gcd(n,d)=g è il fattore primo che cercavamo.


_______________________________________________
II Fase:

- spesso l'operazione [k]P va a buon fine e quindi restituisce un punto finito Q diverso dal punto all'infinito. Ciò potrebbe essere scaturito dal fatto che #E(F

)>[k], quindi potremmo immaginare che esista un secondo fattore primo q da moltiplicare allo scalare [k]

Es. #E(F

) = q*[k]

dove q è un primo maggiore di B1.

ORA SORGE IL DUBBIO: tutti gli articoli che sono andato a leggere ( come da esempio http://www.hyperelliptic.org/tanja/SHAR ... 06/Gaj.pdf , http://www.loria.fr/~zimmerma/papers/ecm-entry.pdf, ... ) mi invitano ad eseguire i seguenti passi:

- precalcolare i punti R = deltaQ, t.c. delta è il vettore "piccolo" delle differenze calcolato in sede di "precalcolo" e Q è il punto finito risultato dell'operazione [k]P svolta nella prima fase.

Es.
R[0] = 2Q
R[1] = 4Q
R[2] = 6Q
R[3] = 8Q

- per ogni primo compreso nell'intervallo [B1,B2] devo calcolare devo svolgere le seguenti somme sulla curva ellittica:

q[1]Q ---> 11Q
q[1]Q + RQ t.c. R è un opportuno valore già calcolato al punto precedente il quale se sommato a q[1] mi restituisce il numero primo successivo a q[1], ovvero q[2]=13
...
q[i+1]Q = qQ+RQ

in tal proposito vi chiedo:

1. conti alla mano, R è in realtà un punto sulla retta, qual'è il criterio di scelta tra i vari R in modo tale che se sommati con qQ mi siano l'elemento primo successivo o meglio il punto all'infinito?

2. il prof. asserisce senza entrare molto nel dettaglio che in sede di precalcolo non c'è bisogno di memorizzare tutti i numeri primi nell'intervallo [B1,B2], ma basta memorizzare solo l'elemento primo successivo a B1, indicato con [1], e la lista delle differenze delta. Lui asserisce che partendo da q[0] e sommandolo opportunamente con le differenze delta otteniamo tutti i primi in [B1, B2], e che per verifica possiamo sommare tutti i valori delta impiegati nelle somme qQ+RQ in modo tale da ottenere il penultimo numero primo presente nella lista di primi compresi in [B1, B2]. A tal proposito come posso scegliere ad hoc il valore delta in modo tale che q[1]+delta sia il numero primo successivo?

- se anche queste somme non forniscono alcun risultato utile ai fini della fattorizzazione ritorniamo alla prima fase.

[Lord K]

Dapprima non è possibile determinare mediante quei $delta_i$ il primo successivo.

Io ti posto il metodo che è stato a me insegnato nello studio delle curve ellittiche e che ha una sostanziale differenza, ovvero la mancanza di quei primi...

- Step 0 -

Sia $n>=2$ un intero composito del quale dobbiamo cercare la fattorizzazione.

- Step 1 -

Verifichiamo che $gcd(n,6)=1$ e che $n$ non abbia la forma $m^r$ per qualche $r>=2$

- Step 2 -

Scegliamo $3$ interi, $b,x_1,y_1$ tra $1$ e $n$.

- Step 3 -

Sia $c=y_1^2-x_1^3-bx_1 (mod n)$ e sia $C$ al curva:

$C:$ $y^2=x^3+bx+c$ con $P=(x_1,y_1) in C$

- Step 4 -

Verificare che $gcd(4b^3+27c^3,n)=1$. Se così non è si torna al passo $2$ scegliendo un nuovo $b$.

- Step 5 -

Scelgo un numero $k$ che è il prodotto di numeri primi "piccoli" in potenza "piccola", per esempio:

$k=lcm(1,2,3,...,K)$

per qualche $K$.

- Step 6 -

Calcolare:

$kP=((a_k)/(d_k)^2, (b_k)/(d_k)^3)$

- Step 7 -

Calcolare $D=gcd(d_k, n)$

-Se $1 -Se $D=1$ allora ritorno al passo $5$ ed incremento $k$, oppure torno al passo $2$ e scelgo una altra curva.
-Se $D=n$ allora ritorno al passo $5$ e decremento $k$.

Osservazioni

Il tutto funziona perchè se siamo così fortunati da trovare una curva $C$ ed un $k$ tale che, per qualche primo $p$ che divide $n$, abbiamo $text{#}\hat C(F_p)$ divide $k$. Quindi ogni elemento di $\hat C(F_p)$ ha un ordine che divide $k$, quindi in particolare se prendiamo il punto $Q in C(QQ)$ e lo riduciamo modulo $p$ sappiamo che:

$\hat (kP)=k \hatP=\hat O$

In altre parole se la riduzione di $kP$ modulo $p$ è il punto $O$ all'infinito, allora dobbiamo avere che $p|d_k$, ovvero $p|gcd(d_k,n)$.

Spero di essere stato almeno un poco chiaro...

[peppespe]

"Lord K":Dapprima non è possibile determinare mediante quei $delta_i$ il primo successivo.

Io ti posto il metodo che è stato a me insegnato nello studio delle curve ellittiche e che ha una sostanziale differenza, ovvero la mancanza di quei primi...

- Step 0 -

Sia $n>=2$ un intero composito del quale dobbiamo cercare la fattorizzazione.

- Step 1 -

Verifichiamo che $gcd(n,6)=1$ e che $n$ non abbia la forma $m^r$ per qualche $r>=2$

- Step 2 -

Scegliamo $3$ interi, $b,x_1,y_1$ tra $1$ e $n$.

- Step 3 -

Sia $c=y_1^2-x_1^3-bx_1 (mod n)$ e sia $C$ al curva:

$C:$ $y^2=x^3+bx+c$ con $P=(x_1,y_1) in C$

- Step 4 -

Verificare che $gcd(4b^3+27c^3,n)=1$. Se così non è si torna al passo $2$ scegliendo un nuovo $b$.

- Step 5 -

Scelgo un numero $k$ che è il prodotto di numeri primi "piccoli" in potenza "piccola", per esempio:

$k=lcm(1,2,3,...,K)$

per qualche $K$.

- Step 6 -

Calcolare:

$kP=((a_k)/(d_k)^2, (b_k)/(d_k)^3)$

Cosa sono i termini (d_k) ??

- Step 7 -

Calcolare $D=gcd(d_k, n)$

-Se $1 -Se $D=1$ allora ritorno al passo $5$ ed incremento $k$, oppure torno al passo $2$ e scelgo una altra curva.
-Se $D=n$ allora ritorno al passo $5$ e decremento $k$.

Osservazioni

Il tutto funziona perchè se siamo così fortunati da trovare una curva $C$ ed un $k$ tale che, per qualche primo $p$ che divide $n$, abbiamo $text{#}\hat C(F_p)$ divide $k$. Quindi ogni elemento di $\hat C(F_p)$ ha un ordine che divide $k$, quindi in particolare se prendiamo il punto $Q in C(QQ)$ e lo riduciamo modulo $p$ sappiamo che:

$\hat (kP)=k \hatP=\hat O$

In altre parole se la riduzione di $kP$ modulo $p$ è il punto $O$ all'infinito, allora dobbiamo avere che $p|d_k$, ovvero $p|gcd(d_k,n)$.

Spero di essere stato almeno un poco chiaro...

[Lord K]

Avevo copiato quanto era sui miei appunti, se preferisci puoi sostituire il tutto con il modo seguente, visto che è querllo che si usa solitamente.

6 Step)

L'obiettivo è calcolare $kP (modn)$. Anzichè procedere con il calcolo diretto $P+P+...+P$ scriviamo $k$ come sviluppo binario, ovvero:

$k=k_0+2*k_1+...k_r*2^r$

dove ovviamente $r
$P_0=P$
$P_1=2P_0=2P$
$P_2=2P_1=2^2P$

etc... etc...

$P_r=2P_(r-1)=2^rP$

e finalmente:

$kP= sum_(k_i=1) P_i$

questo ci fa guadagnare in tempi di computazione, infatti ci sono $2log_2k$ passi di duplicazione e addizione.

[peppespe]

Sono riuscito ad implementare l'algoritmo, chiunque fosse interessato potra consultare il mio articolo http://www.giuseppespecchio.it/?p=147.