Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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 bk .
Sia k=(kh-1 , … , k1 , k0 )2 l’espansione di k in base 2, cioè k=kh-12h-1+…+k12+k0 con kjє{0,1}.
Allora

b^k=b^{\sum _{ _{j=0 \dots h-1}}k_j2^j} \; = \; b^{\sum _{ _{k_j=1}}2^j} \; = \; \prod _{ _{k_j=1}}b^{2^j}
Per ogni j=0,…,h-1 si ponga b_j=b^{2^j}, sicché

b^k= \prod _{ _{k_j=1}}b_j

Metodo dei quadrati ripetuti

Primo step

Si calcolano tutti i bj :
(a) si pone b0 =b
(b) partendo da bj-1 si calcola bj =(bj-1 )2
Secondo step
(a)  si pone c0=1 se k0=0; si pone invece c0=b se k0=1
(b) partendo da cj-1 si calcola cj : si pone cj =cj-1 se kj =0; si pone invece cj =cj-1bj se kj =1.
Al termine di questo procedimento, si determina ch-1 =bk .
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 Zm

Prima di affrontare il problema del calcolo della complessità delle operazioni in Zm , è opportuno chiarire che eseguire un’operazione in Zm 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)
  2. calcolare [a]m[b]m ha complessità O((log m)2)
  3. stabilire se [b]m è invertibile e, in caso affermativo, calcolare [b]m-1 ha complessità O((log m)3).

Complessità delle operazioni in Zm

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)2).
Eseguire a∙b ha complessità O((log m)2), ed eseguire la divisione euclidea di a∙b per m ha complessità O((log (m2))(log m)) e quindi O((log m)2).
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)2).

Complessità delle operazioni in Zm

Dimostrazione
Si useranno le notazioni della prima slide, con b=[a]m .
Nel primo step, il calcolo di (bj-1 )2 ha complessità O((log m)2).
Dunque il calcolo di b0 ,…,bh-1 ha complessità O(h(log m)2) e quindi O ((log k)(log m)2).
Nel secondo step, il calcolo di cj-1bj ha complessità O((log m)2
Dunque il calcolo di c0 ,…,ch-1 ha complessità O(h(log m)2) e quindi O ((log k)(log m)2).

Complessità delle operazioni in Zp[x]

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

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

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

Complessità delle operazioni in Zp[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)3)
  • al più n2 moltiplicazioni tra elementi di Zp , per una complessità totale di O(n2 (log p)2)
  • al più n2 operazioni del tipo  [a]p-[b]p , per una complessità totale di O(n2 (log p)2).

Segue da quanto detto che la complessità totale dell’algoritmo è O(n2 (log p)3).

Complessità delle operazioni in Zp[x]

Proposizione 8.4 
Siano a(x) e b(x) polinomi non nulli appartenenti a Zp[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 pn)3)
  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 pn)3).
  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)=r0(x) , e siano

r1(x) , … , ri-2(x) , ri-1(x) , ri(x) , … , rt(x)=d(x)

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

gr(r1(x)) >  … > gr(ri-2(x)) > gr(ri-1(x)) > gr(ri(x)) > … > gr(rt(x))

Sicché t ≤n.

Complessità delle operazioni in Zp[x]

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

(ut(x), vt(x)) = (0,1)    e    (ui-1(x), vi-1(x)) = (vi(x), ui(x)-vi (x)qi (x))

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

Complessità delle operazioni in Zp[x]

Quindi si ha ut(x)=0 e vt(x)=1 che è un polinomio di grado 0.
Si supponga che per qualche j si abbia
(a) uj(x)=0 oppure gr(uj(x))≤gr(rj(x))
(b) vj(x)=0 oppure gr(vj(x))≤gr(rj-1(x))
Allora si ha:
(a) uj-1(x)=vj(x)⇒ uj-1(x)=0 oppure gr(uj-1(x))≤gr(rj-1(x))
(b) vj-1(x)=uj(x)-vj(x)qj(x) ⇒ vj-1(x)=0 oppure gr(vj-1(x))≤gr(rj(x)+rj-1(x)qj(x)) = gr(rj-2(x))
Dunque per ogni i≤t, si ha
(a) ui(x)=0 oppure gr(ui(x))≤gr(ri(x))
(b) vi(x)=0 oppure gr(vi(x))≤gr(ri-1(x)).
Dunque ciascuno dei due polinomi ui(x), vi(x) è nullo oppure ha grado ≤n.
D’altra parte, per ogni i≤t, il calcolo di  (ui-1(x), vi-1(x)) partendo da  (ui(x), vi(x)) consiste nel calcolare
ui(x)-vi (x)qi (x); dato che qi(x)=0 oppure gr(qi(x))≤n, ne segue che tale calcolo ha complessità O(n2 (log p)2).
Dunque determinare (u(x),v(x)) ha complessità O(n3(log p)2) e quindi O((log pn)3) .
(3) Poiché per ogni i, ciascuno dei due polinomi ui(x), vi(x) è nullo oppure ha grado ≤n, tale condizione è verificata da u(x)=u0(x) e da v(x)=v0(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)
(2) calcolare ab ha complessità O((log q)3)
(3) se b≠0, calcolare b-1 ha complessità O((log q)3)
(4) se se b≠0, calcolare ab-1 ha complessità O((log q)3)

Complessità delle operazioni in un campo finito

Dimostrazione
Si ponga q=pn (con p numero primo), e si supponga che F=Zp[x]/I, dove I è l’ideale generato da un polinomio f(x) irriducibile su Zp di grado n.
Allora a=a(x)+I e b=b(x)+I con a(x) e b(x) polinomi appartenenti a Zp[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)2) e quindi O((log q)2).
(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(n2 (log p)2); 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 p2n)3)=O((2log pn)3) e quindi O((log q)3).
(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)3); calcolare poi r(x) (cioè eseguire la divisione euclidea di u(x) per f(x) ha complessità O((log q)3), 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 bk, con bєF e k≥2, con il metodo dei quadrati ripetuti ha complessità O((log k)(log q)3).
Dimostrazione 
Si useranno le notazioni della prima slide.
Nel passo (1.ii), il calcolo di bj-12 ha complessità O((log q)3). Dunque il calcolo di b0 ,…,bh-1 ha complessità O(h (log q)3) e quindi O ((log k)(log q)3).
Nel passo (2.ii), il calcolo di cj-1bj ha complessità O((log q)3). Dunque il calcolo di c0 ,…,ch-1 ha complessità
O(h(log q)3) e quindi O ((log k)(log q)3).

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.
  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion