Algorithms and Computational Complexity

Chapter 0. Prologue

Johann Gutenberg: Typography

Al Khwarizmi: Indian numerals

Precise, unambiguous, mechanical, efficient, correct: algorithms.

Fibonacci Sequence

Formally

$F_n=\left\{ \begin{aligned} &F_{n-1}+F_{n-2}&n>1\\ &1&n=1\\ &0&n=0 \end{aligned} \right.$

An exponential algorithm.


Let $T(n)$ be the number of computer steps needed to compute fib1(n).

For $n\le1$

$T(n)\le2$

For $n>1$

$T(n)=T(n-1)+T(n-2)+3$

By induction, for all $n \in \N$

$T(n)\ge F_n\\ T(n)=T(n-1)+T(n-2)+3\ge F_{n-1}+F_{n-2}=F_n$


Arithmetic operations on arbitrarily large numbers cannot possibly be performed in a single, constant-time step.

It therefore makes more sense to seek an machine-independent characterization
of an algorithm’s efficiency.

Big-$O$ notation

$f(n)$ and $g(n)$ are the running times of two algorithms on inputs of size $n$.

Let $f(n)$ and $g(n)$ be functions from positive integers to positive reals. We say $f=O(g)$ (which means that “f grows no faster than g”) if there is a constant $c>0$ such that $f(n)\le c\cdot g(n)$.

$f=O(g)$ is a very loose analog of “$f\le g$.” It differs from the usual notion of $\le$ because of the constant $c$, so that for instance $10n=O(n)$.

Other similar notations

We also define analogs of $\ge $ and $=$ as follows:

• $f=\Omega(g)$ means $g=O(f)$.
• $f=\Theta(g)$ means $f=O(g)$ and $f=\Omega (g)$.

Simple rules


Chapter 1. Algorithms with Numbers

数论算法

Factoring: Given a number $N$, express it as a product of its prime factors.（质因数分解）

Primality: Given a number $N$, determine whether it is a prime.（素性判断, AKS Test）

Assumption: Factoring is HARD

Basic arithmetic

Prove that in the big-$O$ notation, the base is irrelevant, which means that,

$\Theta (f(N)\cdot \log_a N )=f(N)\cdot \log_b N$

Proof

$O(f(N)\cdot C)=f(N)\log N$


Addition

The sum of any three single-digit numbers is at most two digits long for any $b\ge2$

$3\times (b-1) \le b^2-1$

This simple rule gives us a way to add two numbers in any base: align their right-hand ends, and then perform a single right-to-left pass in which the sum is computed digit by digit, maintaining the overflow as a carry. Since we know each individual sum is a two-digit number, the carry is always a single digit, and so at any given step, three single-digit numbers are added.

Given two binary numbers x and y, how long does our algorithm take to add them?

$O(n)$

Is there a faster algorithm?

Optimal!

A single instruction we can add integers whose size in bits is within the word length of today’s computer – 64 perhaps. But it is often useful and necessary to handle numbers much larger than this, perhaps several thousand bits long.



Modular arithmetic


Two’s complement



结合律、交换律和分配律。

Modular Addition


Modular multiplication

Modular exponentiation

Euclid’s algorithm for greatest common divisor

Modular inverse

We say $x$ is the multiplicative inverse of a modulo $N$ if $ax\equiv 1$ mod $N$.

There can be at most one such $x$ modulo $N$ with $ax\equiv 1$ mod $N$, denoted by $a^{-1}$.

If there are two distinct $x$ and $y$ satisfying $ax \equiv 1$ mod $N$ and $ay\equiv 1$ mod $N$. $x\not\equiv y$ mod $N$.

$a(x-y)\equiv 0 \pmod{N}$

So $a=0$ mod $N$.


Primality Testing

$S=\{1,2,\cdots,p-1\}=\{a\cdot 1\bmod p, a\cdot 2 \bmod p,\cdots,a\cdot (p-1)\bmod p\}$

We can multiply together its elements in each of these representations to get

$(p-1)!\equiv a^{p-1}\cdot(p-1)!\pmod{p}$

$(p-1)!$ is relatively prime to $p$.






Lagrange’s prime number theorem. Let $\pi(x)$ be the number of primes $\le x$. Then $\pi(x)\approx x/(\ln x)$, or more precisely,

$\lim_{x\to \infin} \frac{\pi(x)}{x/\ln x}=1$

比较丰富，所以随便挑一个 $n$ 位数 $N$，如果通过素性测试，那么输出 $N$。

选到的概率为 $\pi(N)/N=\ln N=O(n)$，$O(n)$ 次测试。

Cryptography


BS 算法



The Rivest-Shamir-Adelman (RSA) cryptosystem

An example of public-key cryptography

• Anybody can send a message to anybody else using publicly available information, rather like addresses or phone numbers.
• Each person has a public key known to the whole world and a secret key known only to him- or herself.
• When Alice wants to send message x to Bob, she encodes it using his public key.
• Bob decrypts it using his secret key, to retrieve x.
• Eve is welcome to see as many encrypted messages for Bob as she likes, but she will not be able to decode them, under certain simple assumptions.

Property


$ed=1\pmod{(p-1)(q-1)}$, we can write

$ed=1+k(p-1)(q-1)$

$x^{ed}-x=x(x^{k(p-1)(q-1)}-1)=x((x^{p-1})^{k(q-1)}-1)$

如果 mod $p$，那么就会发现等于 0，mod $q$ 也是如此。

因此 $(x^e)^d\equiv x$ mod $N$.


Universal Hashing






Chapter 2. Divide-and-conquer algorithms





Recurrence relations

Master theorem

$T(n) = a T\left(\frac{n}{b}\right)+f(n)\qquad \forall n > b$

$T(n) = \begin{cases}\Theta(n^{\log_b a}) & f(n) = O(n^{\log_b a-\epsilon}) \\ \Theta(f(n)) & f(n) = \Omega(n^{\log_b a+\epsilon}) \\ \Theta(n^{\log_b a}\log^{k+1} n) & f(n)=\Theta(n^{\log_b a}\log^k n),k\ge 0 \end{cases}$

strassen乘法

$p\iff q$