Esponenziazione rapida con le
catene di addizione/sottrazione
Ottavio G. Rizzo
http://www.mat.unimi.it/~otto
Università di Milano
Parma, 14 novembre 2003 – p.1/28
Addizioni
Sia E un monoide additivo e supponiamo di voler
calcolare 12P dove P ∈ E.
Parma, 14 novembre 2003 – p.2/28
Addizioni
Sia E un monoide additivo e supponiamo di voler
calcolare 12P dove P ∈ E. Il metodo più ovvio è
calcolare
12P = P
{z· · · + P}
| +P+
12 volte
Parma, 14 novembre 2003 – p.2/28
Addizioni
Sia E un monoide additivo e supponiamo di voler
calcolare 12P dove P ∈ E. Il metodo più ovvio è
calcolare
12P = P
{z· · · + P}
| +P+
12 volte
È chiaro, però, che undici addizioni sono troppe:
possiamo ad esempio calcolare
12P =
P
Parma, 14 novembre 2003 – p.2/28
Addizioni
Sia E un monoide additivo e supponiamo di voler
calcolare 12P dove P ∈ E. Il metodo più ovvio è
calcolare
12P = P
{z· · · + P}
| +P+
12 volte
È chiaro, però, che undici addizioni sono troppe:
possiamo ad esempio calcolare
12P =
2P
Parma, 14 novembre 2003 – p.2/28
Addizioni
Sia E un monoide additivo e supponiamo di voler
calcolare 12P dove P ∈ E. Il metodo più ovvio è
calcolare
12P = P
{z· · · + P}
| +P+
12 volte
È chiaro, però, che undici addizioni sono troppe:
possiamo ad esempio calcolare
12P =
2P + P
Parma, 14 novembre 2003 – p.2/28
Addizioni
Sia E un monoide additivo e supponiamo di voler
calcolare 12P dove P ∈ E. Il metodo più ovvio è
calcolare
12P = P
{z· · · + P}
| +P+
12 volte
È chiaro, però, che undici addizioni sono troppe:
possiamo ad esempio calcolare
12P =
2(2P + P)
Parma, 14 novembre 2003 – p.2/28
Addizioni
Sia E un monoide additivo e supponiamo di voler
calcolare 12P dove P ∈ E. Il metodo più ovvio è
calcolare
12P = P
{z· · · + P}
| +P+
12 volte
È chiaro, però, che undici addizioni sono troppe:
possiamo ad esempio calcolare
¡
¢
12P = 2 2(2P + P)
con solo tre raddoppi ed un’addizione.
Parma, 14 novembre 2003 – p.2/28
Somma e raddoppia
Questo metodo di moltiplicazione si chiama somma
e raddoppia.
Parma, 14 novembre 2003 – p.3/28
Somma e raddoppia
Questo metodo di moltiplicazione si chiama somma
e raddoppia.
poni n = (nλ nλ−1 · · · n0 )2 , Q = P
mentre i = (λ − 1) . . . 0:
poni Q = 2Q
se ni = 1: poni Q = Q + P
Parma, 14 novembre 2003 – p.3/28
Somma e raddoppia
Questo metodo di moltiplicazione si chiama somma
e raddoppia.
poni n = (nλ nλ−1 · · · n0 )2 , Q = P
mentre i = (λ − 1) . . . 0:
poni Q = 2Q
se ni = 1: poni Q = Q + P
Ad esempio: se n = 12 = 11002
1
Q=P
1
Q = 2P
Q = 3P
0
Q = 6P
0
Q = 12P
Parma, 14 novembre 2003 – p.3/28
Somma e raddoppia: analisi I
Dato n = (nλ · · · n0 )2 con nλ = 1 poniamo:
λ(n) = blog2 (n)c, la lunghezza di n
w(n) = #{ni = 1}, il peso di Hamming di n
Parma, 14 novembre 2003 – p.4/28
Somma e raddoppia: analisi I
Dato n = (nλ · · · n0 )2 con nλ = 1 poniamo:
λ(n) = blog2 (n)c, la lunghezza di n
w(n) = #{ni = 1}, il peso di Hamming di n
Se R è il costo di un raddoppio ed S quello di una
somma, il costo totale è
c(n) = cR (n)R + cS (n)S
dove
cR (n) = λ(n),
cS (n) = w(n) − 1
Parma, 14 novembre 2003 – p.4/28
Somma e raddoppia: analisi II
Poniamo
−e P2e −1
C(e) = 2
n=0 c(n)
1−e P2e −1
C (e) = 2
c(n) = 2C(e) − C(e − 1)
n=2e−1
analogamente per CR , CR0 , CS e CS0 .
0
e
Parma, 14 novembre 2003 – p.5/28
Somma e raddoppia: analisi II
Poniamo
−e P2e −1
C(e) = 2
n=0 c(n)
1−e P2e −1
C (e) = 2
c(n) = 2C(e) − C(e − 1)
n=2e−1
analogamente per CR , CR0 , CS e CS0 . Chiaramente
0
e
CR0 (e) = e − 1
Parma, 14 novembre 2003 – p.5/28
Somma e raddoppia: analisi II
Poniamo
−e P2e −1
C(e) = 2
n=0 c(n)
1−e P2e −1
C (e) = 2
c(n) = 2C(e) − C(e − 1)
n=2e−1
analogamente per CR , CR0 , CS e CS0 . Chiaramente
0
e
CR0 (e) = e − 1
mentre
X i
1 e−1
1
CR (e) = e
i 2 = e − 2 + e−1
2 i =1
2
Parma, 14 novembre 2003 – p.5/28
Somma e raddoppia: analisi III
Se λ(n) = e − 1, scriviamo n = 2e−1 + n 0 con
λ(n 0 ) < e − 1.
Parma, 14 novembre 2003 – p.6/28
Somma e raddoppia: analisi III
Se λ(n) = e − 1, scriviamo n = 2e−1 + n 0 con
λ(n 0 ) < e − 1. Quindi cS (2e−1 ) = 0 mentre
cS (n) = 1 + cS (n 0 ) se n 0 6= 0.
Parma, 14 novembre 2003 – p.6/28
Somma e raddoppia: analisi III
Se λ(n) = e − 1, scriviamo n = 2e−1 + n 0 con
λ(n 0 ) < e − 1. Quindi cS (2e−1 ) = 0 mentre
cS (n) = 1 + cS (n 0 ) se n 0 6= 0. Segue che
1
CS (e) = CS (e − 1) + ,
2
C(2) = 0
Parma, 14 novembre 2003 – p.6/28
Somma e raddoppia: analisi III
Se λ(n) = e − 1, scriviamo n = 2e−1 + n 0 con
λ(n 0 ) < e − 1. Quindi cS (2e−1 ) = 0 mentre
cS (n) = 1 + cS (n 0 ) se n 0 6= 0. Segue che
1
CS (e) = CS (e − 1) + ,
2
C(2) = 0
Svolgendo la definizione ricorsiva:
e
CS (e) = − 1,
2
CS0 (e) =
e −1
2
Parma, 14 novembre 2003 – p.6/28
Somma e raddoppia: analisi IV
Infine:
e −1
S
C (e) = (e − 1)R +
2
0
Parma, 14 novembre 2003 – p.7/28
Somma e raddoppia: analisi IV
Infine:
e −1
S
C (e) = (e − 1)R +
2
0
Il costo dei raddoppi (e − 1)R è ineliminabile
Parma, 14 novembre 2003 – p.7/28
Somma e raddoppia: analisi IV
Infine:
e −1
S
C (e) = (e − 1)R +
2
0
Il costo dei raddoppi (e − 1)R è ineliminabile
e −1
S è migliorabile
Il costo delle somme
2
Parma, 14 novembre 2003 – p.7/28
Catene di addizione
Parma, 14 novembre 2003 – p.8/28
Catene di addizione
Una catena d’addizione per n ∈ N è: a0 , a1 , . . . , a`
dove a0 = 1, a` = n e, se i ≥ 1, ai = a j + ak con j , k < i
Parma, 14 novembre 2003 – p.9/28
Catene di addizione
Una catena d’addizione per n ∈ N è: a0 , a1 , . . . , a`
dove a0 = 1, a` = n e, se i ≥ 1, ai = a j + ak con j , k < i
Ad esempio: 1, 2 = 1 + 1, 3 = 2 + 1, 6 = 3 + 3, 12 = 6 + 6
Parma, 14 novembre 2003 – p.9/28
Catene di addizione
Una catena d’addizione per n ∈ N è: a0 , a1 , . . . , a`
dove a0 = 1, a` = n e, se i ≥ 1, ai = a j + ak con j , k < i
Ad esempio: 1, 2 = 1 + 1, 3 = 2 + 1, 6 = 3 + 3, 12 = 6 + 6
Per motivi pratici, c’interessano catene di addizioni
in cui, fissato J ⊂ Z finito (precalcoli)
(
2ai −1
raddoppi
ai =
ai −1 + a j , j ∈ J somme
Parma, 14 novembre 2003 – p.9/28
Catene di addizione
Una catena d’addizione per n ∈ N è: a0 , a1 , . . . , a`
dove a0 = 1, a` = n e, se i ≥ 1, ai = a j + ak con j , k < i
Ad esempio: 1, 2 = 1 + 1, 3 = 2 + 1, 6 = 3 + 3, 12 = 6 + 6
Per motivi pratici, c’interessano catene di addizioni
in cui, fissato J ⊂ Z finito (precalcoli)
(
2ai −1
raddoppi
ai =
ai −1 + a j , j ∈ J somme
«Somma e raddoppia» è una catena d’addizione con
J = {1}: cioè nessun precalcolo.
Parma, 14 novembre 2003 – p.9/28
Lunghezza delle catene
Dato n, vogliamo trovare una catena 1, a1 , . . . , a` = n
di lunghezza minima `(n).
Parma, 14 novembre 2003 – p.10/28
Lunghezza delle catene
Dato n, vogliamo trovare una catena 1, a1 , . . . , a` = n
di lunghezza minima `(n). Abbiamo:
ai ≤ 2i , quindi `(n) ≥ λ(n)
Parma, 14 novembre 2003 – p.10/28
Lunghezza delle catene
Dato n, vogliamo trovare una catena 1, a1 , . . . , a` = n
di lunghezza minima `(n). Abbiamo:
ai ≤ 2i , quindi `(n) ≥ λ(n)
`(n) ≤ λ(n) + w(n) − 1: somma e raddoppia
Parma, 14 novembre 2003 – p.10/28
Lunghezza delle catene
Dato n, vogliamo trovare una catena 1, a1 , . . . , a` = n
di lunghezza minima `(n). Abbiamo:
ai ≤ 2i , quindi `(n) ≥ λ(n)
`(n) ≤ λ(n) + w(n) − 1: somma e raddoppia
`(n)
=1
[Brauer, ’39] lim
n→∞ λ(n)
Parma, 14 novembre 2003 – p.10/28
Lunghezza delle catene
Dato n, vogliamo trovare una catena 1, a1 , . . . , a` = n
di lunghezza minima `(n). Abbiamo:
ai ≤ 2i , quindi `(n) ≥ λ(n)
`(n) ≤ λ(n) + w(n) − 1: somma e raddoppia
`(n)
=1
[Brauer, ’39] lim
n→∞ λ(n)
[Erdős, ’60] Per quasi ogni n,
λ(n)
¢
`(n) è asintotica a λ(n) + ¡
λ λ(n)
Parma, 14 novembre 2003 – p.10/28
Catene in pratica
Applicazioni pratiche:
Fattorizzazione su N
Crittografia
Parma, 14 novembre 2003 – p.11/28
Catene in pratica
Applicazioni pratiche:
Fattorizzazione su N
Crittografia
Monoide:
Campi finiti
Curve ellittiche
Parma, 14 novembre 2003 – p.11/28
Catene in pratica
Applicazioni pratiche:
Fattorizzazione su N
Crittografia
Monoide:
Campi finiti
Curve ellittiche
Hardware:
Calcolatori
Smart card
Parma, 14 novembre 2003 – p.11/28
Catene in pratica
Applicazioni pratiche:
Fattorizzazione su N
Crittografia
Monoide:
Campi finiti
Curve ellittiche
Hardware:
Calcolatori
Smart card
Requisiti diversi!
Parma, 14 novembre 2003 – p.11/28
Altri algoritmi
Parma, 14 novembre 2003 – p.12/28
k
Espansione 2 -aria
precalcola t P per t = 2 . . . 2k − 1
poni n = (nΛ nΛ−1 · · · n0 )2k , Q = nΛ P
mentre i = (Λ − 1) . . . 0:
poni Q = 2k Q
se ni 6= 0: poni Q = Q + ni P
Parma, 14 novembre 2003 – p.13/28
k
Espansione 2 -aria
precalcola t P per t = 2 . . . 2k − 1
poni n = (nΛ nΛ−1 · · · n0 )2k , Q = nΛ P
mentre i = (Λ − 1) . . . 0:
poni Q = 2k Q
se ni 6= 0: poni Q = Q + ni P
Ad esempio: se k = 3 e n = 229 = 11 100 1012 = 3458
112 = 3
1002 = 4
1012 = 5
Q = 8 · 3P = 24P
Q = 8 · 28P = 224P
Q = 3P Q = (4 + 24)P = 28P Q = (5 + 224)P = 225P
Parma, 14 novembre 2003 – p.13/28
k
Espansione 2 -aria: analisi I
Precalcoli: 2k − 2 operazioni
Parma, 14 novembre 2003 – p.14/28
k
Espansione 2 -aria: analisi I
Precalcoli: 2k − 2 operazioni
In realtà: 2k−1 − 1; basta precalcolare t P con t
dispari e raddoppiare in modo opportuno
Parma, 14 novembre 2003 – p.14/28
k
Espansione 2 -aria: analisi I
Precalcoli: 2k − 2 operazioni
In realtà: 2k−1 − 1; basta precalcolare t P con t
dispari e raddoppiare in modo opportuno
µ¹
º
¶
λ(n) + 1
Raddoppi: k
− 1 ∼ λ(n) − k
k
Parma, 14 novembre 2003 – p.14/28
k
Espansione 2 -aria: analisi I
Precalcoli: 2k − 2 operazioni
In realtà: 2k−1 − 1; basta precalcolare t P con t
dispari e raddoppiare in modo opportuno
µ¹
º
¶
λ(n) + 1
Raddoppi: k
− 1 ∼ λ(n) − k
k
Somme: #{ni 6= 0} − 1 dove n = (nΛ nΛ−1 · · · n0 )2k
Parma, 14 novembre 2003 – p.14/28
k
Espansione 2 -aria: analisi I
Precalcoli: 2k − 2 operazioni
In realtà: 2k−1 − 1; basta precalcolare t P con t
dispari e raddoppiare in modo opportuno
µ¹
º
¶
λ(n) + 1
Raddoppi: k
− 1 ∼ λ(n) − k
k
Somme: #{ni 6= 0} − 1 dove n = (nΛ nΛ−1 · · · n0 )2k
Memoria: 2k − 1 (o meglio: 2k−1 ) punti
Parma, 14 novembre 2003 – p.14/28
k
Espansione 2 -aria: analisi II
Considerando i precalcoli,
CS0 (e) ' 2k−1 +
µ
¶
1 e −1
1− k
k
2
Parma, 14 novembre 2003 – p.15/28
k
Espansione 2 -aria: analisi II
Considerando i precalcoli,
CS0 (e) ' 2k−1 +
µ
¶
1 e −1
1− k
k
2
Per minimizzare CS0 (e) prendiamo k minimo t. c.
k(k + 1)22k
≥ e −1
k+1
2 −k −2
Parma, 14 novembre 2003 – p.15/28
k
Espansione 2 -aria: analisi II
Considerando i precalcoli,
CS0 (e) ' 2k−1 +
µ
¶
1 e −1
1− k
k
2
Per minimizzare CS0 (e) prendiamo k minimo t. c.
k(k + 1)22k
≥ e −1
k+1
2 −k −2
La scelta migliore per k è quindi 1 se e ≤ 9, 2 se e ≤ 25,
oppure 6 se 538 < e ≤ 1434.
Parma, 14 novembre 2003 – p.15/28
Catene di addizione/sottrazione
La migliore catena d’addizione per 15 è
1, 2, 3, 6, 7, 14, 15
di lunghezza 6
Parma, 14 novembre 2003 – p.16/28
Catene di addizione/sottrazione
La migliore catena d’addizione per 15 è
1, 2, 3, 6, 7, 14, 15
di lunghezza 6
Se ammettiamo che ai = a j ± ak otteniamo la catena
1, 2, 4, 8, 16, 15 = 16 − 1
di lunghezza 5
Parma, 14 novembre 2003 – p.16/28
Catene di addizione/sottrazione
La migliore catena d’addizione per 15 è
1, 2, 3, 6, 7, 14, 15
di lunghezza 6
Se ammettiamo che ai = a j ± ak otteniamo la catena
1, 2, 4, 8, 16, 15 = 16 − 1
di lunghezza 5
Catene siffatte sono dette di addizione/sottrazione.
Sono utili solo se l’inversione costa poco: ad esempio
per le curve ellitiche.
Parma, 14 novembre 2003 – p.16/28
Bit segnati
Per realizzare un catena di A/S rappresentiamo
l’intero n con bit segnati:
n=
λ
X
ni 2i
con ni ∈ {−1= 1̄, 0, +1} e nλ = 1
i =0
e implementiamo «somma e raddoppia» con le
ovvie variazioni.
Parma, 14 novembre 2003 – p.17/28
Bit segnati
Per realizzare un catena di A/S rappresentiamo
l’intero n con bit segnati:
n=
λ
X
ni 2i
con ni ∈ {−1= 1̄, 0, +1} e nλ = 1
i =0
e implementiamo «somma e raddoppia» con le
ovvie variazioni.
Vantaggi Nessun precalcolo; il peso segnato è
inferiore a quello standard
Parma, 14 novembre 2003 – p.17/28
Bit segnati
Per realizzare un catena di A/S rappresentiamo
l’intero n con bit segnati:
n=
λ
X
ni 2i
con ni ∈ {−1= 1̄, 0, +1} e nλ = 1
i =0
e implementiamo «somma e raddoppia» con le
ovvie variazioni.
Vantaggi Nessun precalcolo; il peso segnato è
inferiore a quello standard
Svantaggi La rappresentazione non è unica
Parma, 14 novembre 2003 – p.17/28
Bit segnati: esempio
Scriviamo 23 = 101112 = 101̄001̄2 = 32 − 9:
0
0
0
1̄
1̄
Q = 2P Q = 4P Q = 6P Q = 12P Q = 24P
Q=P
Q = 3P
Q = 23P
1
Parma, 14 novembre 2003 – p.18/28
Bit segnati: esempio
Scriviamo 23 = 101112 = 101̄001̄2 = 32 − 9:
0
0
0
1̄
1̄
Q = 2P Q = 4P Q = 6P Q = 12P Q = 24P
Q=P
Q = 3P
Q = 23P
1
Oppure scriviamo 23 = 11001̄2 = 24 − 1:
1
Q=P
1
Q = 2P
Q = 3P
0
Q = 6P
0
Q = 12P
1̄
Q = 24P
Q = 23P
Parma, 14 novembre 2003 – p.18/28
NAF modificata
Pλ
Diciamo che la rappresentazione n = i =0 ni 2i con
bit segnati è in forma non adiacente modificata se
∀i < λ, ni 6= 0 ⇒ ni −1 = 0 e nλ−1 6= 1̄
Ad esempio 23 = 11001̄.
Parma, 14 novembre 2003 – p.19/28
NAF modificata
Pλ
Diciamo che la rappresentazione n = i =0 ni 2i con
bit segnati è in forma non adiacente modificata se
∀i < λ, ni 6= 0 ⇒ ni −1 = 0 e nλ−1 6= 1̄
Ad esempio 23 = 11001̄.
Teorema Per ogni n ∈ N, la NAF modificata è unica,
ha la stessa lunghezza di n ed è di peso minimo
Parma, 14 novembre 2003 – p.19/28
NAF modificata
Pλ
Diciamo che la rappresentazione n = i =0 ni 2i con
bit segnati è in forma non adiacente modificata se
∀i < λ, ni 6= 0 ⇒ ni −1 = 0 e nλ−1 6= 1̄
Ad esempio 23 = 11001̄.
Teorema Per ogni n ∈ N, la NAF modificata è unica,
ha la stessa lunghezza di n ed è di peso minimo
Il calcolo della NAF modificata è semplice ed è simile
a quello per le frazioni continue
Parma, 14 novembre 2003 – p.19/28
NAF modificata: analisi
Wieb Bosma (2001) dimostra che, per la NAF
modificata:
µ
e¶
1 (−1) 1
e 5
CS (e) = − − −
3 9
2
18 2e
e
e
2
(−1)
e
CS0 (e) = − +
3 9 9 · 2e−1
Parma, 14 novembre 2003 – p.20/28
Finestre scorrevoli
Fissiamo k > 1 e precalcoliamo t P con t = 3 . . . 2 k − 1
dispari
Parma, 14 novembre 2003 – p.21/28
Finestre scorrevoli
Fissiamo k > 1 e precalcoliamo t P con t = 3 . . . 2 k − 1
dispari
Suddividiamo, a partire da sinistra, l’espansione binaria
di n in finestre di lunghezza al più k della forma 1 ∗ ∗ ∗ 1
Parma, 14 novembre 2003 – p.21/28
Finestre scorrevoli
Fissiamo k > 1 e precalcoliamo t P con t = 3 . . . 2 k − 1
dispari
Suddividiamo, a partire da sinistra, l’espansione binaria
di n in finestre di lunghezza al più k della forma 1 ∗ ∗ ∗ 1
Calcoliamo nP come al solito.
Parma, 14 novembre 2003 – p.21/28
Finestre scorrevoli
Fissiamo k > 1 e precalcoliamo t P con t = 3 . . . 2 k − 1
dispari
Suddividiamo, a partire da sinistra, l’espansione binaria
di n in finestre di lunghezza al più k della forma 1 ∗ ∗ ∗ 1
Calcoliamo nP come al solito.
Ad esempio: se k = 3 e n = 565 = 1 000 11 0 101
12
Q=P
2
0002
112 = 3
02
1012 = 5
Q = 8P
Q = 4 · 8P = 32P
Q = 2 · 35P = 70P
Q = 8 · 70P = 560P
Q = (3 + 32)P = 35P
Q = (560 + 5)P = 565P
Parma, 14 novembre 2003 – p.21/28
Finestre scorrevoli: analisi I
Raddoppi: come al solito
Parma, 14 novembre 2003 – p.22/28
Finestre scorrevoli: analisi I
Raddoppi: come al solito
Somme: Scriviamo n = ν2ε + n 0 dove ν < 2k dispari e
λ(n 0 ) ≤ λ(n) − k.
Parma, 14 novembre 2003 – p.22/28
Finestre scorrevoli: analisi I
Raddoppi: come al solito
Somme: Scriviamo n = ν2ε + n 0 dove ν < 2k dispari e
λ(n 0 ) ≤ λ(n) − k. Allora cS (n) = 0 se n 0 = 0 e
cS (n) = 1 + cS (n 0 ) sennò.
Parma, 14 novembre 2003 – p.22/28
Finestre scorrevoli: analisi I
Raddoppi: come al solito
Somme: Scriviamo n = ν2ε + n 0 dove ν < 2k dispari e
λ(n 0 ) ≤ λ(n) − k. Allora cS (n) = 0 se n 0 = 0 e
cS (n) = 1 + cS (n 0 ) sennò. Quindi CS (e) = 0 se e ≤ k
mentre
1
CS (e − 1) + CS (e − k) + 1
− e−k+1
CS (e) =
2
2
se e > k
Parma, 14 novembre 2003 – p.22/28
Finestre scorrevoli: analisi I
Raddoppi: come al solito
Somme: Scriviamo n = ν2ε + n 0 dove ν < 2k dispari e
λ(n 0 ) ≤ λ(n) − k. Allora cS (n) = 0 se n 0 = 0 e
cS (n) = 1 + cS (n 0 ) sennò. Quindi CS (e) = 0 se e ≤ k
mentre
1
CS (e − 1) + CS (e − k) + 1
− e−k+1
CS (e) =
2
2
se e > k
Brutta ricorsione!
Parma, 14 novembre 2003 – p.22/28
Finestre scorrevoli: analisi II
Fissiamo k = 2. Posto δe = 2e CS (e) otteniamo
δe = δe−1 + 2δe−2 + 2e−1 − 2,
con δ1 = δ2 = 0
Parma, 14 novembre 2003 – p.23/28
Finestre scorrevoli: analisi II
Fissiamo k = 2. Posto δe = 2e CS (e) otteniamo
δe = δe−1 + 2δe−2 + 2e−1 − 2,
con δ1 = δ2 = 0
basata, a sua volta, sulla pseudo-Fibonacci
con a0 = 1, a1 = 1
ae = ae−1 + 2ae−2 ,
¢
¡ e+1
e
che vale ae = 2 + (−1) /3.
Parma, 14 novembre 2003 – p.23/28
Finestre scorrevoli: analisi II
Fissiamo k = 2. Posto δe = 2e CS (e) otteniamo
δe = δe−1 + 2δe−2 + 2e−1 − 2,
con δ1 = δ2 = 0
basata, a sua volta, sulla pseudo-Fibonacci
con a0 = 1, a1 = 1
ae = ae−1 + 2ae−2 ,
¢
¡ e+1
e
che vale ae = 2 + (−1) /3. E quindi
(3e − 8)2e − (−1)e
+1
δe =
9
Parma, 14 novembre 2003 – p.23/28
Finestre scorrevoli: analisi III
Considerando il precalcolo 3P, otteniamo per k = 2:
µ
e¶
(−1) 1
1
1
CS (e) = e + + 1 −
3
9
9
2e
e
4
(−1)
1
CS0 (e) = e + −
3
9 9 · 2e−2
Parma, 14 novembre 2003 – p.24/28
Finestre scorrevoli: analisi III
Considerando il precalcolo 3P, otteniamo per k = 2:
µ
e¶
(−1) 1
1
1
CS (e) = e + + 1 −
3
9
9
2e
e
4
(−1)
1
CS0 (e) = e + −
3
9 9 · 2e−2
Se k ≥ 3:
Parma, 14 novembre 2003 – p.24/28
Finestre scorrevoli: analisi III
Considerando il precalcolo 3P, otteniamo per k = 2:
µ
e¶
(−1) 1
1
1
CS (e) = e + + 1 −
3
9
9
2e
e
4
(−1)
1
CS0 (e) = e + −
3
9 9 · 2e−2
Se k ≥ 3:
Continua. . .
Parma, 14 novembre 2003 – p.24/28
Confrontiamo le prestazioni
e
CR0 (e)
50
49
200
199
600
599
Parma, 14 novembre 2003 – p.25/28
Confrontiamo le prestazioni
e
CR0 (e)
CS0 (e) con S&R
CS0 (e) con 2k , k = 2
CS0 (e) con 2k , k ottimale
CS0 (e) con NAF mod.
CS0 (e) con finestre sc. k = 2
50
49
25
20
18
16
17
200
199
100
77
55
66
67
600
599
300
227
130
200
200
Parma, 14 novembre 2003 – p.25/28
Confrontiamo le prestazioni
e
CR0 (e)
CS0 (e) con S&R
CS0 (e) con 2k , k = 2
CS0 (e) con 2k , k ottimale
CS0 (e) con NAF mod.
CS0 (e) con finestre sc. k = 2
50
49
25
20
18
16
17
200
199
100
77
55
66
67
600
599
300
227
130
200
200
In pratica, consigliamo di usare l’algoritmo 2 k
per un valore opportuno di k — Henri C OHEN
Parma, 14 novembre 2003 – p.25/28
FINE
Parma, 14 novembre 2003 – p.26/28
PUBBLICITÀ
Parma, 14 novembre 2003 – p.27/28
Convegno
Giornate di Matematica Industriale
A Workshop on Coding Theory & Criptography
Milano, 1 dicembre 2003
http://users.mat.unimi.it/mirwork
Parleranno:
M. Sala, UCC Cork
W. Wolfowich, Roma
F. Osnato, STMicroelectronics
J. Golić, Telecom Italia Lab
M. Albanese, Politecnico di Milano
G. Bertoni, Politecnico di Milano
R. Caldelli, Università di Firenze
R. Avanzi, IEM Essen
Scadenze:
Registrazione – 24 novembre
Poster – 21 novembre
Parma, 14 novembre 2003 – p.28/28