Maria De Falco » 8.Complessità delle operazioni nell'anello degli interi modulo m, nei campi finiti e nelle curve ellittiche

Metodo dei quadrati ripetuti

Si illustrerà ora un metodo rapido per il calcolo delle potenze in un semigruppo commutativo unitario
Metodo dei quadrati ripetuti
Sia (S, ∙) unsemigruppo commutativo unitario (denotato moltiplicativamente).
Sia b un elemento di S, e sia k un numero naturale tale che k≥2. Si calcolerà ora b^k .
Sia k=(k_h-1 , … , k₁ , k₀ )₂ l’espansione di k in base 2, cioè k=k_h-12^h-1+…+k₁2+k₀ con k_jє{0,1}.
Allora

Per ogni j=0,…,h-1 si ponga , sicché

Metodo dei quadrati ripetuti

Primo step

Si calcolano tutti i b_j :
(a) si pone b₀ =b
(b) partendo da b_j-1 si calcola b_j =(b_j-1 )²
Secondo step
(a)  si pone c₀=1 se k₀=0; si pone invece c₀=b se k₀=1
(b) partendo da c_j-1 si calcola c_j : si pone c_j =c_j-1 se k_j =0; si pone invece c_j =c_j-1b_j se k_j =1.
Al termine di questo procedimento, si determina c_h-1 =b^k .
Se il semigruppo è denotato additivamente, si ottiene, con lo stesso procedimento e le ovvie variazioni di notazione, il metodo dei doppi ripetuti per il calcolo dei multipli degli elementi del semigruppo secondo numeri naturali ≥2.

Complessità delle operazioni in Z_m

Prima di affrontare il problema del calcolo della complessità delle operazioni in Z_m , è opportuno chiarire che eseguire un’operazione in Z_m significa non solo individuare la classe ξ che costituisce il risultato dell’operazione, ma anche individuarne il suo “rappresentante canonico”, cioè il numero s tale che

ξ=[s]_m e 0≤s≤m-1

Proposizione 8.1 
Sia m un numero intero tale che m>1.
Siano a e b numeri interi tali che 0≤a,b≤m-1. Allora

1. calcolare [a]_m+[b]_m ha complessità O((log m)²)
2. calcolare [a]_m[b]_m ha complessità O((log m)²)
3. stabilire se [b]_m è invertibile e, in caso affermativo, calcolare [b]_m^-1 ha complessità O((log m)³).

Complessità delle operazioni in Z_m

Dimostrazione 
Eseguire a+b ha complessità O(log m), ed eseguire la divisione euclidea di a+b per m ha complessità O((log 2m)(log m)) e quindi O((log m)²).
Eseguire a∙b ha complessità O((log m)²), ed eseguire la divisione euclidea di a∙b per m ha complessità O((log (m²))(log m)) e quindi O((log m)²).
Il punto (3) segue dal Teorema 2.4 e dal Teorema 3.2.
Proposizione 8.2
Sia m un numero intero tale che m>1.
Se a è un numero intero tale che 0≤a≤m-1, e k è un numero naturale maggiore di 1, allora il calcolo di ([a]_m)^k , con il metodo dei quadrati ripetuti ha complessità O ((log k)(log m)²).

Complessità delle operazioni in Z_m

Dimostrazione
Si useranno le notazioni della prima slide, con b=[a]_m .
Nel primo step, il calcolo di (b_j-1 )² ha complessità O((log m)²).
Dunque il calcolo di b₀ ,…,b_h-1 ha complessità O(h(log m)²) e quindi O ((log k)(log m)²).
Nel secondo step, il calcolo di c_j-1b_j ha complessità O((log m)²
Dunque il calcolo di c₀ ,…,c_h-1 ha complessità O(h(log m)²) e quindi O ((log k)(log m)²).

Complessità delle operazioni in Z_p[x]

Proposizione 8.3
Sia p un numero primo positivo e siano f(x) e g(x) polinomi non nulli appartenenti a Z_p[x] di grado al più n. Allora:

1. calcolare f(x)+g(x) ha complessità O(n (log p)²)
2. calcolare f(x)g(x) ha complessità O(n² (log p)²)
3. calcolare quoziente e resto della divisione euclidea di g(x) per f(x) ha complessità  O(n² (log p)³) e quindi O((log pⁿ)³).

Dimostrazione 
Per calcolare f(x)+g(x) si eseguono al più n somme di elementi di Z_p per una complessità totale di O(n (log p)²).
Per calcolare f(x)g(x) si eseguono al più n² prodotti e al più n² somme di elementi di Z_p per una complessità totale di O(n² (log p)²).

Complessità delle operazioni in Z_p[x]

Per calcolare quoziente e resto, si eseguono:

• al più n operazioni del tipo [a]_p[b]_p^-1, per una complessità totale di O(n (log p)³)
• al più n² moltiplicazioni tra elementi di Z_p , per una complessità totale di O(n² (log p)²)
• al più n² operazioni del tipo  [a]_p-[b]_p , per una complessità totale di O(n² (log p)²).

Segue da quanto detto che la complessità totale dell’algoritmo è O(n² (log p)³).

Complessità delle operazioni in Z_p[x]

Proposizione 8.4 
Siano a(x) e b(x) polinomi non nulli appartenenti a Z_p[x] di grado ≤n. Allora:

1. Determinare un massimo comun divisore d(x) di a(x) e b(x) con l’algoritmo delle divisioni successive ha complessità O((log pⁿ)³)
2. Determinare u(x) e v(x) tali che d(x)=a(x)u(x)+b(x)v(x) con l’algoritmo delle divisioni successive ha complessità O((log pⁿ)³).
3. Ciascuno dei polinomi u(x) e v(x) è nullo oppure ha grado ≤n.

Dimostrazione 
Si ponga a(x)= r_-1(x) e b(x)=r₀(x) , e siano

r₁(x) , … , r_i-2(x) , r_i-1(x) , r_i(x) , … , r_t(x)=d(x)

i resti non nulli ottenuti con l’algoritmo delle divisioni successive.
Si può supporre che sia t ≥1.
Si ha

gr(r₁(x)) >  … > gr(r_i-2(x)) > gr(r_i-1(x)) > gr(r_i(x)) > … > gr(r_t(x))

Sicché t ≤n.

Complessità delle operazioni in Z_p[x]

(1) Per determinare d(x) si eseguono O(n) divisioni euclidee ciascuna delle quali ha complessità O(n² (log p)³)
⇒  la complessità totale è O(n³ (log p)³)=O((n log p)³)=O((log pⁿ)³).
(2) Si ricordi che che per ogni i tale che 1≤i≤t, vale la seguente relazione:
r_i-2(x) = r_i-1(x)q_i(x) + r_i(x)
Si ricordi che per determinare la coppia (u(x),v(x)), si pone

(u_t(x), v_t(x)) = (0,1)    e    (u_i-1(x), v_i-1(x)) = (v_i(x), u_i(x)-v_i (x)q_i (x))

La coppia (u(x),v(x)) cercata è la coppia (u₀(x), v₀(x)) che si ottiene alla fine di questo processo.
Si noti che per ogni i≤t tale che -1≤i≤t, ciascuno dei polinomi q_i(x) e r_i(x)è nullo oppure ha grado ≤n.

Complessità delle operazioni in Z_p[x]

Quindi si ha u_t(x)=0 e v_t(x)=1 che è un polinomio di grado 0.
Si supponga che per qualche j si abbia
(a) u_j(x)=0 oppure gr(u_j(x))≤gr(r_j(x))
(b) v_j(x)=0 oppure gr(v_j(x))≤gr(r_j-1(x))
Allora si ha:
(a) u_j-1(x)=v_j(x)⇒ u_j-1(x)=0 oppure gr(u_j-1(x))≤gr(r_j-1(x))
(b) v_j-1(x)=u_j(x)-v_j(x)q_j(x) ⇒ v_j-1(x)=0 oppure gr(v_j-1(x))≤gr(r_j(x)+r_j-1(x)q_j(x)) = gr(r_j-2(x))
Dunque per ogni i≤t, si ha
(a) u_i(x)=0 oppure gr(u_i(x))≤gr(r_i(x))
(b) v_i(x)=0 oppure gr(v_i(x))≤gr(r_i-1(x)).
Dunque ciascuno dei due polinomi u_i(x), v_i(x) è nullo oppure ha grado ≤n.
D’altra parte, per ogni i≤t, il calcolo di  (u_i-1(x), v_i-1(x)) partendo da  (u_i(x), v_i(x)) consiste nel calcolare
u_i(x)-v_i (x)q_i (x); dato che q_i(x)=0 oppure gr(q_i(x))≤n, ne segue che tale calcolo ha complessità O(n² (log p)²).
Dunque determinare (u(x),v(x)) ha complessità O(n³(log p)²) e quindi O((log pⁿ)³) .
(3) Poiché per ogni i, ciascuno dei due polinomi u_i(x), v_i(x) è nullo oppure ha grado ≤n, tale condizione è verificata da u(x)=u₀(x) e da v(x)=v₀(x).

Complessità delle operazioni in un campo finito

Proposizione 8.5 
Sia F un campo finito di ordine q, e siano a,b elementi di F. Allora:
(1) calcolare a+b ha complessità O((log q)²)
(2) calcolare ab ha complessità O((log q)³)
(3) se b≠0, calcolare b^-1 ha complessità O((log q)³)
(4) se se b≠0, calcolare ab^-1 ha complessità O((log q)³)

Complessità delle operazioni in un campo finito

Dimostrazione
Si ponga q=pⁿ (con p numero primo), e si supponga che F=Z_p[x]/I, dove I è l’ideale generato da un polinomio f(x) irriducibile su Z_p di grado n.
Allora a=a(x)+I e b=b(x)+I con a(x) e b(x) polinomi appartenenti a Z_p[x] ciascuno dei quali è nullo oppure ha grado minore di n. Si utilizzeranno ora i risultati esposti nella Proposizione 8.3 e nella Proposizione 8.4.
(1) a+b= (a(x)+b(x))+I (si noti che a(x)+b(x) è nullo oppure ha grado minore di n). Calcolare a(x)+b(x) ha complessità O(n (log p)²) e quindi O((log q)²).
(2) ab= (a(x)b(x))+I=r(x)+I, dove r(x) è il resto della divisione euclidea di a(x)b(x) per f(x). Calcolare a(x)b(x) ha complessità O(n² (log p)²); dato che a(x)b(x) è nullo oppure ha grado ≤2n, calcolare poi r(x) (cioè eseguire la divisione euclidea di a(x)b(x) per f(x) ha complessità O((log p²ⁿ)³)=O((2log pⁿ)³) e quindi O((log q)³).
(3) b^-1=(b(x)+I)^-1=u(x)+I=r(x)+I, dove u(x) è un polinomio tale che [1]_p =u(x)g(x)+v(x)f(x) e r(x) è il resto della divisione euclidea di u(x) per f(x). Calcolare u(x) ha complessità O((log q)³); calcolare poi r(x) (cioè eseguire la divisione euclidea di u(x) per f(x) ha complessità O((log q)³), perché u(x) è nullo oppure ha grado ≤n.
(4) segue da (2) e (3).

Complessità delle operazioni in un campo finito

Proposizione 8.6 
Sia F un campo finito di ordine q.
Il calcolo di b^k, con bєF e k≥2, con il metodo dei quadrati ripetuti ha complessità O((log k)(log q)³).
Dimostrazione 
Si useranno le notazioni della prima slide.
Nel passo (1.ii), il calcolo di b_j-1² ha complessità O((log q)³). Dunque il calcolo di b₀ ,…,b_h-1 ha complessità O(h (log q)³) e quindi O ((log k)(log q)³).
Nel passo (2.ii), il calcolo di c_j-1b_j ha complessità O((log q)³). Dunque il calcolo di c₀ ,…,c_h-1 ha complessità
O(h(log q)³) e quindi O ((log k)(log q)³).

Complessità delle operazioni in una curva ellittica

La seguente proposizione è una ovvia conseguenza della Proposizione 8.6 e della di come è definita l’operazione di somma in una curva ellittica.
Proposizione 8.7
Sia F un campo finito, e sia E una curva ellittica su F. Allora:

1. Se F è finito di ordine q, il calcolo della somma di due elementi di E ha complessità polinomiale rispetto all’input q.
2. Se F è finito di ordine q, il calcolo di kP, con PєE e k≥2, con il metodo dei doppi ripetuti ha complessità polinomiale rispetto agli input k e q.