CS 15-451      Analysis of Algorithms     18 November 2003
                                             Manuel & Avrim Blum

Today: number theoretic algorithms,
               randomizing algorithms.

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.)

Let N be a positive integer.
Let Z* sub N denote the set of all positive integers less than N that are 
relatively prime to N.

THEOREM: Z* sub N under the binary operation of multiplication mod N
forms a group.  Z* sub N contains phi(N) elements, where phi is
defined as follows: for any prime P, phi(P) = P-1,

phi(P^k) = (P-1)*P^(k-1), and
phi(P1^k1 * ... * Pl^kl) = phi(P1^k1)*...*phi(Pl^kl).

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?)


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.

What do random factored integers look like?

How to generate random factored (into primes) integers.

How to generate random factored (into cycles) permutations.



A problem that is NP-hard but not obviously in NP:

ZEROS OF A MULTIVARIATE POLYNOMIAL (ZMP)
INSTANCE: a multivariate poly with integer coefficients
QUESTION: does this poly have a zero in the Real Numbers?

EXAMPLE: F(x) = x^2-2 has a zero, but the zero is irrational. Makes it hard 
to guess a root.

On the other hand, there is a simple poly time reduction f from 3SAT to ZMP:
X -> x^2.  X' -> (1-x)^2.  T -> 0. F -> 1.  AND -> +.  OR -> *.
{X, Y, Z'} -> x^2*y^2*(1-z)^2.

{X, Y, Z'} {X'}  ->  x^2*y^2*(1-z)^2 + (1-x)^2.
A satisfying truth assignment for the clauses
(such as X=F Y=T Z=T or F)
maps to a zero for the corresponding polynomial
(in this case, x=1 y=0 z=0 or 1)
and vice-versa.

In general, the question whether two Boolean Formulas are equivalent is 
co-NP hard. (Why?)

The corresponding question whether two multivariate polynomials are equal 
is SURPRISINGLY easy. It can be decided in randomized polynomial time.

Schwartz's Theorem: If f(x, y, z, ...) is a nontrivial polynomial in n
varables, integer coefficients, degree d, then f can be zero on an at
most HALF of the integer points in any 2d x 2d x 2d x ... n-cube set
of points such as the points with x,y,z,... in {0, 1, ..., d},

Here, degree d means that the sum of the degrees of each product term
is at most d. for example 7*x*x*y is of degree 3, as is 7*(x^2)*y -
(z^3) + 5, which has two product terms each of degree 3 and one
constant term of degree 0.

The proof is by induction on n. It is trivial for the case that n=1:
any nontrivial polynomial of degree d in one variable has at most d
zeroes. For example, a quadratic a + bx + cx^2 has at most 2
zeroes. For larger n, write f aa a polynomial in one variable whose
coefficients are polynomials in the other variables. For example,
f(x,y) = a(x) + b(x)*y + c(x)*y^2.

Reducing search to decision problems.

Matching in bipartite graphs.

Definition of the Tutte matrix.

Tutte's Theorem: A graph has a perfect matching iff the determinant of
the Tutte matrix -- a multivariate polynomial -- is NOT identically
zero.  Matching in general (undirected) graphs.

It follows that there exists a randomizing poly-time algorithm to find 
matchings in general graphs.