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
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
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