Teoria dei Numeri
Number Theory
Cifrari asimmetrici più comuni
basati sulla Teoria dei Numeri
“… both Gauss and lesser mathematicians may be
justified in rejoicing that there is one science at
any rate, and that their own, whose very remoteness
from ordinary human activities keep it gentle and
clean.”
Barbara Masucci
Dipartimento di Informatica ed Applicazioni
Università di Salerno
[email protected]
http://www.dia.unisa.it/professori/masucci
G. H. Hardy, A Mathematician’s Apology, 1940
1
Barbara Masucci - DIA – Università di Salerno
Teoria dei numeri
Teorema della divisione
¾ Dati a є Z, n є N esiste un’unica coppia (q,r) con
Aritmetica modulare
Algoritmo di Euclide per il calcolo del gcd
Calcolo dell’inversa moltiplicativa mod n
Elevazione a potenza modulare
Generazione di numeri primi e test di
primalità
¾ Algoritmi per la fattorizzazione
¾
¾
¾
¾
¾
0 ≤r≤ n-1 tale che
a=q·n+r
quoziente
resto
¾ r è indicato con a mod n
¾a=11, n=7, 11=1·7+4 Æ r=11 mod 7=4
¾a=-11, n=7,-11=(-2) ·7+3 Æ r=-11 mod 7=3
Barbara Masucci - DIA – Università di Salerno
2
Barbara Masucci - DIA – Università di Salerno
3
Congruenze mod n
¾ a e b sono congruenti mod n
L’insieme Zn
¾ [a]n={a+kn, k є Z}
(a ≡b mod n) se
¾ Insieme dei numeri che divisi per n danno lo stesso resto a mod n
a mod n = b mod n
¾ Rappresentata dal più piccolo intero positivo che è in essa
¾ 73 ≡ 4 mod 23
¾ b є [a]n
¾ 73 mod 23 = 4 mod 23
¾ Zn={[a]n, 0 ≤a≤ n-1}
¾ 21 ≡-9 mod 10
b≡ a mod n
Zn={0,…, n-1}
¾ [1]4={…, -11, -7, -3, 1, 5, 9, 13, …}
¾ [2]4={…, -10, -6, -2, 2, 6, 10, 14, …}
¾ Se a ≡ b mod n allora b ≡ a mod n
¾ [3]4={…, -9, -5, -1, 3, 7, 11, 15, …}
4
Barbara Masucci - DIA – Università di Salerno
5
Massimo Comune
Divisore (gcd)
Aritmetica Modulare
¾Addizione modulo n
¾ d è il massimo comune divisore di a e n se
¾ d è un divisore di a e n
¾ ogni divisore di a e n è un divisore di d
¾ (a mod n) + (b mod n) = (a+b) mod n
¾Proprietà
d=a·x+n·y
Commutativa
Associativa
Distributiva
Identità
Esistenza inversa additiva
¾ Proprietà
¾ gcd(a, n)=gcd(a, -n)=gcd(-a, -n)=gcd(|a|, |n|)
¾ gcd(a, 0)=|a|
¾ se gcd(a, n)=1, a e n sono relativamente primi
¾ (l’inversa additiva di x è y tale che x+y≡ 0 mod n)
(Zn, +) gruppo additivo mod n
Barbara Masucci - DIA – Università di Salerno
per semplicità
n | (b-a)
¾ [0]4={…, -12, -8, -4, 0, 4, 8, 12, …}
¾ Se a ≡ b mod n allora n|(b-a)
¾
¾
¾
¾
¾
b-a=kn
¾ Esempio: Z4={[0]4, [1]4, [2]4, [3]4}
¾ 21 mod 10 = -9 mod 10
Barbara Masucci - DIA – Università di Salerno
b=a+kn
6
Barbara Masucci - DIA – Università di Salerno
7
Aritmetica Modulare
L’insieme Zn*
Zn* = { [a]n, 0<a≤ n-1 e gcd(a,n)=1}
¾Moltiplicazione modulo n
¾ Esempio: Z4*={ [1]4, [3]4}
¾ (a mod n) · (b mod n) = (a · b) mod n
¾ [1]4={…, -11, -7, -3, 1, 5, 9, 13, …}
¾Proprietà
¾ [3]4={…, -9, -5, -1, 3, 7, 11, 15, …}
¾
¾
¾
¾
¾
¾ Esempio: Z8*={ [1]8, [3]8, [5]8, [7]8}
¾ [1]8={…, -23, -15, -7, 1, 9, 17, 25, …}
¾ [3]8={…, -21, -13, -5, 3, 11, 19, 30, …}
Commutativa
Associativa
Distributiva
Identità
Esistenza inversa moltiplicativa
¾ L’inversa moltiplicativa di x è y tale che x·y≡ 1 mod n)
(Zn *, ·) gruppo moltiplicativo mod n
8
Barbara Masucci - DIA – Università di Salerno
Aritmetica mod 8
Algoritmo di Euclide
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
0
1
2
3
4
5
6
7
0
0
0
0
0
0
0
0
0
1
1
2
3
4
5
6
7
0
1
0
1
2
3
4
5
6
7
2
2
3
4
5
6
7
0
1
2
0
2
4
6
0
2
4
6
3
3
4
5
6
7
0
1
2
3
0
3
6
1
4
7
2
5
4
4
5
6
7
0
1
2
3
4
0
4
0
4
0
4
0
4
5
5
6
7
0
1
2
3
4
5
0
5
2
7
4
1
6
3
6
6
7
0
1
2
3
4
5
6
0
6
4
2
0
6
4
2
7
7
0
1
2
3
4
5
6
7
0
7
6
5
4
3
2
1
Addizione
Moltiplicazione
Non tutti gli interi in Z8 hanno inversa moltiplicativa,
ma quelli in Z8*={ [1]8, [3]8, [5]8, [7]8} ce l’hanno
Barbara Masucci - DIA – Università di Salerno
9
Barbara Masucci - DIA – Università di Salerno
10
Descritto negli Elementi di Euclide (circa 300 A. C.)
Euclide
Euclide (a,n)
(a,n)
if
n
=
0
if n = 0 then
then return
return aa
else
else return
return Euclide
Euclide (n,
(n, aa mod
mod n)
n)
Teorema
Teorema della
della ricorsione
ricorsione del
del gcd
gcd
Per
Per tutti
tutti gli
gli interi
interi aa ≥≥ 00 ee nn >> 00
gcd(a,
gcd(a, n)
n) == gcd(n,
gcd(n, aa mod
mod n)
n)
Barbara Masucci - DIA – Università di Salerno
11
Algoritmo di Euclide:
Esempi
Algoritmo di Euclide:
complessità
¾ Assumiamo a > n ≥ 0
Euclide (30, 21) = Euclide (21, 9)
= Euclide (9, 3)
= Euclide (3, 0) = 3
¾ Se a<n, Euclide (a,n) chiama Euclide (n,a) e procede
¾ Se a=n, Euclide (a,n) termina subito perché a mod n=0
¾ Al massimo log n chiamate
¾ Analisi complessa basata sui numeri di Fibonacci
Euclide (4864, 3458) = Euclide (3458, 1406)
= Euclide (1406, 646)
= Euclide (646, 114)
= Euclide (114, 76)
= Euclide (76, 38)
= Euclide (38, 0) = 38
Barbara Masucci - DIA – Università di Salerno
¾ Per ogni chiamata O( (log a)2 ) operazioni su bit
¾ Totale: al massimo O( (log a)3 ) operazioni su bit
¾ Euclide (a,n) richiede al massimo O( (log a)2 ) operazioni
su bit
Polinomiale nella lunghezza dell’input
12
Algoritmo di Euclide Esteso
Algoritmo di Euclide Esteso
Euclide-esteso
Euclide-esteso (a,n)
(a,n)
if
if nn == 00 then
then return
return (a,
(a, 1,1, 0)
0)
(d´,
(d´, x´,
x´, y´)
y´) ←
← Euclide-esteso
Euclide-esteso (n,
(n, aa mod
mod n)
n)
(d,
(d, x,
x, y)
y) ←
← (d´,
(d´, y´,
y´, x´x´- ⎣a/n⎦
⎣a/n⎦ y´)
y´)
return
(d,
x,
y)
return (d, x, y)
a
n
d
x
Euclide-esteso
Euclide-esteso (a,n)
(a,n)
if
if nn == 00 then
then return
return (a,
(a, 1,1, 0)
0)
(d´,
x´,
y´)
←
Euclide-esteso
(d´, x´, y´) ← Euclide-esteso (n,
(n, aa mod
mod n)
n)
(d,
x,
y)
←
(d´,
y´,
x´⎣a/n⎦
y´)
(d, x, y) ← (d´, y´, x´- ⎣a/n⎦ y´)
return
return (d,
(d, x,
x, y)
y)
99
78
21
15
6
3
¾ Oltre a computare d=gcd(a,n) computa anche due interi x, y
tali che d = gcd(a,n) = a·x+n·y
¾ Stesso running time asintotico di Euclide (a,n)
Barbara Masucci - DIA – Università di Salerno
13
Barbara Masucci - DIA – Università di Salerno
14
78
21
15
6
3
0
Barbara Masucci - DIA – Università di Salerno
3
3
3
3
3
3
-11
3
-2
1
0
1
y
14
-11
3
-2
1
0
15
Soluzione di ax≡b (mod n)
Soluzione di ax≡b (mod n)
Dati
a, b, n calcolare x
0
1
3x≡7 (mod 8) soluzione 5
2
3
2x≡4 (mod 8) soluzione 2,6
4
4x≡2 (mod 8) nessuna soluzione 5
6
7
Esempi:
0
0
0
0
0
0
0
0
0
1
0
1
2
3
4
5
6
7
2
0
2
4
6
0
2
4
6
3
0
3
6
1
4
7
2
5
4
0
4
0
4
0
4
0
4
5
0
5
2
7
4
1
6
3
6
0
6
4
2
0
6
4
2
Barbara Masucci - DIA – Università di Salerno
7
0
7
6
5
4
3
2
1
16
Soluzione di ax≡1 (mod n)
soluzioni mod n:
b n
x' + i
g g
dove
per i = 0,1,…, g-1
g = a·x′+n·y (da Euclide-esteso (a,n) )
17
Barbara Masucci - DIA – Università di Salerno
Ha soluzioni se e solo se gcd(a,8) =1
1 = 1-1 mod 8
¾ Se gcd(a,n) =1 l’unica soluzione mod n è:
3 = 3-1 mod 8
x´
5 = 5-1 mod 8
1 = a·x′+n·y (da Euclide-esteso (a,n) )
¾ Tale soluzione viene denotata con a-1 mod n
(inversa moltiplicativa di a, mod n)
Barbara Masucci - DIA – Università di Salerno
¾ Se g|b ci sono esattamente g distinte
Soluzione di ax≡1 (mod 8)
¾ Ha soluzioni se e solo se gcd(a,n) =1
dove
(a,n)
¾ Ha soluzioni se e solo se g|b gg == gcd
gcd(a,n)
7 = 7-1 mod 8
18
0
1
2
3
4
5
6
7
0
0
0
0
0
0
0
0
0
Barbara Masucci - DIA – Università di Salerno
1
0
1
2
3
4
5
6
7
2
0
2
4
6
0
2
4
6
3
0
3
6
1
4
7
2
5
4
0
4
0
4
0
4
0
4
5
0
5
2
7
4
1
6
3
6
0
6
4
2
0
6
4
2
7
0
7
6
5
4
3
2
1
19
Soluzione di ax≡1 (mod 7)
Ha soluzioni se e solo se gcd(a,7) =1
1 = 1-1 mod 7
4 = 2-1 mod 7
5 = 3-1 mod 7
2 = 4-1 mod 7
3 = 5-1 mod 7
6 = 6-1 mod 7
0
1
2
3
4
5
6
0
0
0
0
0
0
0
0
1
0
1
2
3
4
5
6
2
0
2
4
6
1
3
5
3
0
3
6
2
5
1
4
4
0
4
1
5
2
6
3
5
0
5
3
1
6
4
2
Euclide-esteso
Euclide-esteso (a,n)
(a,n)
if
n
=
0
then
return
if n = 0 then return (a,
(a, 1,1, 0)
0)
(d´,
(d´, x´,
x´, y´)
y´) ←
← Euclide-esteso
Euclide-esteso (n,
(n, aa mod
mod n)
n)
(d,
(d, x,
x, y)
y) ←
← (d´,
(d´, y´,
y´, x´x´- ⎣a/n⎦
⎣a/n⎦ y´)
y´)
return
a n
return (d,
(d, x,
x, y)
y)
6
0
6
5
4
3
2
1
d = x·a + y·n
1 = -2·7 + 3·5
3=
20
Barbara Masucci - DIA – Università di Salerno
d = x·a + y·n
1 = 1·11 + (-2)·5
-2 =
5-1
mod 11
-2 = 9 mod 11
Barbara Masucci - DIA – Università di Salerno
5-1
mod 7
7
5
d
1
x y
-2 3
5
2
1
1 -2
2
1
1
0
1
1
0
1
1
0
21
Barbara Masucci - DIA – Università di Salerno
Teorema cinese del resto
Esempio: calcolo di 5-1 mod 11
Euclide-esteso
Euclide-esteso (a,n)
(a,n)
if
if nn == 00 then
then return
return (a,
(a, 1,1, 0)
0)
(d´,
(d´, x´,
x´, y´)
y´) ←
← Euclide-esteso
Euclide-esteso (n,
(n, aa mod
mod n)
n)
(d,
x,
y)
←
(d´,
y´,
x´⎣a/n⎦
y´)
(d, x, y) ← (d´, y´, x´- ⎣a/n⎦ y´)
return
a n
return (d,
(d, x,
x, y)
y)
Esempio: calcolo di 5-1 mod 7
Dati
¾ m1, m2,…,mt interi positivi tali che gcd(mi,mj)=1, i≠j
¾ M= m1·m2 …·mt
¾ a1, a2,…,at interi
11
5
d
1
x y
1 -2
5
1
1
0
1
1
0
1
1
0
9 = 5-1 mod 11
22
Esiste una sola soluzione modulo M al sistema di congruenze
x≡a1 mod m1
x≡a2 mod m2
…
x≡at mod mt
t
X = ∑ ai ⋅ Mi ⋅ yi mod M
i=1
Mi = M/mi
Barbara Masucci - DIA – Università di Salerno
yi = Mi-1 mod mi
23
Teorema cinese del resto
Elevazione a potenza modulare
Esempio
x≡2 mod 5
Calcolo di xy mod z
x≡3 mod 13
¾Metodo naive
¾Metodo left-to-right
a1=2, m1=5, M1=13, y1=13-1 mod 5=2
a2=3, m2=13, M2=5, y2=5-1 mod 13= 8
¾Metodo right-to-left
M=65
Soluzione del sistema:
2
X = ∑ ai ⋅ Mi ⋅ yi mod 65 = 2 ⋅ 26 + 3 ⋅ 40 mod65 = 42 mod 65
i=1
Barbara Masucci - DIA – Università di Salerno
24
Barbara Masucci - DIA – Università di Salerno
25
Elevazione a potenza modulare
Metodo naive
Elevazione a potenza modulare
Metodo naive
Calcolo di xy mod z
Calcolo di xy mod z
Potenza_Modulare_naive
Potenza_Modulare_naive (x,
(x, y,
y, z)
z)
Potenza_Modulare_naive
Potenza_Modulare_naive (x,
(x, y,
y, z)
z)
aa ←
← 11
for
for ii == 11 to
to yy do
do
aa ←
(a
← (a··x)
x) mod
mod zz
return
return aa
aa ←
← 11
for
for ii == 11 to
to yy do
do
aa ←
← (a
(a··x)
x) mod
mod zz
return
return aa
512
Se y è di 512 bit, occorrono ≈ 2
operazioni
Esponenziale nella lunghezza dell’esponente
Barbara Masucci - DIA – Università di Salerno
26
Barbara Masucci - DIA – Università di Salerno
27
Elevazione a potenza modulare
Metodo left-to-right
Calcolo di xy mod z
Idea:
Elevazione a potenza modulare
Metodo left-to-right
y = y020+ y121 +… +yt2t
Calcolo di xy mod z
Idea:
y = y0+2(y1+ 2(y2+… +2(yt-1+2yt)))))
y = y020+ y121 +… +yt2t
y = y0+2(y1+ 2(y2+… +2(yt-1+2yt)))))
y +2(y +2(y +…+2(y
Esempio:
40 = 0·20 + 0·21 + 0·22 +1·23 + 0·24 +1·25
y
y1+2(y2+…+2(yt-1+2yt))))) 2
y
y
= x 0(x
)
y
y
y +…+2(yt-1+2yt))))) 2 2
= x 0(x 1(x 2
))
40 = 0 + (2 (0 + 2 (0 + (2 (1 + 2 (0 + 2·1))))))
= x 0 (x 1( … (x
28
Barbara Masucci - DIA – Università di Salerno
Elevazione a potenza modulare
Metodo left-to-right
Calcolo di xy mod z
Idea:
+2y )))))
t-1
t
xy = x 0 1 2
y 2(y +2(y +…+2(yt-1+2yt)))))
= x 0x 1 2
y
y = y020+ y121 +… +yt2t
yt-1
y
(x1
Barbara Masucci - DIA – Università di Salerno
Calcolo di xy mod z
xy = x 0 (… (x
2 2 2 2 2
(x0 (x1) ) ) ) )
30
y = y020+ y121 +… +yt2t
y = y0+2(y1+… +2(yt-1+2yt)))))
y
(x t)2)2… )2
40 = 0 + (2 (0 + 2 (0 + (2 (1 + 2 (0 + 2·1))))))
(x0
29
Barbara Masucci - DIA – Università di Salerno
Idea:
Esempio: x40
40 = 0·20 + 0·21 + 0·22 + 1·23 + 0·24 + 1·25
x40 = x0 ( x0
y
(x t)2)2… )2
Elevazione a potenza modulare
Metodo left-to-right
y = y0+2(y1+… +2(yt-1+2yt)))))
xy = x 0 (… (x
yt-1
yt-1
y
(x t)2)2… )2
Potenza_Modulare
Potenza_Modulare (x,
(x, y,
y, z)
z)
aa ←
1
←1
for
for ii == tt downto
downto 00 do
do
aa ←
← (a
(a··a)
a) mod
mod zz
if
then aa ←
← (a
(a·· x)
x) mod
mod zz
if yyi i == 11 then
return
a
return a
Se y è di 512 bit, occorrono ≈ 512 operazioni
Polinomiale nella lunghezza dell’esponente
Barbara Masucci - DIA – Università di Salerno
31
Elevazione a potenza modulare
Metodo left-to-right
Elevazione a potenza modulare
Metodo right-to-left
Potenza_Modulare
Potenza_Modulare (x,
(x, y,
y, z)
z)
aa ←
1
←1
for
for ii == tt downto
downto 00 do
do
aa ←
← (a
(a··a)
a) mod
mod zz
if
then aa ←
← (a
(a·· x)
x) mod
mod zz
if yyi i == 11 then
return
a
return a
Calcolo di xy mod z
y = y020+ y121 +… +yt2t
0
Idea:
1
t
xy = x2 y0+2 y1…+2 yt
0
1
t
= x2 y0 · x2 y1 · … · x2 yt
0 y
1 y
t y
= (x2 ) 0 · (x2 ) 1 · … · (x2 ) t
334040mod
mod 73=8
73=8
yy55=1,
=1, yy44=0,
=0, yy33=1,
=1, yy22=0,
=0, yy11=0,
=0, yy00=0
=0
32
Barbara Masucci - DIA – Università di Salerno
Elevazione a potenza modulare
Metodo right-to-left
Calcolo di xy mod z
Elevazione a potenza modulare
Metodo right-to-left
y = y020+ y121 +… +yt2t
0 y
Idea:
1 y
t yt
Calcolo di xy mod z
y = y020+ y121 +… +yt2t
0 y
Idea:
xy = (x2 ) 0 · (x2 ) 1 · … · (x2 )
1 y
t yt
xy = (x2 ) 0 · (x2 ) 1 · … · (x2 )
Esempio: x40
Esempio: x40
40 = 0·20+ 0·21 +0·22 + 1·23 + 0·24 + 1·25
40 = 0·20+ 0·21 +0·22 + 1·23 + 0·24 + 1·25
0
33
Barbara Masucci - DIA – Università di Salerno
0
0
1
0
0
1
=1
x1
Barbara Masucci - DIA – Università di Salerno
0
0
1
0
1
x8
=1
x16
x32
x40 = (x1) · (x2) · (x4) · (x8) · (x16) · (x32)
x40 = (x1) · (x2) · (x4) · (x8) · (x16) · (x32)
34
=1
x2
=1
4
x
Barbara Masucci - DIA – Università di Salerno
35
Elevazione a potenza modulare
Metodo right-to-left
Calcolo di xy mod z
Idea:
xy =
Elevazione a potenza modulare
Metodo right-to-left
y = y020+ y121 +… +yt2t
0 y
(x2 ) 0
·
1 y
(x2 ) 1 ·
…·
t y
(x2 ) t
Esempio: x40
40 = 0·20+ 0·21 +0·22 + 1·23 + 0·24 + 1·25
x40 =
x40 =
0
(x1)
·
=1
0
(x2) ·
=1
0
(x4) ·
1
(x8) ·
0
(x16)
·
1
(x32)
=1
=1
x8
36
Numeri primi
0
25
1
1
625
625
0
681
625
Polinomiale nella
lunghezza
dell’esponente
596mod 1234
55596
mod 1234
6
7
8
9
1
0
1
0
0
1
1011 369 421 779 947 925
67
67 1059 1059 1059 1013
37
Barbara Masucci - DIA – Università di Salerno
Funzione di Eulero
¾ Un intero p > 1 è un numero primo se e solo
se i suoi unici divisori sono 1 e sé stesso
Zn* = { [a]n, 0<a≤ n-1 e gcd(a,n)=1}
¾ Esempi: 2, 3, 5, 7, 11, 13, 17, 19,...
φ(n) = cardinalità di Zn* (funzione di Eulero)
¾ Teorema fondamentale dell’aritmetica
¾ φ(p) = p-1
¾ Ogni intero composto n > 1 può essere scritto in
modo unico come prodotto di potenze di primi
se p primo
¾ φ(pq) = (p-1)(q-1)
se p,q primi
⎛
1⎞
1⎞ ⎛
1 ⎞ ⎛
¾ φ(n) = n ⋅ ⎜⎜ 1 − ⎟⎟ ⋅ ⎜⎜ 1 − ⎟⎟ L ⎜⎜ 1 − ⎟⎟
⎝ p1 ⎠ ⎝ p2 ⎠ ⎝ pk ⎠
n = p1e1 p2e2... pkek
pi primo, ei intero positivo
Barbara Masucci - DIA – Università di Salerno
if
if yy == 00 then
then return
return 11
X
X←
← x;
x; PP ←
← 11
if
then PP ←
← xx
if yy00 == 11 then
for
for ii == 11 to
to tt do
do
X
←
X
·X
X ← X ·X mod
mod zz
if
then P ← P ·X mod z
if yyi=1
i=1 then P ← P ·X mod z
return
return PP i 0 1 2
3
4
5
yi 0
X 5
P 1
· x32
Barbara Masucci - DIA – Università di Salerno
Potenza_Modulare
Potenza_Modulare (x,
(x, y,
y, z)
z)
38
Barbara Masucci - DIA – Università di Salerno
se n = p1e1 p2e2... pkek,
pi primo, ei ≥ 0
39
Teorema di Eulero
Teorema di Fermat
¾Per ogni a ∈ Zn*, aφ(n) = 1 mod n
¾Se p è primo, per ogni a ∈ Zp*,
ap-1 = 1 mod p
¾Esempi:
¾Se p è primo, per ogni a ∈ Z
ap = a mod p
Esempi:
¾a=3, n=10, φ(10)=4 Æ 34=81=1 mod 10
¾a=2, n=11, φ(11)=10 Æ 210=1024=1 mod 11
¾a=7, p=19 Æ 718 = 1 mod 19
¾a=10, p=5 Æ 105 = 10 mod 5 = 0 mod 5
Barbara Masucci - DIA – Università di Salerno
40
Generazione di un
primo ‘grande’
Barbara Masucci - DIA – Università di Salerno
41
Generazione di un
primo ‘grande’
1.
1. Genera
Genera aa caso
caso un
un dispari
dispari pp di
di grandezza
grandezza appropriata
appropriata
2.
Testa
se
p
è
primo
2. Testa se p è primo
3.
3. Se
Se pp èè composto,
composto, go
go to
to 1.
1.
1.
1. Genera
Genera aa caso
caso un
un dispari
dispari pp di
di grandezza
grandezza appropriata
appropriata
2.
2. Testa
Testa se
se pp èè primo
primo
3.
3. Se
Se pp èè composto,
composto, go
go to
to 1.
1.
Come testare se un numero p è primo?
Che probabilità abbiamo che p sia primo?
Barbara Masucci - DIA – Università di Salerno
42
Barbara Masucci - DIA – Università di Salerno
43
Distribuzione dei
numeri primi
Scelta di un primo
di 512 bit
¾ Scelto un intero in [2,2512] la probabilità che sia
primo è circa 1 su ln 2512 (ln 2512 ≈ 354,89)
¾ π(x) = numero di primi in [2,x]
π (x)
¾ Teorema dei numeri primi: lim
x →∞
x/ln x
=1
¾ Numero medio di tentativi ≈ 354,89
¾ Se si scelgono solo dispari, numero medio di tentativi
≈ 177,44
π(x) è circa x/ln x
¾ Esempio: π(1010) = 455.052.511
¾ Se si scelgono dispari in [2511,2512] la probabilità è
1010/ln 1010 ≈ 434.294.481,9 (4% in meno)
≈
1 …
(
…
2512
2511
−
ln 2512 ln 2511
)
… 1
1
2
511
2
≈
1
177,79
510 bit scelti a caso
44
Barbara Masucci - DIA – Università di Salerno
Scelta di un primo
di 1024 bit
Barbara Masucci - DIA – Università di Salerno
45
Test di Primalità
¾ Scelto un intero in [2,21024] la probabilità che sia
primo è circa 1 su ln 21024 (ln 21024 ≈ 709,78)
¾ Numero medio di tentativi ≈ 709,78
¾ Se si scelgono solo dispari, numero medio di tentativi
≈ 354,89
Due tipi di test:
¾ Probabilistici
¾ Deterministici
¾ Se si scelgono dispari in [21023,21024] probabilità
≈
1 …
(
…
21024
21023
−
ln 21024 ln 21023
… 1
)
1
1023
2
2
1022 bit scelti a caso
Barbara Masucci - DIA – Università di Salerno
≈
1
355,23
46
Barbara Masucci - DIA – Università di Salerno
47
Diminuizione della
probabilità di errore
Test di primalità probabilistici
p
primo
Test
Test Primalità
Primalità
Probabilmente!
Probabilmente!
dichiarato primo) di tale test ≤ 1/2
composto
Insieme di witness W(p)
Certamente!
Certamente!
¾ dato a∈[0, p-1] è facile verificare se a∈W(p)
¾ se p è primo allora W(p) è vuoto
Scelgo
Scelgo aa
¾ se p è composto allora |W(p)| ≥ p/2
Barbara Masucci - DIA – Università di Salerno
48
Test di primalità
probabilistici
¾ Se il test viene ripetuto indipendentemente t
volte allora la probabilità di errore ≤ (1/2)t
49
Barbara Masucci - DIA – Università di Salerno
Test di Miller-Rabin
¾ Basato sul Teorema di Fermat:
Test di Solovay-Strassen
¾ Se p è primo, per ogni a ∈ Zp*, ap-1
¾Pubblicato nel 1977
= 1 mod p
¾ Algoritmo
¾Probabilità di errore ≤ (1/2)t
¾ p dispari, p-1 pari
¾ p-1=2kq, con q dispari e k>0
Test di Miller-Rabin
k
¾ Scegli 1 < a < p-1 e calcola aq, a2q, …,a2 q
k
¾ Se p è primo, a2 q = 1 mod p (teorema di Fermat)
j
¾ Sia j il più piccolo indice per cui a2 q = 1 mod p
¾Il più usato in pratica
¾ Se j=0, allora aq = 1 mod p ( cioè aq – 1 mod p =0)
j-1
j-1
¾ Se j>0, allora (a2 q -1)(a2 q +1) mod p =0
¾ p divide uno dei due fattori
¾ p non può jdividere il primo, altrimenti j non è il più piccolo valore
per cui a2 q = 1 mod p
j-1
¾ p divide il secondo fattore, da cui a2 q = -1 mod p
¾Il più veloce
¾Probabilità di errore ≤ (1/4)t
Barbara Masucci - DIA – Università di Salerno
¾ Probabilità di errore (n è composto ma viene
50
Barbara Masucci - DIA – Università di Salerno
51
Test di Miller-Rabin
Test di Miller-Rabin p=29
Insieme di witness di Miller-Rabin
Witness di Miller-Rabin
k
p-1
p-1==22kqq con
conqqdispari
dispari
WMR(p) = {a : aq ≠ 1 mod p and
j
a2 q ≠ -1 mod p per ogni j∈[0,k-1]}
¾ Se p è un primo dispari
2
29-1
29-1 == 222 ··77
WMR(29) = {a : a ≠ 1 mod 29 and
j
a2 ·7 ≠ -1 mod 29 per ogni j∈[0,1]}
¾ a=10
7
¾ 107 mod 29=17 (continua)
¾ (107)2 mod 29=28=-1 mod 29 (stop: “primo”)
WMR(p) è vuoto
¾ a=2
¾ Se p è un numero composto dispari
| WMR(p) | ≥ (3/4) ·φ(p)
¾ 27 mod 29=12 (continua)
¾ (27)2 mod 29=28= -1 mod 29 (stop: “primo”)
¾ Prova per tutti gli a ∈[1,28]: sempre output “primo”
52
Barbara Masucci - DIA – Università di Salerno
53
Test di primalità
deterministici
Test di Miller-Rabin p=221
Witness di Miller-Rabin
Barbara Masucci - DIA – Università di Salerno
2
221-1
221-1 == 222 ··55
55
WMR(221) = {a : a55 ≠ 1 mod 221 and
j
a2 ·55 ≠ -1 mod 221 per ogni j∈[0,1]}
¾ a=5
¾ Fino al 2002, il miglior test deterministico era una
variante di Cohen e Lenstra del test di Adleman,
Pomerance e Rumely [1983]
¾ Complessità (ln p)O(lg lg lg p)
¾ 555 mod 221=112 (continua)
¾ (555)2 mod 221=168 (valori terminati, stop: “composto”)
¾ Nel 2002, primo test deterministico polinomiale
¾ a=21
proposto da Agrawal, Kayal e Saxena
¾ 2155 mod 221=220= -1 mod 221 (stop: “primo”)
¾ Complessità O(ln p)6+ε
¾ Per ogni a ∈ {1,…,220}/ WMR(221), output: “primo”
¾ a=1, 21, 47, 174, 200, 220
Barbara Masucci - DIA – Università di Salerno
54
Barbara Masucci - DIA – Università di Salerno
55
Fattorizzazione
Complessità algoritmi
La sicurezza di molte tecniche crittografiche
Un algoritmo ha complessità
si basa sulla intrattabilità della fattorizzazione:
¾ pienamente esponenziale se il suo running time è O(2ck),
dove k è la taglia dell’input e c>0 è una costante
¾ crittosistema RSA, Rabin
¾ sub-esponenziale se il suo running time è O(2o(k)), dove k è
¾ firme digitali RSA
la taglia dell’input
Esempio: n=3337
Soluzione p = 47, q = 71
56
Barbara Masucci - DIA – Università di Salerno
Calcolo di un fattore primo:
a
n]
1-a
con c > 0 ed 0 < a < 1
(esponenziale nella lunghezza dell’input)
Barbara Masucci - DIA – Università di Salerno
57
Barbara Masucci - DIA – Università di Salerno
Lq[a,c] = O(e(c+o(1))(ln q) (lnln q) )
Complessità caso peggiore Θ( n ) = Θ(21/2 log n)
n ≈2
dell’input e c>0 è una costante
Complessità di tempo sub-esponenziale in media
Se p|n allora p è fattore di n
Se n ha 512 bit allora
¾ polinomiale se il suo running time è O(kc), dove k è la taglia
Fattorizzazione:
complessità algoritmi
Fattorizzazione:
un semplice algoritmo
Per tutti i primi p in [2,
f(n)
=0
¾ f(n)=o(g(n)) se lim
n →∞ g(n)
Dato n, calcolare due primi p,q>1 tali che n=p•q
¾ Algoritmo basato su curve ellittiche: Ln[ 1/2, 1]
¾ Quadratic sieve: Ln[ 1/2, 1]
¾ General number field sieve: Ln[ 1/3, 1.923]
256
il più veloce
58
Barbara Masucci - DIA – Università di Salerno
59
General Number field sieve
in pratica
Quadratic sieve in pratica
¾ Quadratic sieve è migliore dell’algoritmo basato su
curve ellittiche
¾ General Number field sieve è migliore del Quadratic
sieve solo per interi di almeno 110-120 cifre decimali
1 mips per anno
13
≈ 3 ·10 istruzioni
anno
1984
1988
1993
1994
numero digit
71
106
120
129
numero bit
236
350
397
425
1 mips per anno
13
≈ 3 ·10 istruzioni
anno
1996
1999
mips per anno
0.01
140
825
5000
Barbara Masucci - DIA – Università di Salerno
RSARSA-129
1600 computer
per 8 mesi
factoring by e-mail
60
61
¾ Prova algoritmo Rho di Pollard
¾ Algoritmo basato su curve ellittiche: tempo medio
¾ Prova algoritmo basato su curve ellittiche
)
¾ Cerca fattori “grandi”
¾ Prova Quadratic sieve
II numeri
numeri più
più difficili
difficili da
da fattorizzare
fattorizzare sono
sono del
del
tipo
tipo nn == pq
pq con
con p,q
p,q primi
primi della
della stessa
stessa lunghezza
lunghezza
Barbara Masucci - DIA – Università di Salerno
Barbara Masucci - DIA – Università di Salerno
RSARSA-155
300 workstation +
CRAY per 5 mesi
¾ Prova divisione per alcuni piccoli primi (2,3,5,7,…)
¾ Algoritmo Rho di Pollard: tempo medio O(√p)
(lnln q)1/2
mips per anno
500
8000
¾ Cerca fattori “piccoli”
Algoritmi per calcolare un fattore p di n:
1/2
numero bit
430
512
Una strategia generale per
fattorizzare
Calcolo di fattori “piccoli”
Lp[1/2, √2] = O(e(√2+o(1))(ln q)
numero digit
130
155
62
¾ Prova General Number field sieve
Barbara Masucci - DIA – Università di Salerno
63
Bibliografia
¾Cryptography and Network Security
by W. Stallings (2003)
¾cap. 4 (Finite Fields)
¾cap. 8 (Introduction to Number Theory)
¾Introduction to Algorithms
by Cormen, Leiserson, Rivest (I ed)
¾cap 31 (Number Theory)
Barbara Masucci - DIA – Università di Salerno
64