Transcript n - PUC-Rio

Fingerprint
1
Verifying set equality
 String
Matching – Rabin-Karp Algorithm
2
Verifying set equality
3
Verifying set equality
4
Verifying set equality
5
Verifying set equality
6
Fingerprinting
7
Fingerprinting
8
Fingerprinting Computation
9
Fingerprinting Computation
Horner’s Rule
10
Protocol
11
Prime Number q
12
False Positive
13
Prime Divisors
14
Density of Primes
15
Density of Primes
 (x)
= número de primos menores ou iguais a x
– (13) = 6
– Primos < = do que 13 = 2, 3, 5 , 7, 11 e 13
valor de  não muda até chegarmos ao
próximo primo.
O
– (13) = (14) = (15) = (16)
– Ou seja,  aumenta em salto de 1, mas o intervalo
entre esses saltos é irregular
16
Density of Primes
Esses intervalos tornam-se cada vez maiores, isto
é, a chance de um inteiro escolhido ao acaso ser
primo diminui quando avançamos para os
números maiores.
PERGUNTA: O valor de
 não poderia ser aproximado por alguma
função conhecida?
17
Density of Primes
Para um valor elevado de x,
(x) ~ x/ ln x .
Ou seja,
lim (x) = 1
x   x/ln x
18
Sample Space
19
Probability of a bad prime
20
Final Protocol Properties
21
String Matching
22
String Matching
Many applications
–While using editor/word processor/browser
–Login name & password checking
–Virus detection
–Header analysis in data communications
–DNA sequence analysis
23
Naïve O(nm) algorithm
24
Rabin-Karp Algorithm
25
Fingerprinting
26
Fingerprinting function
27
Fingerprinting computation
The only expensive operation
28
False Positives?
29
Sample Space
30
False Positives
31
Fingerprinting
32
Primality testing
 A natural
number n is prime iff the only
natural numbers dividing n are 1 and n
33
Primality testing
 A natural
number n is prime iff the only
natural numbers dividing n are 1 and n
 The following are prime: 2, 3, 5, 7, 11, 13,
34
Primality testing
 A natural
number n is prime iff the only
natural numbers dividing n are 1 and n
 The following are prime: 2, 3, 5, 7, 11, 13,
…and so are 1299709,
15485863,
22801763489, …
35
Primality testing
 A natural
number n is prime iff the only
natural numbers dividing n are 1 and n
 The following are prime: 2, 3, 5, 7, 11, 13,
…and so are 1299709,
15485863,
22801763489, …
There is an infinite number of prime numbers
36
Primality testing
There is an infinite number of prime numbers
Proof: Let us suppose the number of primes is Finite.
37
Primality testing
There is an infinite number of prime numbers
Proof: Let us suppose the number of primes is Finite.
Let p1, p2, … pk be all primes.
Let n = p1 p2 … pk+1,
38
Primality testing
There is an infinite number of prime numbers
Proof: Let us suppose the number of primes is Finite.
Let p1, p2, … pk be all primes.
Let n = p1 p2 … pk+1,
 n must be composite.
39
Primality testing
There is an infinite number of prime numbers
Proof: Let us suppose the number of primes is Finite.
Let p1, p2, … pk be all primes.
Let n = p1 p2 … pk+1,
 n must be composite.
 there exists a
arithmetic),
prime p s.t. p | n (fund theo.
and p cannot be any of the p1, p2, … pk
40
Primality testing
There is an infinite number of prime numbers
Proof: Let us suppose the number of primes is Finite.
Let p1, p2, … pk be all primes.
Let n = p1 p2 … pk+1,
 n must be composite.
 there exists a
arithmetic),
prime p s.t. p | n (fund theo.
and p cannot be any of the p1, p2, … pk
Therefore, p1, … pk were not all the prime numbers.
41
Some questions?
 Is 2101-1=2535301200456458802993406410751
prime?
 How do we check whether a number is
prime?
 How do we generate huge prime numbers?
 Why do we care?
42
Some questions?
 Is 2101-1=2535301200456458802993406410751
prime?
 How do we check whether a number is
prime?
 How do we generate huge prime numbers?
 Why do we care?
43
Some questions?
 Is 2101-1=2535301200456458802993406410751
prime?
 How do we check whether a number is
prime?
 How do we generate huge prime numbers?
 Why do we care?
44
Some questions?
 Is 2101-1=2535301200456458802993406410751
prime?
 How do we check whether a number is
prime?
 How do we generate huge prime numbers?
 Why do we care?
45
Naïve solution: Finding
the smallest divisor of n
– For i=2,..., n do
 Divide
n by i until n mod i = 0
Check if i is a divisor of n for some i = 2, ..., n
46
An improvement
 Check
if i is a divisor of n for some
i = 2, ..., n
47
An improvement
 Check
if i is a divisor of n for some
i = 2, ..., n
Why can we do that?
48
Theorem: Composit numbers have a divisor
bellow their square root
49
Theorem: Composit numbers have a divisor
bellow their square root
Proof Idea: n composite  n = ab, 0 < a  b
<n
50
Theorem: Composit numbers have a divisor
bellow their square root
Proof Idea: n composite  n = ab, 0 < a  b
<n
 a  sqrt(n)
51
Theorem: Composit numbers have a divisor
bellow their square root
Proof Idea: n composite  n = ab, 0 < a  b
<n
 a  sqrt(n)
Otherwise, we obtain ab > n (contradiction!!)
52
Is there a more efficient
way of checking primality?
53
Is there a more efficient
way of checking primality?
Yes!
At least if we are willing to accept
a tiny probability of error.
54
Is there a more efficient
way of checking primality?
Yes!
At least if we are willing to accept
a tiny probability of error.
We can prove that a number is not
prime
without explicitly finding a divisor
of it
55
Is there a more efficient
way of checking primality?
Yes!
At least if we are willing to accept
a tiny probability of error.
We can prove that a number is not
prime
without explicitly finding a divisor
of it
RANDOMNESS IS USEFUL IN COMPUTATION
56
The Fermat Primality Test
Fermat’s little theorem:
If p is a prime and p does not divide the integer a,
then:
a p-11(mod p)
57
The Fermat Primality Test
Fermat’s little theorem:
If p is a prime and p does not divide the integer a,
then:
a p-11(mod p)
Proof:
• List the first p-1 positive multiple of a:
a, 2a, 3a, 4a, ..., (p-1) a
Suppose that ra e sa have are the same modulo p, then we have
r = s (mod p) Contradiction!!
Aa, 2a, 3a, ..., (p-1)a quando divididos por p possuem restos
diferentes:1, 2, ..., p-1
58
The Fermat Primality Test
Fermat’s little theorem:
If p is a prime and p does not divide the integer a,
then:
a p-11(mod p)
Proof:
• List the first p-1 positive multiple of a:
a, 2a, 3a, 4a, ..., (p-1) a
Suppose that ra and sa are the same modulo p, then we have r =
s (mod p) Contradiction!!
Aa, 2a, 3a, ..., (p-1)a quando divididos por p possuem restos
diferentes:1, 2, ..., p-1
59
The Fermat Primality Test
Fermat’s little theorem:
If p is a prime and p does not divide the integer a,
then:
a p-11(mod p)
Proof:
• List the first p-1 positive multiple of a:
a, 2a, 3a, 4a, ..., (p-1) a
Suppose that ra and sa are the same modulo p, then we have r =
s (mod p) Contradiction!!
Aa, 2a, 3a, ..., (p-1)a when divided by p have the different
reminders:1, 2, ..., p-1
60
The Fermat Primality Test
Fermat’s little theorem:
If p is a prime and p does not divide the integer a,
then:
a p-11(mod p)
Proof:
a. 2a. 3a. ... . (p-1)a  1. 2. 3. ... . (p-1) (mod p)
a(p-1)(p-1)! = (p-1)! (mod p)
61
The Fermat Primality Test
Fermat’s little theorem:
If p is a prime and p does not divide the integer a,
then:
a p-11(mod p)
Proof:
a. 2a. 3a. ... . (p-1)a  1. 2. 3. ... . (p-1) (mod p)
a(p-1)(p-1)! = (p-1)! (mod p)
Dividing by (p-1)! we get the result
62
A Corollary:
If p is a prime then, for any integer a:
ap  a (mod p)
63
A Corollary:
If p is a prime then, for any integer a:
ap  a (mod p)
The result is trivial if p divides a: a(ap-1 – 1)  0 (mod p)
If a does not divide a, then we need only multiply
the congruence in Fermat´s little theorem by a
to complete the proof
64
A Corollary:
If p is a prime then, for any integer a:
ap  a (mod p)
The result is trivial if p divides a: a(ap-1 – 1)  0 (mod p)
If p does not divide a, then we need only multiply
the congruence in Fermat´s little theorem by a
to complete the proof
65
Corollary:
If an ≠ a (mod n) , for some a, then n is not
a prime!
Such an a is a witness to the
compositeness of n.
The Fermat Test:
Do 100 times:
Pick a random 1<a<n and compute an (mod n).
If an  a (mod n), then n is not a prime.
If all 100 tests passed, declare n to be a prime.
66
Is the Fermat test correct?
If the Fermat test says that a number n is
composite,
then the number n is indeed a composite
number.
 If n is a prime number, the Fermat test will
always say that n is prime.

But,
 Can
the Fermat test say that a composite
number is prime?
 What is the probability that this will
happen?
69
Carmichael numbers
A composite number n is a Carmichael number
iff an  a (mod n) for every integer a.
The first Carmichael numbers are:
561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, …
On Carmichael numbers, the Fermat test is always wrong!
Carmichael numbers are fairly rare.
70
Theorem: (Rabin ’77)
If n is a composite number that is not a Carmichael
number, then at least half of the numbers between
1 and n are witnesses to the compositeness of n.
71
Theorem: (Rabin ’77)
If n is a composite number that is not a Carmichael
number, then at least half of the numbers between
1 and n are witnesses to the compositeness of n.
Proof: Consider Z*n = {1, 2, ..., n-1}
Let B={x / x  Z*n and xn-1  1 (mod n)}
We are going to show that B is subgroup of Z*n
For this:
1. 1 B
2. x1, x2  B  x1. x2  B
3. x  B  x-1  B
72
Theorem: (Rabin ’77)
If n is a composite number that is not a Carmichael
number, then at least half of the numbers between
1 and n are witnesses to the compositeness of n.
Proof: Consider Z*n = {1, 2, ..., n-1}
Let B={x / x  Z*n and xn-1  1 (mod n)}
We are going to show that B is subgroup of Z*n
For this:
1. 1 B : 1n-1  1 (mod n)
2. x1, x2  B  x1. x2  B
3. x  B  x-1  B
73
Theorem: (Rabin ’77)
If n is a composite number that is not a Carmichael
number, then at least half of the numbers between
1 and n are witnesses to the compositeness of n.
Proof: Consider Z*n = {1, 2, ..., n-1}
Let B={x / x  Z*n and xn-1  1 (mod n)}
We are going to show that B is subgroup of Z*n
For this:
(x1)n-1  1 (mod n)
(x2)n-1  1 (mod n)
n-1
1. 1 B : 1  1 (mod n)
2. x1, x2  B  x1. x2  B
(x1.x2)n-1  1 (mod n)
-1
3. x  B  x  B
74
Theorem: (Rabin ’77)
If n is a composite number that is not a Carmichael
number, then at least half of the numbers between
1 and n are witnesses to the compositeness of n.
Proof: Consider Z*n = {1, 2, ..., n-1}
Let B={x / x  Z*n and xn-1  1 (mod n)}
We are going to show that B is subgroup of Z*n
For this:
(1)n-1  1 (mod n)
(x.x-1)n-1  1 (mod n)
n-1
1. 1 B : 1  1 (mod n)
2. x1, x2  B  x1. x2  B
(x-1)n-1  1 (mod n)
-1
3. x  B  x  B
75
Theorem: (Rabin ’77)
If n is a composite number that is not a Carmichael
number, then at least half of the numbers between
1 and n are witnesses to the compositeness of n.
Proof:
Pr(xn-1  1 (mod n)) = Pr(x  B)
It can be proved that 1  B and n-1  B and therefore, |B|  2
Since the order of a subgroup divides the subgroup we have that
|B|  |Z*n | / 2
 Pr(x  B)  1/2
76
Theorem: (Rabin ’77)
If n is a composite number that is not a Carmichael
number, then at least half of the numbers between
1 and n are witnesses to the compositeness of n.
Corollary:
Let n be a composite number that is not a Carmichael
number. If we pick a random number a, 1<a<n, then a is
a witness with a probability of at least a 1/2 !
77
“Correctness” of the
Fermat test
 If
n is prime, the Fermat test is always
right.
 If n is a Carmichael number,
the Fermat test is always wrong!
 If n is composite number that is not a
Carmichael number, the Fermat test is
wrong with a probability of at most
2-100
Yes!
Is an error probability of 2-100 acceptable?
78
The Rabin-Miller test
 A fairly
simple modification of the Fermat
test that is correct with a probability of at
least 1-2-100 also on Carmichael numbers.
 Will
not be covered in this course.
79
A probabilistic algorithm
An algorithm that uses random choices but
outputs the correct result, with high probability,
for every input!
Randomness is a very useful algorithmic tool.
Up to 2002, there were no efficient
deterministic primality testing algorithms.
In 2002, Agarwal, Kayal and Saxena found a
fast deterministic primality testing algorithm.
80
Finding large prime
numbers
The prime number Theorem:
The number of prime numbers smaller than n is
asymptotically n / ln n.
Thus, for every number n, there is “likely” to be
a prime number between n and n + ln n.
To find a prime number roughly the size of n,
simply test n, n+2, n+4, … for primality.
81
Primality testing versus
Factoring
Fast primality testing algorithms determine that a
number n is composite without finding any of its
factors.
 No efficient factoring algorithms are known.
 Factoring a number is believed to be a much
harder task.

Primality testing - Easy
Factoring - Hard
But, factoring is not that hard
on a quantum computer!
82