\documentclass[12pt,twoside]{article}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{epsfig}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                       BEGINNING OF PREAMBLE                           %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\newcommand{\eqdef}{\stackrel{\rm def}{=}}
\newcommand{\eqquest}{\stackrel{\rm def}{?}}
\newcommand{\bitset}{\{0,1\}}
\newcommand{\rnd}{\in_R}
\newcommand{\ov}{\overline}
\newcommand{\e}{\epsilon}
\newcommand{\union}{{\cup}}


\newenvironment{summary}{\begin{quote} {\bf Summary:}}{\end{quote}}


\newcommand{\bibref}[1]{[\ref{#1}]}
\renewcommand{\cite}[1]{[\ref{#1}]}

%\newcommand{\eqref}[1]{Eq.~(\ref{#1})}

\newcommand{\anote}[1]{\begin{quote}
                       {\sf Tal's Note}: {\sl{#1}} \end{quote}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\newcommand{\GEN}{\mathbf{GEN}}
\newcommand{\ENC}{\mathbf{ENC}}
\newcommand{\DEC}{\mathbf{DEC}}

% Big O, small o (Andrew)
\newcommand{\bigO}{{\mathop{\rm O}}}
\newcommand{\smallo}{{\mathop{\rm o}}}


% Complexity classes

%\newcommand{\PCP}{\textsf{PCP}}
%\newcommand{\NEXP}{\textsf{NEXP}}

\newcommand{\logspace}{\textsf{L}}     % logarithmic space (Andrej)
\newcommand{\RL}{\textsf{RL}}
\newcommand{\NL}{\textsf{NL}}
\newcommand{\polytime}{\textsf{P}}     % polynomial time (Andrej)
\newcommand{\NP}{\textsf{NP}}          % NP (Andrej)
\newcommand{\coNP}{\textsf{coNP}}
\newcommand{\RP}{\textsf{RP}}
\newcommand{\BPP}{\textsf{BPP}}
\newcommand{\ZPP}{\textsf{ZPP}}
\newcommand{\coNL}{\textsf{coNL}}
\newcommand{\coRP}{\textsf{coRP}}

\newcommand{\EXP}{\textsf{EXP}}        % exponential time (Andrej)
\newcommand{\PSPACE}{\textsf{PSPACE}}
\newcommand{\ACZ}{\textsf{AC}^0}
\newcommand{\IP}{\textsf{IP}}
\newcommand{\AM}{\textsf{AM}}
\newcommand{\coAM}{\textsf{coAM}}

%Logical operators (Andrew)
\newcommand{\AND}{\land}
\newcommand{\OR}{\lor}
\newcommand{\NOT}{\neg}
\newcommand{\EQUIV}{\;\Longleftrightarrow\;}
\newcommand{\IMPLY}{\;\Longrightarrow\;}

% Useful Symbols
\newcommand{\qed}{\hspace*{\fill}\rule{7pt}{7pt}}
\newcommand{\xor}{\oplus}
\newcommand{\Xor}{\bigoplus}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\for}[3]{{\sf for}\hspace{3pt} #1 = #2\hspace{3pt}{\sf to}\hspace{3pt}#3:}
\newcommand{\pr}[1]{{\rm Pr}\left[ #1 \right]}
\newcommand{\ignore}[1]{}


% variable size parens in math mode (pfr)
\newcommand{\lp}{\ensuremath{\left (}}
\newcommand{\rp}{\ensuremath{\right )}}

%easy way to represent a pair (pfr)
\newcommand{\pair}[2]{\ensuremath{\langle}#1,\nolinebreak#2\ensuremath{\rangle}}

%Useful way to make notes for yourself or your editor
\newcommand{\mycomment}[1]{{\bf $<$#1$>$}}

%Contradiction symbol
%\def\contrad{\ensuremath{\ \Rightarrow \Leftarrow \ }}


% Communication complexity (Andrew)
%\newcommand{\cost}{\textsf{COST}}

% Turing Machines
%\newcommand{\qstart}{\mbox{$q_{start}$}}
%\newcommand{\qaccept}{\mbox{$q_{accept}$}}
%\newcommand{\qreject}{\mbox{$q_{reject}$}}
%\newcommand{\blank}{\mbox{$\Box$}}


% Number sets
\newcommand{\Nats}{\ensuremath{\mathbb{N}}}   % Natural numbers
\newcommand{\Reals}{\ensuremath{\mathbb{R}}}  % Real numbers
\newcommand{\Ints}{\ensuremath{\mathbb{Z}}}   % Integers
\newcommand{\CC}{\ensuremath{\mathbb{C}}}     % Complex numbers
\newcommand{\QQ}{\ensuremath{\mathbb{Q}}}     % rational numbers

\newcommand{\Z}{{\mathbb Z}}
\newcommand{\Zp}{{\mathbb Z}_p}
\newcommand{\Zn}{{\mathbb Z}_n}
%\newcommand{\mod}{\mbox{\rm \  mod\ }}
\newcommand{\modp}{\mbox{\rm \ (mod $p$)}}
\newcommand{\modn}{\mbox{\rm \ (mod $n$)}}


%Macros for describing sets and functions (Andrew)
%
% It is *bad* to write $f: A \to B$, because that ':' doesn't come out right.
% Use $f \cc A \to B$ instead. (Andrew)
\newcommand{\cc}{\colon\thinspace}
%
% When you describe a set, like {f(x) | x < 10}, you shouldn't
% write $\{ f(x) | x < 10 \}$ because that won't put enough space around |.
% Use $\{f(x) \such x < 10 \}$ instead. (Andrew)
%
\newcommand{\such}{\; | \;}
\newcommand{\suchthat}{\; : \;}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Theorems are environments with numbering schemes
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem{theorem}{Theorem}      % A counter for Theorems etc
\newcommand{\BT}{\begin{theorem}}
\newcommand{\ET}{\end{theorem}}
%---
\newtheorem{conjecture}[theorem]{Conjecture}
%---
\newtheorem{definition}{Definition}      %
\newcommand{\BD}{\begin{definition}}
\newcommand{\ED}{\end{definition}}
%---
\newtheorem{corollary}[theorem]{Corollary}      %
\newcommand{\BCR}{\begin{corollary}}
\newcommand{\ECR}{\end{corollary}}
%---
\newtheorem{example}{Example}
\newcommand{\BEX}{\begin{example}}
\newcommand{\EEX}{\end{example}}
%---
\newtheorem{lemma}[theorem]{Lemma}  % A counter for Lemmas etc
\newcommand{\BL}{\begin{lemma}}
\newcommand{\EL}{\end{lemma}}
%---
\newtheorem{proposition}[theorem]{Proposition}
\newcommand{\BP}{\begin{proposition}}
\newcommand{\EP}{\end{proposition}}
%---
\newtheorem{claim}[theorem]{Claim}            %
\newcommand{\BCM}{\begin{claim}}
\newcommand{\ECM}{\end{claim}}
%---
\newtheorem{fact}[theorem]{Fact}            %
\newcommand{\BF}{\begin{fact}}
\newcommand{\EF}{\end{fact}}
%---
\newenvironment{proof_sketch}{\QuadSpace\par\noindent{\bf Proof sketch}:}{\qed}
\newenvironment{proof}{\noindent{\bf Proof:~~}}{\qed}
\newcommand{\BPF}{\begin{proof}}
\newcommand{\EPF}{\end{proof}}
%---
\newcommand{\BE}{\begin{enumerate}}
\newcommand{\EE}{\end{enumerate}}
\newcommand{\BI}{\begin{itemize}}
\newcommand{\EI}{\end{itemize}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% \newtheorem{theorem}{Theorem}[section]
%%%% \newtheorem{lemma}[theorem]{Lemma}
%%%% \newtheorem{corollary}[theorem]{Corollary}
%%%% \newtheorem{definition}{Definition}[section]
%%%% \newtheorem{fact}{Fact}
%%%% \newtheorem{assumption}{Assumption}
%%%% \newtheorem{example}{Example}[example]
%%%%
%%%% \newenvironment{proof}{\QuadSpace\par\noindent{\bf Proof}:}{\EndProof\QuadSpace}
%%%% \newenvironment{notation}{\QuadSpace\par\noindent{\bf Notation}:}{\QuadSpace}
%%%% \newenvironment{intuition}{\begin{quote}\par\noindent{\bf Intuition}:}{\end{quote}}
%%%% \newenvironment{note}{\QuadSpace\par\noindent{\bf Note}:}{\QuadSpace}
%%%% \newenvironment{convention}{\QuadSpace\par\noindent{\bf Convention}:}{\QuadSpace}
%%%% \newenvironment{example}{\QuadSpace\par\noindent{\bf Example}:}{\QuadSpace}
%%%% \newenvironment{question}{\QuadSpace\par\noindent{\bf Question}:}{\QuadSpace}
\newenvironment{remark}{\QuadSpace\par\noindent{\bf Remark}:}{\QuadSpace}
%%%% \newenvironment{observation}{\QuadSpace\par\noindent{\bf Observation}:}{\QuadSpace}
%%%% \newenvironment{proposition}{\QuadSpace\par\noindent{\bf Proposition}:}{\QuadSpace}
%%%% \newenvironment{claim}{\QuadSpace\par\noindent{\bf Claim}:}{\QuadSpace}

\newcommand{\QuadSpace}{\vspace{0.25\baselineskip}}
\newcommand{\HalfSpace}{\vspace{0.5\baselineskip}}
\newcommand{\FullSpace}{\vspace{1.0\baselineskip}}
\newcommand{\EndProof}{ \hfill \vrule width 1ex height 1ex depth 0pt }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%       DO NOT CHANGE THE PREAMBLE BELOW THIS LINE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\textwidth=6in \oddsidemargin=0.25in \evensidemargin=0.25in
\topmargin=-0.1in \footskip=0.8in
\parindent=0.0cm
\parskip=0.3cm
\textheight=8.00in

\newcommand{\lecture}[6]
{ \pagestyle{plain} \thispagestyle{plain}
\newpage
\noindent
\begin{center}
\framebox { \vbox{ \hbox to 5.75in
{ \small\bf COMS W4995
Introduction to Cryptography \hfill #2}
\vspace{7mm} \hbox
to 5.75in
{\large\bf \hfill Lecture #1: #5 \hfill}
\vspace{5mm} \hbox to 5.75in
{ \small\it Lecturer: #3 \hfill Scribes: #4}}}
\end{center}                                                            \vspace*{4mm}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                       END OF PREAMBLE                                 %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%               UDPATE the header and synopsis below                    %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%The \lecture command takes 5 arguments as follows:
% \lecture{lecture number}{date of lecture}{lecturer (me usually)}
% {name of scribe (YOU)}{Editor}{title of lecture}

\newcommand{\lecturer}{Tal Malkin}
\newcommand{\scribes}{Ariel Elbaz}
\newcommand{\lectureSummary}{\LaTeX \ introduction}
\newcommand{\lectureNumber}{0}
\newcommand{\lectureDate}{September 2, 2003}

\lecture{\lectureNumber}{\lectureDate}{\lecturer}{\scribes}{{\bf \lectureSummary}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%               Place body of SCRIBE notes after here                   %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section*{Summary}
This is an example latex file. You should use this file ({\tt
ITC0.tex}) as a template for scribing the lecture notes. Start by
modifying the lecture number and details. If you're scribing
lecture $n$, submit your edited file as ({\tt ITC$n$.tex}).


\section{Theorems, Proofs, etc.}

\begin{definition}

\end{definition}

\begin{theorem}
text of a theorem \dots
\end{theorem}
\begin{proof}
starting a proof \dots \quad \quad
and ending it
\end{proof}

\begin{claim}
text of a claim
\end{claim}

\begin{proof_sketch}
text of a proof sketch
\end{proof_sketch}

We can also {\em emphasize parts of the text}

\subsection{A subsection on primes}

\begin{definition}
  $p$ is a prime if $p$ is an integer that has no integral factors but itself and 1.
\end{definition}

\subsection*{More examples}

\begin{lemma}
text of a lemma
\end{lemma}

\begin{example}
text of an example
\end{example}

\section{Mathematical Equations}

Math equations can either be mixed with text,, such as $y = x + 2$ or $2^{2^{13}}$ or
$\frac {17!} {2^{34}}$, or else they can be in a sepeate line
$$ Pr[x \geq y] \leq \frac 1 3 $$
or on an automatically numbered equation
\begin{equation} \label{first equation}
\{ x \suchthat x \leq y \Rightarrow y \geq 0 \}
\end{equation}
We can refer to a specific equation by labelling them.
Equation \ref{first equation} defines the set of values $x$, such
that if $x$ is smaller than $y$, it must be the case that $y$ is at most $0$.
\\
Note: you will have to compile the LaTeX file {\bf twice} for equation references to appear
correctly.

More advanced equations
\begin{eqnarray*}
V_{s,0}^{\{q_0,q_1\}} &  =  V_{s,0}^{\{q_0\}} \ \cup  &
V_{s,1}^{\{q_0\}}\circ
\left(V_{1,1}^{\{q_0\}}\right)^* \circ
V_{1,0}^{\{q_0\}}
\\
V_{s,2}^{\{q_0,q_1\}} & =  V_{s,2}^{\{q_0\}} \ \cup  &
V_{s,1}^{\{q_0\}}\circ
\left(V_{1,1}^{\{q_0\}}\right)^* \circ
V_{1,2}^{\{q_0\}} =
V_{s,1}^{\{q_0\}}\circ
\left(V_{1,1}^{\{q_0\}}\right)^* \circ
V_{1,2}^{\{q_0\}}
\end{eqnarray*}

\section{Itemizing}
\begin{itemize}
  \item First item
  \item Second item
  \item[$\Rightarrow$] You can define the bullet shape that appears to the left.
    \begin{enumerate}
      \item Items can also be numbered
      \item And they can be nested
       \begin{enumerate}
        \item Just another item.
       \end{enumerate}
    \end{enumerate}
\end{itemize}


\section{Writing text}
The \LaTeX  compiler does it's own pagesetting. It converts any number of spaces to a single space, and concatantes sentences to fill the paragraph. You can spread one sentence
over
as
many
lines
as
you
want,
it
will
continue
as if it was written in a single line.
If you want to break a paragraph you need to leave an empty line.

When you want to verify some text not being spread across two lines, e.g. \mbox{"1 2 3 \dots 4 5 6 \dots 7 8 9"},
you can enclose it in {\tt mbox}. LaTeX treats it as a single letter and will never cut it in the middle.

Same text, without {\tt mbox}: \\
When you want to verify some text not being spread across two lines, e.g. "1 2 3 \dots 4 5 6 \dots 7 8 9",
you can enclose it in {\tt mbox}. LaTeX treats it as a single letter and will never cut it in the middle.


\section{Some Symbols}
Encryption scheme : ($\GEN, \ENC, \DEC$).

pair : \pair{a}{b}

Big O, small o :
$k = \bigO(n) , \epsilon = \smallo(1)$

complexity classes : \\ $
\logspace,
\RL,
\NL,
\polytime,
\NP,
\coNP,
\RP,
\BPP,
\ZPP,
\coNL,
\coRP,
\EXP,
\PSPACE,
\ACZ,
\IP,
\AM,
\coAM $


Number sets : $\Nats, \Reals, \Ints, \CC, \QQ, \Z, \Zp, \Zn, \Zp^*$

Logical operators : $\AND, \OR, \NOT, \EQUIV, \IMPLY $

\begin{theorem}[Fermat's little theorem]
If $p$ is a prime, then for any $a \in \Z_p^*$, $a^{p-1} \equiv 1 \modp$
\end{theorem}

\begin{definition}
A function $f \cc \bitset^n \to \bitset^{n+1}$ is a pseudo random generator \dots
\end{definition}

\anote{If the lecturer feels there are things to be added on some topic, they might appear as a note
inside the scribes.
This does not necessarily mean that the scribes are not good; Sometimes these notes may refer
to topics that are beyond the scope of the course.}



\end{document}