recitation4.tex

%% This file was auto-generated by IPython.
%% Conversion from the original notebook file:
%% recitation4.ipynb
%%
\documentclass[11pt,english]{article}

%% This is the automatic preamble used by IPython.  Note that it does *not*
%% include a documentclass declaration. The documentclass is added at runtime
%% to the overall document.

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{ucs}
\usepackage[utf8x]{inputenc}

% needed for markdown enumerations to work
\usepackage{enumerate}

% Slightly bigger margins than the latex defaults
\usepackage{geometry}
\geometry{verbose,tmargin=3cm,bmargin=3cm,lmargin=2.5cm,rmargin=2.5cm}

% Define a few colors for use in code, links and cell shading
\usepackage{color}
\definecolor{orange}{cmyk}{0,0.4,0.8,0.2}
\definecolor{darkorange}{rgb}{.71,0.21,0.01}
\definecolor{darkgreen}{rgb}{.12,.54,.11}
\definecolor{myteal}{rgb}{.26, .44, .56}
\definecolor{gray}{gray}{0.45}
\definecolor{lightgray}{gray}{.95}
\definecolor{mediumgray}{gray}{.8}
\definecolor{inputbackground}{rgb}{.95, .95, .85}
\definecolor{outputbackground}{rgb}{.95, .95, .95}
\definecolor{traceback}{rgb}{1, .95, .95}

% Framed environments for code cells (inputs, outputs, errors, ...).  The
% various uses of \unskip (or not) at the end were fine-tuned by hand, so don't
% randomly change them unless you're sure of the effect it will have.
\usepackage{framed}

% remove extraneous vertical space in boxes
\setlength\fboxsep{0pt}

% codecell is the whole input+output set of blocks that a Code cell can
% generate.

% TODO: unfortunately, it seems that using a framed codecell environment breaks
% the ability of the frames inside of it to be broken across pages.  This
% causes at least the problem of having lots of empty space at the bottom of
% pages as new frames are moved to the next page, and if a single frame is too
% long to fit on a page, it will completely stop latex from compiling the
% document.  So unless we figure out a solution to this, we'll have to instead
% leave the codecell env. as empty.  I'm keeping the original codecell
% definition here (a thin vertical bar) for reference, in case we find a
% solution to the page break issue.

%% \newenvironment{codecell}{%
%%     \def\FrameCommand{\color{mediumgray} \vrule width 1pt \hspace{5pt}}%
%%    \MakeFramed{\vspace{-0.5em}}}
%%  {\unskip\endMakeFramed}

% For now, make this a no-op...
\newenvironment{codecell}{}

 \newenvironment{codeinput}{%
   \def\FrameCommand{\colorbox{inputbackground}}%
   \MakeFramed{\advance\hsize-\width \FrameRestore}}
 {\unskip\endMakeFramed}

\newenvironment{codeoutput}{%
   \def\FrameCommand{\colorbox{outputbackground}}%
   \vspace{-1.4em}
   \MakeFramed{\advance\hsize-\width \FrameRestore}}
 {\unskip\medskip\endMakeFramed}

\newenvironment{traceback}{%
   \def\FrameCommand{\colorbox{traceback}}%
   \MakeFramed{\advance\hsize-\width \FrameRestore}}
 {\endMakeFramed}

% Use and configure listings package for nicely formatted code
\usepackage{listingsutf8}
\lstset{
  language=python,
  inputencoding=utf8x,
  extendedchars=\true,
  aboveskip=\smallskipamount,
  belowskip=\smallskipamount,
  xleftmargin=2mm,
  breaklines=true,
  basicstyle=\small \ttfamily,
  showstringspaces=false,
  keywordstyle=\color{blue}\bfseries,
  commentstyle=\color{myteal},
  stringstyle=\color{darkgreen},
  identifierstyle=\color{darkorange},
  columns=fullflexible,  % tighter character kerning, like verb
}

% The hyperref package gives us a pdf with properly built
% internal navigation ('pdf bookmarks' for the table of contents,
% internal cross-reference links, web links for URLs, etc.)
\usepackage{hyperref}
\hypersetup{
  breaklinks=true,  % so long urls are correctly broken across lines
  colorlinks=true,
  urlcolor=blue,
  linkcolor=darkorange,
  citecolor=darkgreen,
  }

% hardcode size of all verbatim environments to be a bit smaller
\makeatletter
\g@addto@macro\@verbatim\small\topsep=0.5em\partopsep=0pt
\makeatother

% Prevent overflowing lines due to urls and other hard-to-break entities.
\sloppy

\begin{document}

\section{CS1001.py}

\subsection{Extended Introduction to Computer Science with Python,
Tel-Aviv University, Spring 2013}

\section{Recitation 4 - 4-8.4.2013}

\subsection{Last update: 3.4.2013}


\section{Reminder - \texttt{Big O} notation}

Let $f(x)$ and $g(x)$ be two function. Then \[
f(x) = O(g(x)) \; as \; x \to \infty 
\] If and only if there exist $M \ge 0 \;$ and $x_{0}\in \mathbb{R}$
such that \[
|f(x)| \le M|g(x)| \; \forall x>x_{0}
\]

\section{Time complexity hierarchy}

The most common time complexities we encounter are (\emph{c
\textgreater{} 1} is a real constant, *n \textgreater{}1 * is the size
of the input):

\begin{itemize}
\item
  Constant - $O(1)$
\item
  Logarithmic - $O(log(n))$
\item
  Root/fractional - $O(n^{1/c})$
\item
  Linear - $O(n)$
\item
  Loglinear - $O(n log(n))$
\item
  Polynomial - $O(n^{c})$
\item
  Exponential - $O(c^{n})$
\item
  Factorial - $O(n!)$
\end{itemize}
See also this list on
\href{http://en.wikipedia.org/wiki/Time\_complexity\#Table\_of\_common\_time\_complexities}{Wikipedia}.

\subsection{Size of the input}

\begin{itemize}
\item
  For a numerical input (factorization, prime numbers) the size of the
  input is the number of bits of the numerical input
\item
  For a list/vector input, the size is the number of elements
\item
  For a matrix?
\end{itemize}
\subsection{Examples}

\subsubsection{Constant, Linear, Loglinear, Polynomial}


\begin{codecell}
\begin{codeinput}
\begin{lstlisting}
from math import log

domain = range(1,100)
const = [10 for x in domain]
lin = [x for x in domain]
loglin = [x * log(x) for x in domain]
poly = [x ** 2 for x in domain]

# these lines are the plotting directives
fig = figure(figsize=(16,6))
ax = subplot(1,3,1)
ax.plot(domain,const)
ax.plot(domain,lin)
ax.legend(["const","lin"],loc=2);
ax = subplot(1,3,2)
ax.plot(domain,lin)
ax.plot(domain,loglin)
ax.legend(["lin","loglin"],loc=2);
ax = subplot(1,3,3)
ax.plot(domain,loglin)
ax.plot(domain,poly)
ax.legend(["loglin","poly"],loc=2);
\end{lstlisting}
\end{codeinput}
\begin{codeoutput}
\begin{center}
\includegraphics[width=0.7\textwidth]{recitation4_files/recitation4_fig_00.png}
\par
\end{center}
\end{codeoutput}
\end{codecell}
\subsection{Exercises}

\subsubsection{Transitivity}

If \$ f(n)=O(g(n)); \$ and \$ g(n) = O(h(n)); \$ then \$ f = O(h(n)); \$
?

\subsubsection{Symmetry}

If $f=O(g)\;$ then $g=O(f)$? Or $g \ne O(f)$?

\subsubsection{Series Loops}

Let $f_1 = O(g_1)\;$ and $f_2=O(g_2)$.

Show that $f_1 + f_2 = O(g_1 + g_2)$.

This relates to two consecutive loops:

\begin{verbatim}
for i in range(len(list1)):
    print i
for i in range(len(list2)):
    print i
\end{verbatim}
\subsubsection{Parallel Loops}

Show that $f_1 \cdot f_2 = O(g_1 \cdot g_2)$.

This relates to independent nested loops:

\begin{verbatim}
for i in range(len(list1)):
    print i
    for j in range(len(list2)):
        print j
\end{verbatim}
\subsubsection{Maximum}

Show that $_1 + f_2 + ... + f_k = O(f_max)$. That is, in a finite
constant sum of functions, the dominate function defines the growth
rate.

A private case is that of a polynomial.

\subsubsection{Dependent nested loops}

For exmaple,

\begin{verbatim}
for i in range(len(list1)):
    for j in range(i):
        print i, j
\end{verbatim}
Prove:

\begin{itemize}
\item
  $\sum_{i=1}^{n}{i} = O(n^2)$ - the arithmetic series
\item
  $\sum_{i=1}^{n}{2^i} = O(2^n)$ - the geometric series
\end{itemize}

\section{Primality testing}


\subsubsection{\href{http://en.wikipedia.org/wiki/Fermat's\_little\_theorem}{Fermat's
little theorem}}

If $p$ is a prime $a$ is a natural number such that $1\le a < p\;$, then
$a^{p-1} = 1 \; (mod \; p)$.

\subsubsection{Probabilistic test with Fermat's little theorem}

We can use this to create a primality test for \emph{p}.

\begin{codecell}
\begin{codeinput}
\begin{lstlisting}
from random import randrange
def is_prime(p):
    """probabilistic test for p's compositeness"""
    for i in range(100):
        a = randrange(1, p-1) # a is a random integer in [1..p-1]
        if pow(a, p-1, p) != 1: # this takes O(n^3) = O((log2 p)^3)
            #print(p, "is composite")
            return False
    #print(p, "is prime")
    return True # we get here if no compositeness witness was found
\end{lstlisting}
\end{codeinput}
\end{codecell}
\begin{codecell}
\begin{codeinput}
\begin{lstlisting}
is_prime(11)
\end{lstlisting}
\end{codeinput}
\begin{codeoutput}
\begin{verbatim}
True
\end{verbatim}
\end{codeoutput}
\end{codecell}
\begin{codecell}
\begin{codeinput}
\begin{lstlisting}
is_prime(190125101)
\end{lstlisting}
\end{codeinput}
\begin{codeoutput}
\begin{verbatim}
True
\end{verbatim}
\end{codeoutput}
\end{codecell}
\subsubsection{Notes}

\begin{itemize}
\item
  \texttt{pow(a,b,c)} is equivalent to $a^b \; mod \; c$, only it is
  more efficient by use of \emph{iterated squaring}.
\item
  The \emph{False Positive} rate - the probablity the function returns
  \texttt{True} when it should return \texttt{False} - is less than
  $0.25^{100}$ (Miller-Rabin).
\end{itemize}

\subsubsection{Testing the prime number theorem}

\paragraph{The theorem}

Define by $\pi(x)$ the number of prime numbersless than or equal to $x$.
Then the
\href{http://en.wikipedia.org/wiki/Prime\_number\_theorem}{prime number
theorem} states that

\[
\pi(x) \thicksim \frac{x}{log(x)}
\]

for large $x$.

Since $n$ the number of bits in $x$ is $O(log(x))\;$ this translates to
\[
\pi(x) = O(1/n)
\]

And we can say that \textgreater{} A number with \emph{n} bits is prime
with a probability of $O(1/n)$.

We'd like to check this, but for large \emph{n} there are too many
($2^{n-1}$) numbers to check. So we will use \emph{sampling}.

\begin{codecell}
\begin{codeinput}
\begin{lstlisting}
def prob_prime(n):
    """evaluate the probability of an n-bit long integer to be prime"""
    count = 0
    sample_size = 10 ** 5
    for i in range(sample_size):
        p = random.randint(2 ** (n-1), 2 ** n-1)
        count += is_prime(p)
    return count/sample_size
\end{lstlisting}
\end{codeinput}
\end{codecell}
\begin{codecell}
\begin{codeinput}
\begin{lstlisting}
prob_prime(20)
\end{lstlisting}
\end{codeinput}
\begin{codeoutput}
\begin{verbatim}
0.07521
\end{verbatim}
\end{codeoutput}
\end{codecell}
\begin{codecell}
\begin{codeinput}
\begin{lstlisting}
1/20
\end{lstlisting}
\end{codeinput}
\begin{codeoutput}
\begin{verbatim}
0.05
\end{verbatim}
\end{codeoutput}
\end{codecell}
\section{Diffie-Hellman}

A Khan Academy video that illustrates the Diffie-Hellman key exchange:

See the paper
\href{http://www.cs.tau.ac.il/~bchor/diffie-hellman.pdf}{New directions
in cryptography}.

This is the protocol:

\begin{codecell}
\begin{codeinput}
\begin{lstlisting}
def DH_exchange(p):
    """ generates a shared DH key """
    g = randrange(1,p-1)
    a = randrange(1,p-1) # Alice's secret
    b = randrange(1,p-1) # Bob's secret
    x = pow(g,a,p) 
    y = pow(g,b,p)
    key_A = pow(y,a,p)
    key_B = pow(x,b,p)
    return g, a, b, x, y, key_A, key_B
\end{lstlisting}
\end{codeinput}
\end{codecell}
\begin{codecell}
\begin{codeinput}
\begin{lstlisting}
DH_exchange(190125101)
\end{lstlisting}
\end{codeinput}
\begin{codeoutput}
\begin{verbatim}
(130721310, 61963609, 1775050, 132736567, 143446917, 74182194, 74182194)
\end{verbatim}
\end{codeoutput}
\end{codecell}
\begin{codecell}
\begin{codeinput}
\begin{lstlisting}
DH_exchange(833648000993161193752610727299)
\end{lstlisting}
\end{codeinput}
\begin{codeoutput}
\begin{verbatim}
(225405422835827732918401478004,
 153883981994400043514132897779,
 556710940458985113442266962618,
 620358857758647613746179753310,
 479744267228387852844588852918,
 610421506532174772126394293202,
 610421506532174772126394293202)
\end{verbatim}
\end{codeoutput}
\end{codecell}
Now let's try and break it:

\begin{codecell}
\begin{codeinput}
\begin{lstlisting}
def crack_DH(p, g, x):
    """find secret "a" that satisfies g**a%p == x
    Not feasible for large p"""
    for a in range(1,p-1):
        if a % 100000 == 0: 
            print("Iteration",a) # progress bar
        if pow(g,a,p) == x:
            return a
    return None
\end{lstlisting}
\end{codeinput}
\end{codecell}
We need a function that finds primes:

\begin{codecell}
\begin{codeinput}
\begin{lstlisting}
def find_prime(n):
    """ find random n-bit long prime (no leading zeros: 2**(n-1)<= N < 2**n )"""
    while True: #here we're optimistic, but actually we have a good reason to be:
                 # after O(1/n) iterations we expect to find a prime and halt
        candidate = randrange(2**(n - 1), 2**n)
        if is_prime(candidate):
            return candidate
\end{lstlisting}
\end{codeinput}
\end{codecell}
\begin{codecell}
\begin{codeinput}
\begin{lstlisting}
find_prime(10)
\end{lstlisting}
\end{codeinput}
\begin{codeoutput}
\begin{verbatim}
809
\end{verbatim}
\end{codeoutput}
\end{codecell}
\begin{codecell}
\begin{codeinput}
\begin{lstlisting}
find_prime(100)
\end{lstlisting}
\end{codeinput}
\begin{codeoutput}
\begin{verbatim}
867229771910197365894912239707
\end{verbatim}
\end{codeoutput}
\end{codecell}
Running with a 10-bit prime:

\begin{codecell}
\begin{codeinput}
\begin{lstlisting}
p = find_prime(10)
print(p,log(p,2))
g,a,b,x,y,key_A,key_B = DH_exchange(p)
print('g',g,'a',a,'b',b,'x',x,'y',y,'key_A',key_A,'key_B',key_B)
print('a',crack_DH(p,g,x))
\end{lstlisting}
\end{codeinput}
\begin{codeoutput}
\begin{verbatim}
571 9.157346935362844
g 323 a 376 b 467 x 271 y 353 key_A 350 key_B 350
a 15
\end{verbatim}
\end{codeoutput}
\end{codecell}
Running with a 16-bit prime:

\begin{codecell}
\begin{codeinput}
\begin{lstlisting}
p = find_prime(16)
print(p,log(p,2))
g,a,b,x,y,key_A,key_B = DH_exchange(p)
print('g',g,'a',a,'b',b,'x',x,'y',y,'key_A',key_A,'key_B',key_B)
print('a',crack_DH(p,g,x))
\end{lstlisting}
\end{codeinput}
\begin{codeoutput}
\begin{verbatim}
43913 15.422360477832592
g 38791 a 18986 b 43896 x 19571 y 18163 key_A 32540 key_B 32540
a
\end{verbatim}
\begin{verbatim}
18986
\end{verbatim}
\end{codeoutput}
\end{codecell}
\begin{codecell}
\begin{codeinput}
\begin{lstlisting}
p = find_prime(24)
print(p,log(p,2))
g,a,b,x,y,key_A,key_B = DH_exchange(p)
print('g',g,'a',a,'b',b,'x',x,'y',y,'key_A',key_A,'key_B',key_B)
print('a',crack_DH(p,g,x))
\end{lstlisting}
\end{codeinput}
\begin{codeoutput}
\begin{verbatim}
14410853 23.78065239753461
g 336845 a 5626365 b 10932040 x 2437765 y 286640 key_A 7725816 key_B 7725816
Iteration
\end{verbatim}
\begin{verbatim}
100000
Iteration
\end{verbatim}
\begin{verbatim}
200000
Iteration
\end{verbatim}
\begin{verbatim}
300000
Iteration
\end{verbatim}
\begin{verbatim}
400000
Iteration
\end{verbatim}
\begin{verbatim}
500000
Iteration
\end{verbatim}
\begin{verbatim}
600000
Iteration
\end{verbatim}
\begin{verbatim}
700000
Iteration
\end{verbatim}
\begin{verbatim}
800000
Iteration
\end{verbatim}
\begin{verbatim}
900000
Iteration
\end{verbatim}
\begin{verbatim}
1000000
Iteration
\end{verbatim}
\begin{verbatim}
1100000
Iteration
\end{verbatim}
\begin{verbatim}
1200000
Iteration
\end{verbatim}
\begin{verbatim}
1300000
Iteration
\end{verbatim}
\begin{verbatim}
1400000
Iteration
\end{verbatim}
\begin{verbatim}
1500000
Iteration
\end{verbatim}
\begin{verbatim}
1600000
Iteration
\end{verbatim}
\begin{verbatim}
1700000
Iteration
\end{verbatim}
\begin{verbatim}
1800000
Iteration
\end{verbatim}
\begin{verbatim}
1900000
Iteration
\end{verbatim}
\begin{verbatim}
2000000
Iteration
\end{verbatim}
\begin{verbatim}
2100000
Iteration
\end{verbatim}
\begin{verbatim}
2200000
Iteration
\end{verbatim}
\begin{verbatim}
2300000
Iteration
\end{verbatim}
\begin{verbatim}
2400000
Iteration
\end{verbatim}
\begin{verbatim}
2500000
Iteration
\end{verbatim}
\begin{verbatim}
2600000
Iteration
\end{verbatim}
\begin{verbatim}
2700000
Iteration
\end{verbatim}
\begin{verbatim}
2800000
Iteration
\end{verbatim}
\begin{verbatim}
2900000
Iteration
\end{verbatim}
\begin{verbatim}
3000000
Iteration
\end{verbatim}
\begin{verbatim}
3100000
Iteration
\end{verbatim}
\begin{verbatim}
3200000
Iteration
\end{verbatim}
\begin{verbatim}
3300000
Iteration
\end{verbatim}
\begin{verbatim}
3400000
Iteration
\end{verbatim}
\begin{verbatim}
3500000
Iteration
\end{verbatim}
\begin{verbatim}
3600000
Iteration
\end{verbatim}
\begin{verbatim}
3700000
Iteration
\end{verbatim}
\begin{verbatim}
3800000
Iteration
\end{verbatim}
\begin{verbatim}
3900000
Iteration
\end{verbatim}
\begin{verbatim}
4000000
Iteration
\end{verbatim}
\begin{verbatim}
4100000
Iteration
\end{verbatim}
\begin{verbatim}
4200000
Iteration
\end{verbatim}
\begin{verbatim}
4300000
Iteration
\end{verbatim}
\begin{verbatim}
4400000
Iteration
\end{verbatim}
\begin{verbatim}
4500000
Iteration
\end{verbatim}
\begin{verbatim}
4600000
Iteration
\end{verbatim}
\begin{verbatim}
4700000
Iteration
\end{verbatim}
\begin{verbatim}
4800000
Iteration
\end{verbatim}
\begin{verbatim}
4900000
Iteration
\end{verbatim}
\begin{verbatim}
5000000
Iteration
\end{verbatim}
\begin{verbatim}
5100000
Iteration
\end{verbatim}
\begin{verbatim}
5200000
Iteration
\end{verbatim}
\begin{verbatim}
5300000
Iteration
\end{verbatim}
\begin{verbatim}
5400000
Iteration
\end{verbatim}
\begin{verbatim}
5500000
Iteration
\end{verbatim}
\begin{verbatim}
5600000
a
\end{verbatim}
\begin{verbatim}
5626365
\end{verbatim}
\end{codeoutput}
\end{codecell}
\subsection{Fin}

This notebook is part of the
\href{http://tau-cs1001-py.wikidot.com/}{Extended introduction to
computer science} course at Tel-Aviv University.

The notebook was written using Python 3.2 and IPython 0.13.1.

The code is available at
\url{https://raw.github.com/yoavram/CS1001.py/master/recitation4.ipynb}.

The notebook can be viewed online at
\url{http://nbviewer.ipython.org/urls/raw.github.com/yoavram/CS1001.py/master/recitation4.ipynb}.

This work is licensed under a
\href{http://creativecommons.org/licenses/by-sa/3.0/}{Creative Commons
Attribution-ShareAlike 3.0 Unported License}.

\end{document}