Part X
Fooling the adversary - examples
Chapter 10. ABUNDANCE of WITNESSES TECHNIQUE
Abundance of witnesses (AOW) techniques is for two reasons “a real jewel” between
methods of the design of randomized algorithms:
An application of this techniques usually requires to use deep results from
mathematics.
This techniques is deeply related to the question of whether or not, for a given
problem, randomized mode of computation can be more efficient than the
deterministic mode.
A witness for a problem P and an input x is such an additional information y that
helps to solve the problem P for an input x in much more efficient way than one
can do that without y.
In this chapter we will discuss and illustrate this important technique for the design of
randomized algorithms.
It is also worth to notice that the fingerprinting technique can be also seen as a simplified
case of the abundance of witnesses techniques for the cases that witnesses are easy to
find.
prof. Jozef Gruska IV054 10. Fooling the adversary - examples 2/21
BASIC IDEAS – ABUNDANCE of WITNESS TECHNIQUE
In order to apply the AOW technique, one needs to have for every input instance a
set of candidates for witnesses in which there is an abundance (say more than half)
of witnesses. If this is the case, one gets a witness with a sufficient probability if one
chooses randomly an element from such a set of candidates for witnesses.
An important question, namely, whether for a given algorithmic problem P
randomized algorithms can be more efficient than deterministic, is closely related to
the question whether witnesses for P are randomly distributed or deterministically
ordered.
If witnesses are ordered, and one can discover this order for a given input instance,
then one can find witnesses in a deterministic way and in such a case deterministic
algorithms for a given problem can be efficient.
Randomized algorithms are more efficient only in the case witnesses are randomly
distributed in the set of potential witnesses and there is a lot of them.
prof. Jozef Gruska IV054 10. Fooling the adversary - examples 3/21
BASIC IDEAS II
It may happen that there is an order in the set of witnesses, but this order is very
hard to find.
An excellent example is the primality testing problem.
Inefficient methods to test primality have been known for years. Two main
randomized tests are shown in next slides.
Around 1977 the first randomized algorithms were designed and all of them used
abundance of witnesses technique.
In 2002 a definition of witnesses for primality testing was discovered with the
property that if p is composite, then there must always be a witness of p’s
compositeness among the smallest candidates for a witness.
This led to the discovery, as discussed in details later, by M. Agrawal, N. Kayal
and N. Saxena, from Kanpur, of the deterministic primality testing algorithm for
integers.
prof. Jozef Gruska IV054 10. Fooling the adversary - examples 4/21
RABIN-MILLER PRIMALITY TESTING
A simple randomized Rabin-Miller’s Monte Carlo algorithm for prime recognition is based
on the following result from the number theory.
Lemma Let n ∈ N, n = 2s
d + 1, d is odd. Denote, for 1 ≤ x < n, by C(x) the condition:
xd
≡ 1 (mod n) and x2r
d
≡ −1 (mod n) for all 1 < r < s
Fact: If C(x) holds for some 1 ≤ x < n, then n is not prime. If n is not prime, then
C(x) holds for at least half of x between 1 and n.
In other words, most of the numbers between 1 and n are witnesses for composability of
n.
Rabin-Miller algorithm
Choose randomly integers x1, . . . , xm such that 1 ≤ xj < n;
For each xj determine whether C(xj ) holds;
if C(xj ) holds for some xj ;
then n is not prime
else n is prime, with probability of error 2−m
prof. Jozef Gruska IV054 10. Fooling the adversary - examples 5/21
LEGENDRE and LEGENDRE-JACOBI SYMBOLS
In order to present second randomized algorithm for primality testing we need to
introduce Legendre and Legendre-Jacobi symbols having very important role in the
numer theory.
Notation QRn is the set of quadratic residua, that is of integers x such that
x = y2
mod n for some y; Complement of QRn is denoted QNRn.
Let us now define:
(x|m) =



1 ifx ∈ QRm and m is prime
−1 ifx ∈ QNRm and m is prime
n
i=1(x|pi ) ifm = n
i=1 pi , pi are primes, gcd(x, m) = 1
(x|m) is called the Legendre symbol if m is prime and the Legendre-Jacobi symbol
otherwise.
prof. Jozef Gruska IV054 10. Fooling the adversary - examples 6/21
Rules to compute (x|m)
1. Euler’s criterion: x|p ≡ x
p−1
2 (mod p) if p > 2 is prime, x ∈ Z∗
p
2. If x ≡ y(mod m), then (x|m) = (y|m).
3. (x|m) · (y|m) = (xy|m).
4. (−1|m) = (−1)
m−1
2 , if m is odd.
5. (2|m) = (−1)
m2−1
8 , if m is odd
6. Law of quadratic reciprocity: If gcd(m, n) = 1, m, n are odd, then
(n|m)(m|n) = (−1)
(m−1)(n−1)
4 .
Example:
(28|97) = (2|97)(2|97)(7|97) = (7|97)
= (97|7)(−1)
(97−1)(7−1)
4 = (6|7)
= (2|7)(3|7) = (−1)6
(3|7) = (7|3)(−1)3
= −(1|3) = −1
At least 72 different proofs are known for the law of quadratic reciprocity.
prof. Jozef Gruska IV054 10. Fooling the adversary - examples 7/21
SOME TECHNICAL RESULTS
Theorem (Lagrange) If (H, ◦) is a subgroup of a group (G, ◦), then |H|
divides |G|.
Definition Euler quotient function is defined as follows
Φ(n) = |{m; 1 ≤ m < n, m does not divide n}.
Theorem (Euler’s Totient Theorem)
nΦ(m) ≡ 1 (mod m) if n < m, gcd(m, n) = 1
Corollary n−1 ≡ nΦ(m)−1 (mod m) if n < m, gcd(m, n) = 1
Theorem (Fermat’s Little Theorem)
For any a, it holds ap ≡ a (mod p) if p is prime.
prof. Jozef Gruska IV054 10. Fooling the adversary - examples 8/21
SOLOVAY-STRASSEN’s PRIME RECOGNITION ALGORITHM
It follows from the Lagrange theorem that if the following fast Monte Carlo algorithm —
based on the fact that computation of Legendre-Jacobi symbols can be done fast —
reports that a given number n is composite, then this is 100%, true and if it reports that
it is a prime, then the error is at most 1
2
.
begin choose randomly an integer a ∈ {1, . . . , n}
if gcd(a, n) = 1 then return “composite”
else if (a|n) ≡ a
n−1
2 (modn)
then return “composite”;
return “prime”
end
Indeed, if n is composite, then all integers a ∈ Zn such that (a|n) ≡ a
n−1
2 (modn) form a
proper subgroup of the group Z∗
n . This implies that most of the elements a ∈ Z∗
n are such
that (a|n) ≡ a
n−1
2 (mod n) and therefore they can “witness” coppositeness of n, if n is
composite.
prof. Jozef Gruska IV054 10. Fooling the adversary - examples 9/21
COMBINATION of TWO RANDOMIZED PRIMALITY TESTING
ALGORITMOV
1 Soloway and Strassen (and also Rabin, independently) developed an algorithm such
that for given integer n and another number a
If n is prime, then for any choice of a the output of the algorithm is prime
If n is composite, then for most of the choices of a the output of the algorithm is
composite.
2 Adleman and Huang dveloped an algorithm such that for given integer n and
another number a”
If n is prime, then for most of the choices of a, the output is prime
If n is composite, then for any choice of a, the output is composite.
If we combine both of these algorithms, will we always get a correct answer? Can we run
above algorithms in parallel till either the first one outputs ”composite” or second
outputs ”prime”
No, the trouble is that there is a small chance that none of the possibility ever happen.
prof. Jozef Gruska IV054 10. Fooling the adversary - examples 10/21
CHARACTERIZATION of WITNESSES
A good definition of a witness for proving a FACT (for example, that ”n is composite”)
should satisfy the following conditions:
1 A witness of the FACT should offer a possibility to verify the FACT easily.
2 One should be able easily verify for a to-be witness whether it is indeed a witness.
3 It should be possible to specify a set of candidates for witnesses with abundance of
witnesses.
Example Fermat’s Little Theorem says: For every prime p and every
a ∈ {1, 2, . . . , p − 1}, ap−1
mod p = 1. We could therefore try to define
A number a ∈ {1, 2, . . . , n − 1} is a witness of the fact “n ∈ PRIME” iff
an−1
mod n = 1.
However, this does not work because some composite integers have very few such
witnesses. There are even integers, so called Carmichael numbers, that have no witnesses
of such a type. Examples of Carmichael numbers: 561, 1105, 1729.
prof. Jozef Gruska IV054 10. Fooling the adversary - examples 11/21
ANOTHER ATTEMPT
The following theorem holds Theorem Let p > 2 be an odd integer. Then
p is a prime ↔ (a
p−1
2 mod p) ∈ {1, p − 1} for all a ∈ Zp − {0}
We could terefore try to define a set of witnesses for n ≥ 3 as follows:
A number a ∈ {1, 2, . . . , n − 1}
is a witness of the fact n ∈ PRIME iff
a(n−1)/2
mod n ∈ {1, n − 1}
The following theorem shows that the above definition assures the abundance of witness
for at least every second odd integer greater than 2.
Theorem For every Blum integer n, that is such and n that that n mod 4 = 3, it holds:
(a) if n is a prime, then
a(n−1)/2
mod n ∈ {1, n − 1}
for all a ∈ {1, . . . , n − 1}, and
(b) if n is composite, then
a(n−1)/2
mod n ∈ {1, n − 1}
prof. Jozef Gruska IV054 10. Fooling the adversary - examples 12/21
SIMPLIFIED SOLOVAY STRASSEN’S ALGORITHM
Algorithm works only for Blum integers:
1 Choose randomly ai ∈ {2, . . . , n − 1}, for i = 1, . . . , k;
2 Compute all Ai = a
(n−1)/2
i mod n
3 If one Ai ∈ {−1, 1}, then n is surely composite; otherwise probability
that n is not prime is smaller than 1
2k
prof. Jozef Gruska IV054 10. Fooling the adversary - examples 13/21
AKS - deterministic polynomial primality testing
In 1975 Gary L. Miller design a deterministic polynomial primality testing algorithm
that works correctly provided so called Generalized Rieman hypothesis (that has
been experimentally verified till ???) holds.
On 6.8.2002 Manindra Agrawal, Neeraj Kayal and Nitin Saxena, from the Indian
Institute of Technology in Kanpur published the paper ”PRIMES are in P”, with
detrministic polynomial time primality testing algorithm, for which they received in
2006 Godel prize and also Fulkerson prize.
prof. Jozef Gruska IV054 10. Fooling the adversary - examples 14/21
AKS algorithm for primality test of an integer n
1 If n = ab
for some integers a, b greater than 1 , output composite;
2 Find smallest r such that Or (n) > lg2
n.
3 If 1 < gcd(a, n) < n for some a ≤ r, output composite.
4 If n ≤ r, output prime.
5 For a = 1 to φ(r) lg n do
if (X + a)n
= xn
+ a (mod(Xr
− 1, n)), output composite;
6 Output prime
where
Or (n) is multiplicative order of n modulo r
φ is the Euler function.
prof. Jozef Gruska IV054 10. Fooling the adversary - examples 15/21
PASCAL TRIANGLES
It is a triangle having in n + 1-th raw, n ≥ 1, n + 1 integers, n
i
, 0 ≤ i ≤ n.
1
1
1
1
21
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 2135 7
1 8 28 56 70 56 28 8 1
1
One can show that when ignoring first and last number of each raw, namely n
0
and
n
n
, then all numbers in the n-th raw are divided by n if and only if n is prime.
Aggrawal, Kayal and Saxenna found a how utilize the above fact.
prof. Jozef Gruska IV054 10. Fooling the adversary - examples 16/21
BASIC IDEAS behind the AKS METHOD
The AKS primality test is now based on the following theorem:
Theorem An integer n ≥ 2 is prime if and only if the polynomial congruence relation
(x − a)n
≡ (xn
− a)(mod n)
holds for all integers a that are coprime to n.
While the above relation constitutes a primality test in itself, verifying it takes
exponential time.
To reduce computational complexity, AKS makes use of the related congrueence
(x − a)n
≡ (xn
− a) (mod n, xr
− 1)
which is the same as
(x − a)n
− (xn
− a) ≡ 0 (mod n, xr
− 1)
which is the same as
(x − a)n
− (xn
− a) = nf + (xr
− 1)g
for some polynomials f and g. The last congruence can be checked in polynomial
time.
prof. Jozef Gruska IV054 10. Fooling the adversary - examples 17/21
Thhe proof of correctness consists now in showing
that there exists a suitably small r and a suitably
small set of integers A such that, if the above
congruence holds for all a ∈ A, then n must be a
prime.
prof. Jozef Gruska IV054 10. Fooling the adversary - examples 18/21
STORY of AKS PRIMALITY TEST
On 6.8.2002 Manindra Agrawal, Neeraj Kayal and Nitin Saxena, from the Indian
Institute of Technology in Kanpur published the paper ”PRIMES are in P” for which
they received in 2006 Godel prize and also Fulkerson prize.
To test m digit integer with the AKS algorithm required O(m12
) time.
Shortly after that they improved the algorithm to have complexity O(m10.5
) and
O(m7.5
).
In 2005, Carl Pomerance and H.W. Lenstra, Jr, developed a variant of AKS
algorithm with complexity O(m6
).
Unfortunately, storage requirements of the KS algorithm are huge. To test 1024 bits
numbers 109
gigabytes of storage is needed.
prof. Jozef Gruska IV054 10. Fooling the adversary - examples 19/21
APPENDIX
APPENDIX
prof. Jozef Gruska IV054 10. Fooling the adversary - examples 20/21
EXERCISES
1 Show that number of primes is infinite. (Already Archimedes new
a simple proof.)
prof. Jozef Gruska IV054 10. Fooling the adversary - examples 21/21