CS 15-451 Analysis of Algorithms 18 November 2004
Manuel & Avrim Blum
Today: number theoretic algorithms,
randomizing algorithms,
and... QUIZ!
1. Let a, e, m be three n-bit numbers. Then can compute
a^e mod m in O(n^3) steps using ordinary multiplication. More generally,
can compute it in O(n*M(n)) steps using any fast integer
multiplication that multiplies 2 n-bit numbers in M(n) steps.
In what follows, we use n to denote the length of an input, and N to denote
the positive input integer under consideration.
2. Observation 1 above has many applications, including the design of
collision-resistant hash functions. pseudo-random generators, and Fast
Randomizing Primality Tests. The latter tests are based on the
following observation:
Odd N = 3 5 7 9 11 13 15 17 19 21
2^(N-1) mod N = 1 1 1 4 1 1 4 1 1 4
Prime = 1 1 1 0 1 1 0 1 1 0
23 25 27 29 31 33 35 37 39 41 43 45 47 49 51
1 16 13 1 1 4 9 1 4 1 1 31 1 15 4
1 0 0 1 1 0 0 1 0 1 1 0 1 0 0
53 55 57 59 61 63 65 67 69 71 73 75 77 79 81
1 49 4 1 1 4 16 1 4 1 1 34 9 1 40
1 0 0 1 1 0 0 1 0 1 1 0 0 1 0
83 85 87 89 91 93 95 97 99 101 103 105 107 109 111
1 16 4 1 64 4 54 1 58 1 1 46 1 1 4
1 0 0 1 0 0 0 1 0 1 1 0 1 1 0
The above suggests (but naturally does not prove) the following FALSE
assertion:
Let N be an odd positive integer. Then:
N prime <=> 2^(N-1) mod N = 1.
Would that the assertion were true -- it would give us a fast primality
test. (What would that test be?)
The first counterexample is 341 = 11*31: 341
1
0
341 is called a 2-pseudo-prime.
Fortunately, while 341 is a 2-pseudo-prime (2^340 mod 341 = 1) it is not a
3-pseudo-prime, since 3^340 mod 341 = 56 <> 1.
So there is hope. In fact, if there is any integer a such that a^(N-1) mod
N <> 1, then it follows from group theory that for at least half the
integers x in the set {1,2,...,N-1}, x^(N-1) mod N <> 1.
Before going on, here is what is true of the above (false) assertion:
FERMAT'S LITTLE THEOREM: Let N be an odd positive integer.
Let a be a positive integer less than N. Then:
N prime => a^(N-1) mod N = 1.
:( Note that the above implication goes in only one direction.)
PROOF of Fermat's Little Theorem for the special case a=2:
For N = P an odd prime: (1+1)^P = 1^P + (P choose 1)*1^(P-1) +
(P choose 2)*1^(P-2) + ... + (P choose P)*1^(P-P).
Therefore,
2^P mod P = (1+1)^P mod P = (1^P + (P choose P)*1^0) mod P
= (1 + 1) mod P
= 2.
Since 2 is relatively prime to P, it has an inverse mod P.
Multiplying both sides by this inverse gives 2^(P-1) mod P = 1.
This proof for a=2 can be extended by induction to the general case
of 0 < a < P .
QED
Recall the definition of a GROUP G: it is a set that is closed under an
associative "multiplication" operation *, such that:
1. G contains an identity element 1: 1 satisfies 1*a = a*1 = a for all a in
G, and
2. Every a in G has an inverse (a^-1) such that
a*(a^-1) = (a^-1)*a = 1.
A subgroup H of G is a subset of G that forms a group under the (same)
operation *.
THEOREM: Let H be a subgroup of a finite group G. Then |H| divides |G|. In
other words, the number of elements in H divides the number of elements in G.
It follows that if G has even one element that is not in H, then H contains
at most half the elements of G.
In what follows, G = Z* sub N denotes the group of all positive integers
that are less than and relatively prime to N, under multiplication mod
N. H = subgroup of G consisting of all elements a of G such that
a^(N-1) mod N = 1. (You should check that H is a group!)
This leads us to an *improved* but unfortunately still incorrect suggestion
for a randomizing test for Primality.
Randomizing algorithms:
Generic randomizing algorithm:
INPUT: 1. an urn containing either:
1.1 all white balls,
or
1.2 an equal number of black and white balls, and
2. a positive integer k.
OUTPUT: if the urn contains all white balls, then definitely
output PROBABLY ALL WHITE;
if the urn contains equal numbers of black and white,
then probably output HALF WHITE HALf BLACK.
Probability of error is at most 1/2^k.
begin
Do k times:
Select a ball at random.
If the ball is black, return HALF WHITE HALf BLACK.
od
return PROBABLY ALL WHITE
end
Example:
Let N be a positive integer.
Let Z* sub N denote the group of all positive integers that are less than
and relatively prime to N, under multiplication mod N.
THEOREM: Z* sub N contains phi(N) elements, where phi(p) = p-1 for any
prime p, phi(p^k) = (p-1)*p^(k-1), and
phi(p1^k1 * ... * pi^ki) = phi(p1^k1)*...*phi(pi^ki).
It follows that if Z* sub N contains any element a such that
a^(N-1) mod N <> 1, then at least half the elements of Z* sub N satisfy
a^(N-1) mod N <> 1.
(Why?)
EXAMPLE: Let N = 15. Z* sub N = {1,2,4,7,8,11,13,14}.
phi(15) = phi(3)*phi(5) = 2*4 = 8, and so |Z* sub N| = phi(N) = 8.
The subgroup H of Z* sub N consisting of all elements a of Z* sub N such
that a^(N-1) mod N = 1 is H = {1,4,11,15}.
Z* sub N is the urn containing all white balls or at most half white balls.
A ball a is white iff a^(N-1) mod N = 1.
This suggests an improved randomizing algorithm for primality.
What is it?
Unfortunately, even this does not work. There are numbers called
pseudo-primes or Carmichael numbers: these are composite numbers for
which a^(N-1) mod N = 1 for all a in Z* sub N .
Indeed, there exist infinitely many Carmichael numbers. A lot is known
about them. For example, such numbers are all products of three
distinct primes.
ASIDE:
1729 = The Hardy-Ramanujan "Taxi" number is Carmichael number:
= 7*13*19
= least number expressible as sum of two positive integral
cubes in two different ways:
1729 = 9^3+10^3 = 1^3+12^3
Fortunately, there is an efficient test for Carmichael numbers, so modulo
this test, we have an efficient randomizing test for primality.
Let pi(N) = number of primes less than N.
Then pi(N) is asymptotic to N/(ln N), meaning that the ratio
pi(N)
lim --------- = 1
N -> infinity N/(ln N)
Typical notation: pi(N) ~ N/ln(N).
Application: Efficient generation of random n-bit primes.