Created
January 31, 2014 07:20
-
-
Save anonymous/8727845 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| % Header, overrides base | |
| % Make sure that the sphinx doc style knows who it inherits from. | |
| \def\sphinxdocclass{article} | |
| % Declare the document class | |
| \documentclass[letterpaper,10pt,english]{c:/python27/lib/site-packages/sphinx/texinputs/sphinxhowto} | |
| % Imports | |
| \usepackage[utf8]{inputenc} | |
| \DeclareUnicodeCharacter{00A0}{\\nobreakspace} | |
| \usepackage[T1]{fontenc} | |
| \usepackage{babel} | |
| \usepackage{times} | |
| \usepackage{import} | |
| \usepackage[Bjarne]{c:/python27/lib/site-packages/sphinx/texinputs/fncychap} | |
| \usepackage{longtable} | |
| \usepackage{c:/python27/lib/site-packages/sphinx/texinputs/sphinx} | |
| \usepackage{multirow} | |
| \usepackage{amsmath} | |
| \usepackage{amssymb} | |
| \usepackage{ucs} | |
| \usepackage{enumerate} | |
| % Used to make the Input/Output rules follow around the contents. | |
| \usepackage{needspace} | |
| % Pygments requirements | |
| \usepackage{fancyvrb} | |
| \usepackage{color} | |
| % ansi colors additions | |
| \definecolor{darkgreen}{rgb}{.12,.54,.11} | |
| \definecolor{lightgray}{gray}{.95} | |
| \definecolor{brown}{rgb}{0.54,0.27,0.07} | |
| \definecolor{purple}{rgb}{0.5,0.0,0.5} | |
| \definecolor{darkgray}{gray}{0.25} | |
| \definecolor{lightred}{rgb}{1.0,0.39,0.28} | |
| \definecolor{lightgreen}{rgb}{0.48,0.99,0.0} | |
| \definecolor{lightblue}{rgb}{0.53,0.81,0.92} | |
| \definecolor{lightpurple}{rgb}{0.87,0.63,0.87} | |
| \definecolor{lightcyan}{rgb}{0.5,1.0,0.83} | |
| % Needed to box output/input | |
| \usepackage{tikz} | |
| \usetikzlibrary{calc,arrows,shadows} | |
| \usepackage[framemethod=tikz]{mdframed} | |
| \usepackage{alltt} | |
| % Used to load and display graphics | |
| \usepackage{graphicx} | |
| \graphicspath{ {figs/} } | |
| \usepackage[Export]{adjustbox} % To resize | |
| % used so that images for notebooks which have spaces in the name can still be included | |
| \usepackage{grffile} | |
| % For formatting output while also word wrapping. | |
| \usepackage{listings} | |
| \lstset{breaklines=true} | |
| \lstset{basicstyle=\small\ttfamily} | |
| \def\smaller{\fontsize{9.5pt}{9.5pt}\selectfont} | |
| %Pygments definitions | |
| \makeatletter | |
| \def\PY@reset{\let\PY@it=\relax \let\PY@bf=\relax% | |
| \let\PY@ul=\relax \let\PY@tc=\relax% | |
| \let\PY@bc=\relax \let\PY@ff=\relax} | |
| \def\PY@tok#1{\csname PY@tok@#1\endcsname} | |
| \def\PY@toks#1+{\ifx\relax#1\empty\else% | |
| \PY@tok{#1}\expandafter\PY@toks\fi} | |
| \def\PY@do#1{\PY@bc{\PY@tc{\PY@ul{% | |
| \PY@it{\PY@bf{\PY@ff{#1}}}}}}} | |
| \def\PY#1#2{\PY@reset\PY@toks#1+\relax+\PY@do{#2}} | |
| \expandafter\def\csname PY@tok@gd\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.63,0.00,0.00}{##1}}} | |
| \expandafter\def\csname PY@tok@gu\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.50,0.00,0.50}{##1}}} | |
| \expandafter\def\csname PY@tok@gt\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.00,0.27,0.87}{##1}}} | |
| \expandafter\def\csname PY@tok@gs\endcsname{\let\PY@bf=\textbf} | |
| \expandafter\def\csname PY@tok@gr\endcsname{\def\PY@tc##1{\textcolor[rgb]{1.00,0.00,0.00}{##1}}} | |
| \expandafter\def\csname PY@tok@cm\endcsname{\let\PY@it=\textit\def\PY@tc##1{\textcolor[rgb]{0.25,0.50,0.50}{##1}}} | |
| \expandafter\def\csname PY@tok@vg\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.10,0.09,0.49}{##1}}} | |
| \expandafter\def\csname PY@tok@m\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.40,0.40,0.40}{##1}}} | |
| \expandafter\def\csname PY@tok@mh\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.40,0.40,0.40}{##1}}} | |
| \expandafter\def\csname PY@tok@go\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.53,0.53,0.53}{##1}}} | |
| \expandafter\def\csname PY@tok@ge\endcsname{\let\PY@it=\textit} | |
| \expandafter\def\csname PY@tok@vc\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.10,0.09,0.49}{##1}}} | |
| \expandafter\def\csname PY@tok@il\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.40,0.40,0.40}{##1}}} | |
| \expandafter\def\csname PY@tok@cs\endcsname{\let\PY@it=\textit\def\PY@tc##1{\textcolor[rgb]{0.25,0.50,0.50}{##1}}} | |
| \expandafter\def\csname PY@tok@cp\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.74,0.48,0.00}{##1}}} | |
| \expandafter\def\csname PY@tok@gi\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.00,0.63,0.00}{##1}}} | |
| \expandafter\def\csname PY@tok@gh\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.00,0.50}{##1}}} | |
| \expandafter\def\csname PY@tok@ni\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.60,0.60,0.60}{##1}}} | |
| \expandafter\def\csname PY@tok@nl\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.63,0.63,0.00}{##1}}} | |
| \expandafter\def\csname PY@tok@nn\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.00,1.00}{##1}}} | |
| \expandafter\def\csname PY@tok@no\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.53,0.00,0.00}{##1}}} | |
| \expandafter\def\csname PY@tok@na\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.49,0.56,0.16}{##1}}} | |
| \expandafter\def\csname PY@tok@nb\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.00,0.50,0.00}{##1}}} | |
| \expandafter\def\csname PY@tok@nc\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.00,1.00}{##1}}} | |
| \expandafter\def\csname PY@tok@nd\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.67,0.13,1.00}{##1}}} | |
| \expandafter\def\csname PY@tok@ne\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.82,0.25,0.23}{##1}}} | |
| \expandafter\def\csname PY@tok@nf\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.00,0.00,1.00}{##1}}} | |
| \expandafter\def\csname PY@tok@si\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.73,0.40,0.53}{##1}}} | |
| \expandafter\def\csname PY@tok@s2\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.73,0.13,0.13}{##1}}} | |
| \expandafter\def\csname PY@tok@vi\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.10,0.09,0.49}{##1}}} | |
| \expandafter\def\csname PY@tok@nt\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.50,0.00}{##1}}} | |
| \expandafter\def\csname PY@tok@nv\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.10,0.09,0.49}{##1}}} | |
| \expandafter\def\csname PY@tok@s1\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.73,0.13,0.13}{##1}}} | |
| \expandafter\def\csname PY@tok@sh\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.73,0.13,0.13}{##1}}} | |
| \expandafter\def\csname PY@tok@sc\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.73,0.13,0.13}{##1}}} | |
| \expandafter\def\csname PY@tok@sx\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.00,0.50,0.00}{##1}}} | |
| \expandafter\def\csname PY@tok@bp\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.00,0.50,0.00}{##1}}} | |
| \expandafter\def\csname PY@tok@c1\endcsname{\let\PY@it=\textit\def\PY@tc##1{\textcolor[rgb]{0.25,0.50,0.50}{##1}}} | |
| \expandafter\def\csname PY@tok@kc\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.50,0.00}{##1}}} | |
| \expandafter\def\csname PY@tok@c\endcsname{\let\PY@it=\textit\def\PY@tc##1{\textcolor[rgb]{0.25,0.50,0.50}{##1}}} | |
| \expandafter\def\csname PY@tok@mf\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.40,0.40,0.40}{##1}}} | |
| \expandafter\def\csname PY@tok@err\endcsname{\def\PY@bc##1{\setlength{\fboxsep}{0pt}\fcolorbox[rgb]{1.00,0.00,0.00}{1,1,1}{\strut ##1}}} | |
| \expandafter\def\csname PY@tok@kd\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.50,0.00}{##1}}} | |
| \expandafter\def\csname PY@tok@ss\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.10,0.09,0.49}{##1}}} | |
| \expandafter\def\csname PY@tok@sr\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.73,0.40,0.53}{##1}}} | |
| \expandafter\def\csname PY@tok@mo\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.40,0.40,0.40}{##1}}} | |
| \expandafter\def\csname PY@tok@kn\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.50,0.00}{##1}}} | |
| \expandafter\def\csname PY@tok@mi\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.40,0.40,0.40}{##1}}} | |
| \expandafter\def\csname PY@tok@gp\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.00,0.50}{##1}}} | |
| \expandafter\def\csname PY@tok@o\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.40,0.40,0.40}{##1}}} | |
| \expandafter\def\csname PY@tok@kr\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.50,0.00}{##1}}} | |
| \expandafter\def\csname PY@tok@s\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.73,0.13,0.13}{##1}}} | |
| \expandafter\def\csname PY@tok@kp\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.00,0.50,0.00}{##1}}} | |
| \expandafter\def\csname PY@tok@w\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.73,0.73,0.73}{##1}}} | |
| \expandafter\def\csname PY@tok@kt\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.69,0.00,0.25}{##1}}} | |
| \expandafter\def\csname PY@tok@ow\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.67,0.13,1.00}{##1}}} | |
| \expandafter\def\csname PY@tok@sb\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.73,0.13,0.13}{##1}}} | |
| \expandafter\def\csname PY@tok@k\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.50,0.00}{##1}}} | |
| \expandafter\def\csname PY@tok@se\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.73,0.40,0.13}{##1}}} | |
| \expandafter\def\csname PY@tok@sd\endcsname{\let\PY@it=\textit\def\PY@tc##1{\textcolor[rgb]{0.73,0.13,0.13}{##1}}} | |
| \def\PYZbs{\char`\\} | |
| \def\PYZus{\char`\_} | |
| \def\PYZob{\char`\{} | |
| \def\PYZcb{\char`\}} | |
| \def\PYZca{\char`\^} | |
| \def\PYZam{\char`\&} | |
| \def\PYZlt{\char`\<} | |
| \def\PYZgt{\char`\>} | |
| \def\PYZsh{\char`\#} | |
| \def\PYZpc{\char`\%} | |
| \def\PYZdl{\char`\$} | |
| \def\PYZhy{\char`\-} | |
| \def\PYZsq{\char`\'} | |
| \def\PYZdq{\char`\"} | |
| \def\PYZti{\char`\~} | |
| % for compatibility with earlier versions | |
| \def\PYZat{@} | |
| \def\PYZlb{[} | |
| \def\PYZrb{]} | |
| \makeatother | |
| %Set pygments styles if needed... | |
| \definecolor{nbframe-border}{rgb}{0.867,0.867,0.867} | |
| \definecolor{nbframe-bg}{rgb}{0.969,0.969,0.969} | |
| \definecolor{nbframe-in-prompt}{rgb}{0.0,0.0,0.502} | |
| \definecolor{nbframe-out-prompt}{rgb}{0.545,0.0,0.0} | |
| \newenvironment{ColorVerbatim} | |
| {\begin{mdframed}[% | |
| roundcorner=1.0pt, % | |
| backgroundcolor=nbframe-bg, % | |
| userdefinedwidth=1\linewidth, % | |
| leftmargin=0.1\linewidth, % | |
| innerleftmargin=0pt, % | |
| innerrightmargin=0pt, % | |
| linecolor=nbframe-border, % | |
| linewidth=1pt, % | |
| usetwoside=false, % | |
| everyline=true, % | |
| innerlinewidth=3pt, % | |
| innerlinecolor=nbframe-bg, % | |
| middlelinewidth=1pt, % | |
| middlelinecolor=nbframe-bg, % | |
| outerlinewidth=0.5pt, % | |
| outerlinecolor=nbframe-border, % | |
| needspace=0pt | |
| ]} | |
| {\end{mdframed}} | |
| \newenvironment{InvisibleVerbatim} | |
| {\begin{mdframed}[leftmargin=0.1\linewidth,innerleftmargin=3pt,innerrightmargin=3pt, userdefinedwidth=1\linewidth, linewidth=0pt, linecolor=white, usetwoside=false]} | |
| {\end{mdframed}} | |
| \renewenvironment{Verbatim}[1][\unskip] | |
| {\begin{alltt}\smaller} | |
| {\end{alltt}} | |
| % Help prevent overflowing lines due to urls and other hard-to-break | |
| % entities. This doesn't catch everything... | |
| \sloppy | |
| % Document level variables | |
| \title{recitation4} | |
| \date{April 04, 2013} | |
| \release{} | |
| \author{Unknown Author} | |
| \renewcommand{\releasename}{} | |
| % TODO: Add option for the user to specify a logo for his/her export. | |
| \newcommand{\sphinxlogo}{} | |
| % Make the index page of the document. | |
| \makeindex | |
| % Import sphinx document type specifics. | |
| % Body | |
| % Start of the document | |
| \begin{document} | |
| \maketitle | |
| \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: 4.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 \[ | |
| \vert f(x)\vert \le M\vert g(x)\vert \; \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} | |
| \itemsep1pt\parskip0pt\parsep0pt | |
| \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} | |
| \itemsep1pt\parskip0pt\parsep0pt | |
| \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} | |
| % Make sure that atleast 4 lines are below the HR | |
| \needspace{4\baselineskip} | |
| \vspace{6pt} | |
| \makebox[0.1\linewidth]{\smaller\hfill\tt\color{nbframe-in-prompt}In\hspace{4pt}{[}35{]}:\hspace{4pt}}\\* | |
| \vspace{-2.65\baselineskip} | |
| \begin{ColorVerbatim} | |
| \vspace{-0.7\baselineskip} | |
| \begin{Verbatim}[commandchars=\\\{\}] | |
| \PY{k+kn}{from} \PY{n+nn}{math} \PY{k+kn}{import} \PY{n}{log} | |
| \PY{n}{domain} \PY{o}{=} \PY{n+nb}{range}\PY{p}{(}\PY{l+m+mi}{1}\PY{p}{,}\PY{l+m+mi}{100}\PY{p}{)} | |
| \PY{n}{const} \PY{o}{=} \PY{p}{[}\PY{l+m+mi}{10} \PY{k}{for} \PY{n}{x} \PY{o+ow}{in} \PY{n}{domain}\PY{p}{]} | |
| \PY{n}{lin} \PY{o}{=} \PY{p}{[}\PY{n}{x} \PY{k}{for} \PY{n}{x} \PY{o+ow}{in} \PY{n}{domain}\PY{p}{]} | |
| \PY{n}{loglin} \PY{o}{=} \PY{p}{[}\PY{n}{x} \PY{o}{*} \PY{n}{log}\PY{p}{(}\PY{n}{x}\PY{p}{)} \PY{k}{for} \PY{n}{x} \PY{o+ow}{in} \PY{n}{domain}\PY{p}{]} | |
| \PY{n}{poly} \PY{o}{=} \PY{p}{[}\PY{n}{x} \PY{o}{*}\PY{o}{*} \PY{l+m+mi}{2} \PY{k}{for} \PY{n}{x} \PY{o+ow}{in} \PY{n}{domain}\PY{p}{]} | |
| \PY{c}{\PYZsh{} these lines are the plotting directives} | |
| \PY{n}{fig} \PY{o}{=} \PY{n}{figure}\PY{p}{(}\PY{n}{figsize}\PY{o}{=}\PY{p}{(}\PY{l+m+mi}{16}\PY{p}{,}\PY{l+m+mi}{6}\PY{p}{)}\PY{p}{)} | |
| \PY{n}{ax} \PY{o}{=} \PY{n}{subplot}\PY{p}{(}\PY{l+m+mi}{1}\PY{p}{,}\PY{l+m+mi}{3}\PY{p}{,}\PY{l+m+mi}{1}\PY{p}{)} | |
| \PY{n}{ax}\PY{o}{.}\PY{n}{plot}\PY{p}{(}\PY{n}{domain}\PY{p}{,}\PY{n}{const}\PY{p}{)} | |
| \PY{n}{ax}\PY{o}{.}\PY{n}{plot}\PY{p}{(}\PY{n}{domain}\PY{p}{,}\PY{n}{lin}\PY{p}{)} | |
| \PY{n}{ax}\PY{o}{.}\PY{n}{legend}\PY{p}{(}\PY{p}{[}\PY{l+s}{\PYZdq{}}\PY{l+s}{const}\PY{l+s}{\PYZdq{}}\PY{p}{,}\PY{l+s}{\PYZdq{}}\PY{l+s}{lin}\PY{l+s}{\PYZdq{}}\PY{p}{]}\PY{p}{,}\PY{n}{loc}\PY{o}{=}\PY{l+m+mi}{2}\PY{p}{)}\PY{p}{;} | |
| \PY{n}{ax} \PY{o}{=} \PY{n}{subplot}\PY{p}{(}\PY{l+m+mi}{1}\PY{p}{,}\PY{l+m+mi}{3}\PY{p}{,}\PY{l+m+mi}{2}\PY{p}{)} | |
| \PY{n}{ax}\PY{o}{.}\PY{n}{plot}\PY{p}{(}\PY{n}{domain}\PY{p}{,}\PY{n}{lin}\PY{p}{)} | |
| \PY{n}{ax}\PY{o}{.}\PY{n}{plot}\PY{p}{(}\PY{n}{domain}\PY{p}{,}\PY{n}{loglin}\PY{p}{)} | |
| \PY{n}{ax}\PY{o}{.}\PY{n}{legend}\PY{p}{(}\PY{p}{[}\PY{l+s}{\PYZdq{}}\PY{l+s}{lin}\PY{l+s}{\PYZdq{}}\PY{p}{,}\PY{l+s}{\PYZdq{}}\PY{l+s}{loglin}\PY{l+s}{\PYZdq{}}\PY{p}{]}\PY{p}{,}\PY{n}{loc}\PY{o}{=}\PY{l+m+mi}{2}\PY{p}{)}\PY{p}{;} | |
| \PY{n}{ax} \PY{o}{=} \PY{n}{subplot}\PY{p}{(}\PY{l+m+mi}{1}\PY{p}{,}\PY{l+m+mi}{3}\PY{p}{,}\PY{l+m+mi}{3}\PY{p}{)} | |
| \PY{n}{ax}\PY{o}{.}\PY{n}{plot}\PY{p}{(}\PY{n}{domain}\PY{p}{,}\PY{n}{loglin}\PY{p}{)} | |
| \PY{n}{ax}\PY{o}{.}\PY{n}{plot}\PY{p}{(}\PY{n}{domain}\PY{p}{,}\PY{n}{poly}\PY{p}{)} | |
| \PY{n}{ax}\PY{o}{.}\PY{n}{legend}\PY{p}{(}\PY{p}{[}\PY{l+s}{\PYZdq{}}\PY{l+s}{loglin}\PY{l+s}{\PYZdq{}}\PY{p}{,}\PY{l+s}{\PYZdq{}}\PY{l+s}{poly}\PY{l+s}{\PYZdq{}}\PY{p}{]}\PY{p}{,}\PY{n}{loc}\PY{o}{=}\PY{l+m+mi}{2}\PY{p}{)}\PY{p}{;} | |
| \end{Verbatim} | |
| \vspace{-0.2\baselineskip} | |
| \end{ColorVerbatim} | |
| % If the first block is an image, minipage the image. Else | |
| % request a certain amount of space for the input text. | |
| \needspace{4\baselineskip} | |
| % Add document contents. | |
| \begin{InvisibleVerbatim} | |
| \vspace{-0.5\baselineskip} | |
| \begin{center} | |
| \includegraphics[max size={\textwidth}{\textheight}]{recitation4_files/recitation4_3_0.png} | |
| \par | |
| \end{center} | |
| \end{InvisibleVerbatim} | |
| \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 $f_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} | |
| \itemsep1pt\parskip0pt\parsep0pt | |
| \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{{[}Fermat's little | |
| theorem{]}(http://en.wikipedia.org/wiki/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}. | |
| % Make sure that atleast 4 lines are below the HR | |
| \needspace{4\baselineskip} | |
| \vspace{6pt} | |
| \makebox[0.1\linewidth]{\smaller\hfill\tt\color{nbframe-in-prompt}In\hspace{4pt}{[}39{]}:\hspace{4pt}}\\* | |
| \vspace{-2.65\baselineskip} | |
| \begin{ColorVerbatim} | |
| \vspace{-0.7\baselineskip} | |
| \begin{Verbatim}[commandchars=\\\{\}] | |
| \PY{k+kn}{from} \PY{n+nn}{random} \PY{k+kn}{import} \PY{n}{randrange} | |
| \PY{k}{def} \PY{n+nf}{is\PYZus{}prime}\PY{p}{(}\PY{n}{p}\PY{p}{)}\PY{p}{:} | |
| \PY{l+s+sd}{\PYZdq{}\PYZdq{}\PYZdq{}probabilistic test for p\PYZsq{}s compositeness\PYZdq{}\PYZdq{}\PYZdq{}} | |
| \PY{k}{for} \PY{n}{i} \PY{o+ow}{in} \PY{n+nb}{range}\PY{p}{(}\PY{l+m+mi}{100}\PY{p}{)}\PY{p}{:} | |
| \PY{n}{a} \PY{o}{=} \PY{n}{randrange}\PY{p}{(}\PY{l+m+mi}{1}\PY{p}{,} \PY{n}{p} \PY{o}{\PYZhy{}} \PY{l+m+mi}{1}\PY{p}{)} \PY{c}{\PYZsh{} a is a random integer in [1..p\PYZhy{}1]} | |
| \PY{k}{if} \PY{n+nb}{pow}\PY{p}{(}\PY{n}{a}\PY{p}{,} \PY{n}{p} \PY{o}{\PYZhy{}} \PY{l+m+mi}{1}\PY{p}{,} \PY{n}{p}\PY{p}{)} \PY{o}{!=} \PY{l+m+mi}{1}\PY{p}{:} \PY{c}{\PYZsh{} this takes O(n\PYZca{}3) = O((log2 p)\PYZca{}3)} | |
| \PY{k}{return} \PY{n+nb+bp}{False} | |
| \PY{k}{return} \PY{n+nb+bp}{True} \PY{c}{\PYZsh{} we get here if no compositeness witness was found} | |
| \end{Verbatim} | |
| \vspace{-0.2\baselineskip} | |
| \end{ColorVerbatim} | |
| % Make sure that atleast 4 lines are below the HR | |
| \needspace{4\baselineskip} | |
| \vspace{6pt} | |
| \makebox[0.1\linewidth]{\smaller\hfill\tt\color{nbframe-in-prompt}In\hspace{4pt}{[}4{]}:\hspace{4pt}}\\* | |
| \vspace{-2.65\baselineskip} | |
| \begin{ColorVerbatim} | |
| \vspace{-0.7\baselineskip} | |
| \begin{Verbatim}[commandchars=\\\{\}] | |
| \PY{n}{is\PYZus{}prime}\PY{p}{(}\PY{l+m+mi}{11}\PY{p}{)} | |
| \end{Verbatim} | |
| \vspace{-0.2\baselineskip} | |
| \end{ColorVerbatim} | |
| % If the first block is an image, minipage the image. Else | |
| % request a certain amount of space for the input text. | |
| \needspace{4\baselineskip} | |
| % Add document contents. | |
| \makebox[0.1\linewidth]{\smaller\hfill\tt\color{nbframe-out-prompt}Out\hspace{4pt}{[}4{]}:\hspace{4pt}}\\* | |
| \vspace{-2.55\baselineskip}\begin{InvisibleVerbatim} | |
| \vspace{-0.5\baselineskip} | |
| \begin{alltt}True\end{alltt} | |
| \end{InvisibleVerbatim} | |
| % Make sure that atleast 4 lines are below the HR | |
| \needspace{4\baselineskip} | |
| \vspace{6pt} | |
| \makebox[0.1\linewidth]{\smaller\hfill\tt\color{nbframe-in-prompt}In\hspace{4pt}{[}5{]}:\hspace{4pt}}\\* | |
| \vspace{-2.65\baselineskip} | |
| \begin{ColorVerbatim} | |
| \vspace{-0.7\baselineskip} | |
| \begin{Verbatim}[commandchars=\\\{\}] | |
| \PY{n}{is\PYZus{}prime}\PY{p}{(}\PY{l+m+mi}{190125101}\PY{p}{)} | |
| \end{Verbatim} | |
| \vspace{-0.2\baselineskip} | |
| \end{ColorVerbatim} | |
| % If the first block is an image, minipage the image. Else | |
| % request a certain amount of space for the input text. | |
| \needspace{4\baselineskip} | |
| % Add document contents. | |
| \makebox[0.1\linewidth]{\smaller\hfill\tt\color{nbframe-out-prompt}Out\hspace{4pt}{[}5{]}:\hspace{4pt}}\\* | |
| \vspace{-2.55\baselineskip}\begin{InvisibleVerbatim} | |
| \vspace{-0.5\baselineskip} | |
| \begin{alltt}True\end{alltt} | |
| \end{InvisibleVerbatim} | |
| \subsubsection{Notes} | |
| \begin{itemize} | |
| \itemsep1pt\parskip0pt\parsep0pt | |
| \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$. | |
| Now, assuming the primes are uniformaly distributed, the probability | |
| that a randomly sampled number between $1$ and $x$ is prime is | |
| $\frac{\pi(x)}{x} \thicksim \frac{1}{log(x)}$. | |
| Since the number of bits in $x$, $n$, is $O(log(x))\;$ this translates | |
| to $O(1/n)$. | |
| Now, the probability that a number with exactly $n$ bits is prime is | |
| roughly half of the probability that a number of $n$ or less bits is | |
| prime, and this doesn't change the order of magnitude, 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}. | |
| % Make sure that atleast 4 lines are below the HR | |
| \needspace{4\baselineskip} | |
| \vspace{6pt} | |
| \makebox[0.1\linewidth]{\smaller\hfill\tt\color{nbframe-in-prompt}In\hspace{4pt}{[}34{]}:\hspace{4pt}}\\* | |
| \vspace{-2.65\baselineskip} | |
| \begin{ColorVerbatim} | |
| \vspace{-0.7\baselineskip} | |
| \begin{Verbatim}[commandchars=\\\{\}] | |
| \PY{k}{def} \PY{n+nf}{prob\PYZus{}prime}\PY{p}{(}\PY{n}{n}\PY{p}{)}\PY{p}{:} | |
| \PY{l+s+sd}{\PYZdq{}\PYZdq{}\PYZdq{}evaluate the probability of an n\PYZhy{}bit long integer to be prime\PYZdq{}\PYZdq{}\PYZdq{}} | |
| \PY{n}{count} \PY{o}{=} \PY{l+m+mi}{0} | |
| \PY{n}{sample\PYZus{}size} \PY{o}{=} \PY{l+m+mi}{10} \PY{o}{*}\PY{o}{*} \PY{l+m+mi}{5} | |
| \PY{k}{for} \PY{n}{i} \PY{o+ow}{in} \PY{n+nb}{range}\PY{p}{(}\PY{n}{sample\PYZus{}size}\PY{p}{)}\PY{p}{:} | |
| \PY{n}{p} \PY{o}{=} \PY{n}{randrange}\PY{p}{(}\PY{l+m+mi}{2} \PY{o}{*}\PY{o}{*} \PY{p}{(}\PY{n}{n} \PY{o}{\PYZhy{}} \PY{l+m+mi}{1}\PY{p}{)}\PY{p}{,} \PY{l+m+mi}{2} \PY{o}{*}\PY{o}{*} \PY{n}{n} \PY{o}{\PYZhy{}} \PY{l+m+mi}{1}\PY{p}{)} | |
| \PY{n}{count} \PY{o}{+}\PY{o}{=} \PY{n}{is\PYZus{}prime}\PY{p}{(}\PY{n}{p}\PY{p}{)} | |
| \PY{k}{return} \PY{n}{count} \PY{o}{/} \PY{n}{sample\PYZus{}size} | |
| \end{Verbatim} | |
| \vspace{-0.2\baselineskip} | |
| \end{ColorVerbatim} | |
| % Make sure that atleast 4 lines are below the HR | |
| \needspace{4\baselineskip} | |
| \vspace{6pt} | |
| \makebox[0.1\linewidth]{\smaller\hfill\tt\color{nbframe-in-prompt}In\hspace{4pt}{[}36{]}:\hspace{4pt}}\\* | |
| \vspace{-2.65\baselineskip} | |
| \begin{ColorVerbatim} | |
| \vspace{-0.7\baselineskip} | |
| \begin{Verbatim}[commandchars=\\\{\}] | |
| \PY{n}{prob\PYZus{}prime}\PY{p}{(}\PY{l+m+mi}{20}\PY{p}{)} | |
| \end{Verbatim} | |
| \vspace{-0.2\baselineskip} | |
| \end{ColorVerbatim} | |
| % If the first block is an image, minipage the image. Else | |
| % request a certain amount of space for the input text. | |
| \needspace{4\baselineskip} | |
| % Add document contents. | |
| \makebox[0.1\linewidth]{\smaller\hfill\tt\color{nbframe-out-prompt}Out\hspace{4pt}{[}36{]}:\hspace{4pt}}\\* | |
| \vspace{-2.55\baselineskip}\begin{InvisibleVerbatim} | |
| \vspace{-0.5\baselineskip} | |
| \begin{alltt}0.07423\end{alltt} | |
| \end{InvisibleVerbatim} | |
| % Make sure that atleast 4 lines are below the HR | |
| \needspace{4\baselineskip} | |
| \vspace{6pt} | |
| \makebox[0.1\linewidth]{\smaller\hfill\tt\color{nbframe-in-prompt}In\hspace{4pt}{[}37{]}:\hspace{4pt}}\\* | |
| \vspace{-2.65\baselineskip} | |
| \begin{ColorVerbatim} | |
| \vspace{-0.7\baselineskip} | |
| \begin{Verbatim}[commandchars=\\\{\}] | |
| \PY{l+m+mi}{1} \PY{o}{/} \PY{l+m+mi}{20} | |
| \end{Verbatim} | |
| \vspace{-0.2\baselineskip} | |
| \end{ColorVerbatim} | |
| % If the first block is an image, minipage the image. Else | |
| % request a certain amount of space for the input text. | |
| \needspace{4\baselineskip} | |
| % Add document contents. | |
| \makebox[0.1\linewidth]{\smaller\hfill\tt\color{nbframe-out-prompt}Out\hspace{4pt}{[}37{]}:\hspace{4pt}}\\* | |
| \vspace{-2.55\baselineskip}\begin{InvisibleVerbatim} | |
| \vspace{-0.5\baselineskip} | |
| \begin{alltt}0.05\end{alltt} | |
| \end{InvisibleVerbatim} | |
| The relative error is therefore small: | |
| % Make sure that atleast 4 lines are below the HR | |
| \needspace{4\baselineskip} | |
| \vspace{6pt} | |
| \makebox[0.1\linewidth]{\smaller\hfill\tt\color{nbframe-in-prompt}In\hspace{4pt}{[}40{]}:\hspace{4pt}}\\* | |
| \vspace{-2.65\baselineskip} | |
| \begin{ColorVerbatim} | |
| \vspace{-0.7\baselineskip} | |
| \begin{Verbatim}[commandchars=\\\{\}] | |
| \PY{p}{(}\PY{l+m+mf}{0.07423} \PY{o}{\PYZhy{}} \PY{l+m+mf}{0.05}\PY{p}{)} \PY{o}{/} \PY{l+m+mf}{0.05} | |
| \end{Verbatim} | |
| \vspace{-0.2\baselineskip} | |
| \end{ColorVerbatim} | |
| % If the first block is an image, minipage the image. Else | |
| % request a certain amount of space for the input text. | |
| \needspace{4\baselineskip} | |
| % Add document contents. | |
| \makebox[0.1\linewidth]{\smaller\hfill\tt\color{nbframe-out-prompt}Out\hspace{4pt}{[}40{]}:\hspace{4pt}}\\* | |
| \vspace{-2.55\baselineskip}\begin{InvisibleVerbatim} | |
| \vspace{-0.5\baselineskip} | |
| \begin{alltt}0.48460000000000003\end{alltt} | |
| \end{InvisibleVerbatim} | |
| \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: | |
| % Make sure that atleast 4 lines are below the HR | |
| \needspace{4\baselineskip} | |
| \vspace{6pt} | |
| \makebox[0.1\linewidth]{\smaller\hfill\tt\color{nbframe-in-prompt}In\hspace{4pt}{[}20{]}:\hspace{4pt}}\\* | |
| \vspace{-2.65\baselineskip} | |
| \begin{ColorVerbatim} | |
| \vspace{-0.7\baselineskip} | |
| \begin{Verbatim}[commandchars=\\\{\}] | |
| \PY{k}{def} \PY{n+nf}{DH\PYZus{}exchange}\PY{p}{(}\PY{n}{p}\PY{p}{)}\PY{p}{:} | |
| \PY{l+s+sd}{\PYZdq{}\PYZdq{}\PYZdq{} generates a shared DH key \PYZdq{}\PYZdq{}\PYZdq{}} | |
| \PY{n}{g} \PY{o}{=} \PY{n}{randrange}\PY{p}{(}\PY{l+m+mi}{1}\PY{p}{,}\PY{n}{p}\PY{o}{\PYZhy{}}\PY{l+m+mi}{1}\PY{p}{)} | |
| \PY{n}{a} \PY{o}{=} \PY{n}{randrange}\PY{p}{(}\PY{l+m+mi}{1}\PY{p}{,}\PY{n}{p}\PY{o}{\PYZhy{}}\PY{l+m+mi}{1}\PY{p}{)} \PY{c}{\PYZsh{} Alice\PYZsq{}s secret} | |
| \PY{n}{b} \PY{o}{=} \PY{n}{randrange}\PY{p}{(}\PY{l+m+mi}{1}\PY{p}{,}\PY{n}{p}\PY{o}{\PYZhy{}}\PY{l+m+mi}{1}\PY{p}{)} \PY{c}{\PYZsh{} Bob\PYZsq{}s secret} | |
| \PY{n}{x} \PY{o}{=} \PY{n+nb}{pow}\PY{p}{(}\PY{n}{g}\PY{p}{,}\PY{n}{a}\PY{p}{,}\PY{n}{p}\PY{p}{)} | |
| \PY{n}{y} \PY{o}{=} \PY{n+nb}{pow}\PY{p}{(}\PY{n}{g}\PY{p}{,}\PY{n}{b}\PY{p}{,}\PY{n}{p}\PY{p}{)} | |
| \PY{n}{key\PYZus{}A} \PY{o}{=} \PY{n+nb}{pow}\PY{p}{(}\PY{n}{y}\PY{p}{,}\PY{n}{a}\PY{p}{,}\PY{n}{p}\PY{p}{)} | |
| \PY{n}{key\PYZus{}B} \PY{o}{=} \PY{n+nb}{pow}\PY{p}{(}\PY{n}{x}\PY{p}{,}\PY{n}{b}\PY{p}{,}\PY{n}{p}\PY{p}{)} | |
| \PY{k}{return} \PY{n}{g}\PY{p}{,} \PY{n}{a}\PY{p}{,} \PY{n}{b}\PY{p}{,} \PY{n}{x}\PY{p}{,} \PY{n}{y}\PY{p}{,} \PY{n}{key\PYZus{}A}\PY{p}{,} \PY{n}{key\PYZus{}B} | |
| \end{Verbatim} | |
| \vspace{-0.2\baselineskip} | |
| \end{ColorVerbatim} | |
| % Make sure that atleast 4 lines are below the HR | |
| \needspace{4\baselineskip} | |
| \vspace{6pt} | |
| \makebox[0.1\linewidth]{\smaller\hfill\tt\color{nbframe-in-prompt}In\hspace{4pt}{[}44{]}:\hspace{4pt}}\\* | |
| \vspace{-2.65\baselineskip} | |
| \begin{ColorVerbatim} | |
| \vspace{-0.7\baselineskip} | |
| \begin{Verbatim}[commandchars=\\\{\}] | |
| \PY{n}{DH\PYZus{}exchange}\PY{p}{(}\PY{l+m+mi}{190125101}\PY{p}{)} | |
| \end{Verbatim} | |
| \vspace{-0.2\baselineskip} | |
| \end{ColorVerbatim} | |
| % If the first block is an image, minipage the image. Else | |
| % request a certain amount of space for the input text. | |
| \needspace{4\baselineskip} | |
| % Add document contents. | |
| \makebox[0.1\linewidth]{\smaller\hfill\tt\color{nbframe-out-prompt}Out\hspace{4pt}{[}44{]}:\hspace{4pt}}\\* | |
| \vspace{-2.55\baselineskip}\begin{InvisibleVerbatim} | |
| \vspace{-0.5\baselineskip} | |
| \begin{alltt}(130721310, 61963609, 1775050, 132736567, 143446917, 74182194, | |
| 74182194)\end{alltt} | |
| \end{InvisibleVerbatim} | |
| % Make sure that atleast 4 lines are below the HR | |
| \needspace{4\baselineskip} | |
| \vspace{6pt} | |
| \makebox[0.1\linewidth]{\smaller\hfill\tt\color{nbframe-in-prompt}In\hspace{4pt}{[}45{]}:\hspace{4pt}}\\* | |
| \vspace{-2.65\baselineskip} | |
| \begin{ColorVerbatim} | |
| \vspace{-0.7\baselineskip} | |
| \begin{Verbatim}[commandchars=\\\{\}] | |
| \PY{n}{DH\PYZus{}exchange}\PY{p}{(}\PY{l+m+mi}{833648000993161193752610727299}\PY{p}{)} | |
| \end{Verbatim} | |
| \vspace{-0.2\baselineskip} | |
| \end{ColorVerbatim} | |
| % If the first block is an image, minipage the image. Else | |
| % request a certain amount of space for the input text. | |
| \needspace{4\baselineskip} | |
| % Add document contents. | |
| \makebox[0.1\linewidth]{\smaller\hfill\tt\color{nbframe-out-prompt}Out\hspace{4pt}{[}45{]}:\hspace{4pt}}\\* | |
| \vspace{-2.55\baselineskip}\begin{InvisibleVerbatim} | |
| \vspace{-0.5\baselineskip} | |
| \begin{alltt}(225405422835827732918401478004, | |
| 153883981994400043514132897779, | |
| 556710940458985113442266962618, | |
| 620358857758647613746179753310, | |
| 479744267228387852844588852918, | |
| 610421506532174772126394293202, | |
| 610421506532174772126394293202)\end{alltt} | |
| \end{InvisibleVerbatim} | |
| Now let's try and break it: | |
| % Make sure that atleast 4 lines are below the HR | |
| \needspace{4\baselineskip} | |
| \vspace{6pt} | |
| \makebox[0.1\linewidth]{\smaller\hfill\tt\color{nbframe-in-prompt}In\hspace{4pt}{[}19{]}:\hspace{4pt}}\\* | |
| \vspace{-2.65\baselineskip} | |
| \begin{ColorVerbatim} | |
| \vspace{-0.7\baselineskip} | |
| \begin{Verbatim}[commandchars=\\\{\}] | |
| \PY{k}{def} \PY{n+nf}{crack\PYZus{}DH}\PY{p}{(}\PY{n}{p}\PY{p}{,} \PY{n}{g}\PY{p}{,} \PY{n}{x}\PY{p}{)}\PY{p}{:} | |
| \PY{l+s+sd}{\PYZdq{}\PYZdq{}\PYZdq{}find secret \PYZdq{}a\PYZdq{} that satisfies g**a\PYZpc{}p == x} | |
| \PY{l+s+sd}{ Not feasible for large p\PYZdq{}\PYZdq{}\PYZdq{}} | |
| \PY{k}{for} \PY{n}{a} \PY{o+ow}{in} \PY{n+nb}{range}\PY{p}{(}\PY{l+m+mi}{1}\PY{p}{,}\PY{n}{p}\PY{o}{\PYZhy{}}\PY{l+m+mi}{1}\PY{p}{)}\PY{p}{:} | |
| \PY{k}{if} \PY{n}{a} \PY{o}{\PYZpc{}} \PY{l+m+mi}{100000} \PY{o}{==} \PY{l+m+mi}{0}\PY{p}{:} | |
| \PY{k}{print}\PY{p}{(}\PY{l+s}{\PYZdq{}}\PY{l+s}{Iteration}\PY{l+s}{\PYZdq{}}\PY{p}{,}\PY{n}{a}\PY{p}{)} \PY{c}{\PYZsh{} progress bar} | |
| \PY{k}{if} \PY{n+nb}{pow}\PY{p}{(}\PY{n}{g}\PY{p}{,}\PY{n}{a}\PY{p}{,}\PY{n}{p}\PY{p}{)} \PY{o}{==} \PY{n}{x}\PY{p}{:} | |
| \PY{k}{return} \PY{n}{a} | |
| \PY{k}{return} \PY{n+nb+bp}{None} | |
| \end{Verbatim} | |
| \vspace{-0.2\baselineskip} | |
| \end{ColorVerbatim} | |
| Note that because \texttt{pow(a,b,c)} is not | |
| \href{http://en.wikipedia.org/wiki/Injective_function}{injective} (in | |
| contrast to what might have been said in class\ldots{}) this may return | |
| the wrong answer. | |
| To test the protocol, we first need a function that finds primes: | |
| % Make sure that atleast 4 lines are below the HR | |
| \needspace{4\baselineskip} | |
| \vspace{6pt} | |
| \makebox[0.1\linewidth]{\smaller\hfill\tt\color{nbframe-in-prompt}In\hspace{4pt}{[}14{]}:\hspace{4pt}}\\* | |
| \vspace{-2.65\baselineskip} | |
| \begin{ColorVerbatim} | |
| \vspace{-0.7\baselineskip} | |
| \begin{Verbatim}[commandchars=\\\{\}] | |
| \PY{k}{def} \PY{n+nf}{find\PYZus{}prime}\PY{p}{(}\PY{n}{n}\PY{p}{)}\PY{p}{:} | |
| \PY{l+s+sd}{\PYZdq{}\PYZdq{}\PYZdq{} find random n\PYZhy{}bit long prime (no leading zeros: 2**(n\PYZhy{}1)\PYZlt{}= N \PYZlt{} 2**n )\PYZdq{}\PYZdq{}\PYZdq{}} | |
| \PY{k}{while} \PY{n+nb+bp}{True}\PY{p}{:} \PY{c}{\PYZsh{}here we\PYZsq{}re optimistic, but actually we have a good reason to be:} | |
| \PY{c}{\PYZsh{} after O(1/n) iterations we expect to find a prime and halt} | |
| \PY{n}{candidate} \PY{o}{=} \PY{n}{randrange}\PY{p}{(}\PY{l+m+mi}{2}\PY{o}{*}\PY{o}{*}\PY{p}{(}\PY{n}{n} \PY{o}{\PYZhy{}} \PY{l+m+mi}{1}\PY{p}{)}\PY{p}{,} \PY{l+m+mi}{2}\PY{o}{*}\PY{o}{*}\PY{n}{n}\PY{p}{)} | |
| \PY{k}{if} \PY{n}{is\PYZus{}prime}\PY{p}{(}\PY{n}{candidate}\PY{p}{)}\PY{p}{:} | |
| \PY{k}{return} \PY{n}{candidate} | |
| \end{Verbatim} | |
| \vspace{-0.2\baselineskip} | |
| \end{ColorVerbatim} | |
| % Make sure that atleast 4 lines are below the HR | |
| \needspace{4\baselineskip} | |
| \vspace{6pt} | |
| \makebox[0.1\linewidth]{\smaller\hfill\tt\color{nbframe-in-prompt}In\hspace{4pt}{[}15{]}:\hspace{4pt}}\\* | |
| \vspace{-2.65\baselineskip} | |
| \begin{ColorVerbatim} | |
| \vspace{-0.7\baselineskip} | |
| \begin{Verbatim}[commandchars=\\\{\}] | |
| \PY{n}{find\PYZus{}prime}\PY{p}{(}\PY{l+m+mi}{10}\PY{p}{)} | |
| \end{Verbatim} | |
| \vspace{-0.2\baselineskip} | |
| \end{ColorVerbatim} | |
| % If the first block is an image, minipage the image. Else | |
| % request a certain amount of space for the input text. | |
| \needspace{4\baselineskip} | |
| % Add document contents. | |
| \makebox[0.1\linewidth]{\smaller\hfill\tt\color{nbframe-out-prompt}Out\hspace{4pt}{[}15{]}:\hspace{4pt}}\\* | |
| \vspace{-2.55\baselineskip}\begin{InvisibleVerbatim} | |
| \vspace{-0.5\baselineskip} | |
| \begin{alltt}991\end{alltt} | |
| \end{InvisibleVerbatim} | |
| % Make sure that atleast 4 lines are below the HR | |
| \needspace{4\baselineskip} | |
| \vspace{6pt} | |
| \makebox[0.1\linewidth]{\smaller\hfill\tt\color{nbframe-in-prompt}In\hspace{4pt}{[}16{]}:\hspace{4pt}}\\* | |
| \vspace{-2.65\baselineskip} | |
| \begin{ColorVerbatim} | |
| \vspace{-0.7\baselineskip} | |
| \begin{Verbatim}[commandchars=\\\{\}] | |
| \PY{n}{find\PYZus{}prime}\PY{p}{(}\PY{l+m+mi}{100}\PY{p}{)} | |
| \end{Verbatim} | |
| \vspace{-0.2\baselineskip} | |
| \end{ColorVerbatim} | |
| % If the first block is an image, minipage the image. Else | |
| % request a certain amount of space for the input text. | |
| \needspace{4\baselineskip} | |
| % Add document contents. | |
| \makebox[0.1\linewidth]{\smaller\hfill\tt\color{nbframe-out-prompt}Out\hspace{4pt}{[}16{]}:\hspace{4pt}}\\* | |
| \vspace{-2.55\baselineskip}\begin{InvisibleVerbatim} | |
| \vspace{-0.5\baselineskip} | |
| \begin{alltt}1115065337204017303367921856997\end{alltt} | |
| \end{InvisibleVerbatim} | |
| % Make sure that atleast 4 lines are below the HR | |
| \needspace{4\baselineskip} | |
| \vspace{6pt} | |
| \makebox[0.1\linewidth]{\smaller\hfill\tt\color{nbframe-in-prompt}In\hspace{4pt}{[}17{]}:\hspace{4pt}}\\* | |
| \vspace{-2.65\baselineskip} | |
| \begin{ColorVerbatim} | |
| \vspace{-0.7\baselineskip} | |
| \begin{Verbatim}[commandchars=\\\{\}] | |
| \PY{n}{find\PYZus{}prime}\PY{p}{(}\PY{l+m+mi}{256}\PY{p}{)} | |
| \end{Verbatim} | |
| \vspace{-0.2\baselineskip} | |
| \end{ColorVerbatim} | |
| % If the first block is an image, minipage the image. Else | |
| % request a certain amount of space for the input text. | |
| \needspace{4\baselineskip} | |
| % Add document contents. | |
| \makebox[0.1\linewidth]{\smaller\hfill\tt\color{nbframe-out-prompt}Out\hspace{4pt}{[}17{]}:\hspace{4pt}}\\* | |
| \vspace{-2.55\baselineskip}\begin{InvisibleVerbatim} | |
| \vspace{-0.5\baselineskip} | |
| \begin{alltt}5981782241541348011667964959333282233859059980723648176423291650962030 | |
| 4609287\end{alltt} | |
| \end{InvisibleVerbatim} | |
| We can now run the DH protocol and try to break it. | |
| We will start with a 10-bit prime: | |
| % Make sure that atleast 4 lines are below the HR | |
| \needspace{4\baselineskip} | |
| \vspace{6pt} | |
| \makebox[0.1\linewidth]{\smaller\hfill\tt\color{nbframe-in-prompt}In\hspace{4pt}{[}27{]}:\hspace{4pt}}\\* | |
| \vspace{-2.65\baselineskip} | |
| \begin{ColorVerbatim} | |
| \vspace{-0.7\baselineskip} | |
| \begin{Verbatim}[commandchars=\\\{\}] | |
| \PY{k+kn}{from} \PY{n+nn}{math} \PY{k+kn}{import} \PY{n}{log} | |
| \PY{n}{p} \PY{o}{=} \PY{n}{find\PYZus{}prime}\PY{p}{(}\PY{l+m+mi}{10}\PY{p}{)} | |
| \PY{k}{print}\PY{p}{(}\PY{n}{p}\PY{p}{,}\PY{n}{log}\PY{p}{(}\PY{n}{p}\PY{p}{,}\PY{l+m+mi}{2}\PY{p}{)}\PY{p}{)} | |
| \PY{n}{g}\PY{p}{,}\PY{n}{a}\PY{p}{,}\PY{n}{b}\PY{p}{,}\PY{n}{x}\PY{p}{,}\PY{n}{y}\PY{p}{,}\PY{n}{key\PYZus{}A}\PY{p}{,}\PY{n}{key\PYZus{}B} \PY{o}{=} \PY{n}{DH\PYZus{}exchange}\PY{p}{(}\PY{n}{p}\PY{p}{)} | |
| \PY{k}{print}\PY{p}{(}\PY{l+s}{\PYZsq{}}\PY{l+s}{g}\PY{l+s}{\PYZsq{}}\PY{p}{,}\PY{n}{g}\PY{p}{,}\PY{l+s}{\PYZsq{}}\PY{l+s}{a}\PY{l+s}{\PYZsq{}}\PY{p}{,}\PY{n}{a}\PY{p}{,}\PY{l+s}{\PYZsq{}}\PY{l+s}{b}\PY{l+s}{\PYZsq{}}\PY{p}{,}\PY{n}{b}\PY{p}{,}\PY{l+s}{\PYZsq{}}\PY{l+s}{x}\PY{l+s}{\PYZsq{}}\PY{p}{,}\PY{n}{x}\PY{p}{,}\PY{l+s}{\PYZsq{}}\PY{l+s}{y}\PY{l+s}{\PYZsq{}}\PY{p}{,}\PY{n}{y}\PY{p}{,}\PY{l+s}{\PYZsq{}}\PY{l+s}{key\PYZus{}A}\PY{l+s}{\PYZsq{}}\PY{p}{,}\PY{n}{key\PYZus{}A}\PY{p}{,}\PY{l+s}{\PYZsq{}}\PY{l+s}{key\PYZus{}B}\PY{l+s}{\PYZsq{}}\PY{p}{,}\PY{n}{key\PYZus{}B}\PY{p}{)} | |
| \PY{k}{print}\PY{p}{(}\PY{l+s}{\PYZsq{}}\PY{l+s}{a}\PY{l+s}{\PYZsq{}}\PY{p}{,}\PY{n}{crack\PYZus{}DH}\PY{p}{(}\PY{n}{p}\PY{p}{,}\PY{n}{g}\PY{p}{,}\PY{n}{x}\PY{p}{)}\PY{p}{)} | |
| \end{Verbatim} | |
| \vspace{-0.2\baselineskip} | |
| \end{ColorVerbatim} | |
| % If the first block is an image, minipage the image. Else | |
| % request a certain amount of space for the input text. | |
| \needspace{4\baselineskip} | |
| % Add document contents. | |
| \begin{InvisibleVerbatim} | |
| \vspace{-0.5\baselineskip} | |
| \begin{alltt}971 9.923327485419193 | |
| g 813 a 150 b 234 x 371 y 196 key\_A 939 key\_B 939 | |
| a 150 | |
| \end{alltt} | |
| \end{InvisibleVerbatim} | |
| Running with a 16-bit prime: | |
| % Make sure that atleast 4 lines are below the HR | |
| \needspace{4\baselineskip} | |
| \vspace{6pt} | |
| \makebox[0.1\linewidth]{\smaller\hfill\tt\color{nbframe-in-prompt}In\hspace{4pt}{[}28{]}:\hspace{4pt}}\\* | |
| \vspace{-2.65\baselineskip} | |
| \begin{ColorVerbatim} | |
| \vspace{-0.7\baselineskip} | |
| \begin{Verbatim}[commandchars=\\\{\}] | |
| \PY{n}{p} \PY{o}{=} \PY{n}{find\PYZus{}prime}\PY{p}{(}\PY{l+m+mi}{16}\PY{p}{)} | |
| \PY{k}{print}\PY{p}{(}\PY{n}{p}\PY{p}{,}\PY{n}{log}\PY{p}{(}\PY{n}{p}\PY{p}{,}\PY{l+m+mi}{2}\PY{p}{)}\PY{p}{)} | |
| \PY{n}{g}\PY{p}{,}\PY{n}{a}\PY{p}{,}\PY{n}{b}\PY{p}{,}\PY{n}{x}\PY{p}{,}\PY{n}{y}\PY{p}{,}\PY{n}{key\PYZus{}A}\PY{p}{,}\PY{n}{key\PYZus{}B} \PY{o}{=} \PY{n}{DH\PYZus{}exchange}\PY{p}{(}\PY{n}{p}\PY{p}{)} | |
| \PY{k}{print}\PY{p}{(}\PY{l+s}{\PYZsq{}}\PY{l+s}{g}\PY{l+s}{\PYZsq{}}\PY{p}{,}\PY{n}{g}\PY{p}{,}\PY{l+s}{\PYZsq{}}\PY{l+s}{a}\PY{l+s}{\PYZsq{}}\PY{p}{,}\PY{n}{a}\PY{p}{,}\PY{l+s}{\PYZsq{}}\PY{l+s}{b}\PY{l+s}{\PYZsq{}}\PY{p}{,}\PY{n}{b}\PY{p}{,}\PY{l+s}{\PYZsq{}}\PY{l+s}{x}\PY{l+s}{\PYZsq{}}\PY{p}{,}\PY{n}{x}\PY{p}{,}\PY{l+s}{\PYZsq{}}\PY{l+s}{y}\PY{l+s}{\PYZsq{}}\PY{p}{,}\PY{n}{y}\PY{p}{,}\PY{l+s}{\PYZsq{}}\PY{l+s}{key\PYZus{}A}\PY{l+s}{\PYZsq{}}\PY{p}{,}\PY{n}{key\PYZus{}A}\PY{p}{,}\PY{l+s}{\PYZsq{}}\PY{l+s}{key\PYZus{}B}\PY{l+s}{\PYZsq{}}\PY{p}{,}\PY{n}{key\PYZus{}B}\PY{p}{)} | |
| \PY{k}{print}\PY{p}{(}\PY{l+s}{\PYZsq{}}\PY{l+s}{a}\PY{l+s}{\PYZsq{}}\PY{p}{,}\PY{n}{crack\PYZus{}DH}\PY{p}{(}\PY{n}{p}\PY{p}{,}\PY{n}{g}\PY{p}{,}\PY{n}{x}\PY{p}{)}\PY{p}{)} | |
| \end{Verbatim} | |
| \vspace{-0.2\baselineskip} | |
| \end{ColorVerbatim} | |
| % If the first block is an image, minipage the image. Else | |
| % request a certain amount of space for the input text. | |
| \needspace{4\baselineskip} | |
| % Add document contents. | |
| \begin{InvisibleVerbatim} | |
| \vspace{-0.5\baselineskip} | |
| \begin{alltt}47809 15.54499460932774 | |
| g 42852 a 42613 b 27757 x 26351 y 21063 key\_A 21555 key\_B 21555 | |
| a 117 | |
| \end{alltt} | |
| \end{InvisibleVerbatim} | |
| % Make sure that atleast 4 lines are below the HR | |
| \needspace{4\baselineskip} | |
| \vspace{6pt} | |
| \makebox[0.1\linewidth]{\smaller\hfill\tt\color{nbframe-in-prompt}In\hspace{4pt}{[}*{]}:\hspace{4pt}}\\* | |
| \vspace{-2.65\baselineskip} | |
| \begin{ColorVerbatim} | |
| \vspace{-0.7\baselineskip} | |
| \begin{Verbatim}[commandchars=\\\{\}] | |
| \PY{n}{p} \PY{o}{=} \PY{n}{find\PYZus{}prime}\PY{p}{(}\PY{l+m+mi}{128}\PY{p}{)} | |
| \PY{k}{print}\PY{p}{(}\PY{n}{p}\PY{p}{,}\PY{n}{log}\PY{p}{(}\PY{n}{p}\PY{p}{,}\PY{l+m+mi}{2}\PY{p}{)}\PY{p}{)} | |
| \PY{n}{g}\PY{p}{,}\PY{n}{a}\PY{p}{,}\PY{n}{b}\PY{p}{,}\PY{n}{x}\PY{p}{,}\PY{n}{y}\PY{p}{,}\PY{n}{key\PYZus{}A}\PY{p}{,}\PY{n}{key\PYZus{}B} \PY{o}{=} \PY{n}{DH\PYZus{}exchange}\PY{p}{(}\PY{n}{p}\PY{p}{)} | |
| \PY{k}{print}\PY{p}{(}\PY{l+s}{\PYZsq{}}\PY{l+s}{g}\PY{l+s}{\PYZsq{}}\PY{p}{,}\PY{n}{g}\PY{p}{,}\PY{l+s}{\PYZsq{}}\PY{l+s}{a}\PY{l+s}{\PYZsq{}}\PY{p}{,}\PY{n}{a}\PY{p}{,}\PY{l+s}{\PYZsq{}}\PY{l+s}{b}\PY{l+s}{\PYZsq{}}\PY{p}{,}\PY{n}{b}\PY{p}{,}\PY{l+s}{\PYZsq{}}\PY{l+s}{x}\PY{l+s}{\PYZsq{}}\PY{p}{,}\PY{n}{x}\PY{p}{,}\PY{l+s}{\PYZsq{}}\PY{l+s}{y}\PY{l+s}{\PYZsq{}}\PY{p}{,}\PY{n}{y}\PY{p}{,}\PY{l+s}{\PYZsq{}}\PY{l+s}{key\PYZus{}A}\PY{l+s}{\PYZsq{}}\PY{p}{,}\PY{n}{key\PYZus{}A}\PY{p}{,}\PY{l+s}{\PYZsq{}}\PY{l+s}{key\PYZus{}B}\PY{l+s}{\PYZsq{}}\PY{p}{,}\PY{n}{key\PYZus{}B}\PY{p}{)} | |
| \PY{k}{print}\PY{p}{(}\PY{l+s}{\PYZsq{}}\PY{l+s}{a}\PY{l+s}{\PYZsq{}}\PY{p}{,}\PY{n}{crack\PYZus{}DH}\PY{p}{(}\PY{n}{p}\PY{p}{,}\PY{n}{g}\PY{p}{,}\PY{n}{x}\PY{p}{)}\PY{p}{)} | |
| \end{Verbatim} | |
| \vspace{-0.2\baselineskip} | |
| \end{ColorVerbatim} | |
| % If the first block is an image, minipage the image. Else | |
| % request a certain amount of space for the input text. | |
| \needspace{4\baselineskip} | |
| % Add document contents. | |
| \begin{InvisibleVerbatim} | |
| \vspace{-0.5\baselineskip} | |
| \begin{alltt}232058770554614453837871524801758451143 127.44775783025453 | |
| g 159913793420381443650379750802964420717 a | |
| 116795875092692988667366016317257384027 b | |
| 173352797834467896747096128107523563976 x | |
| 224894493378616747082831720370075484037 y | |
| 202527828205657594721613336077418916066 key\_A | |
| 6312501138165008035876819356018294783 key\_B | |
| 6312501138165008035876819356018294783 | |
| Iteration 100000 | |
| Iteration 200000 | |
| Iteration 300000 | |
| Iteration 400000 | |
| Iteration 500000 | |
| Iteration\end{alltt} | |
| \end{InvisibleVerbatim} | |
| \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}. | |
| \renewcommand{\indexname}{Index} | |
| \printindex | |
| % End of document | |
| \end{document} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment