\begin{document}
\documentclass[11pt]{article}

\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{algorithmic}
\usepackage{algorithm}
\usepackage{complexity}
\usepackage{graphicx}

\usepackage{palatino} %what a beautiful font!


\newcommand{\handout}[5]{
  \noindent
  \begin{center}
    \framebox[\textwidth]{
      \vbox{
        \hbox to \textwidth { {\bf #2}\hfill {\bf Computational Number Theory }
       }
        \vspace{4mm}
        \hbox to \textwidth { {\Large \hfill #5  \hfill} }
        \vspace{2mm}
        \hbox to \textwidth { {\em #3 \hfill #4} }
      }
    }
  \end{center}
  \vspace*{4mm}
}

\newcommand{\lecture}[4]{\handout{#1}{#2}{Instructor: #3}{Scribe:
    #4}{Lecture #1}}

\newtheorem{theorem}{Theorem}
\newtheorem{theorem*}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[]{Fact}
\newtheorem{subclaim}[theorem]{Subclaim}

% my custom commands
\newcommand{\inparen}[1]{\left(#1\right)}             %\inparen{x+y}  is (x+y)
\newcommand{\inbrace}[1]{\left\{#1\right\}}           %\inbrace{x+y}  is {x+y}
\newcommand{\insquar}[1]{\left[#1\right]}             %\insquar{x+y}  is [x+y]
\newcommand{\inangle}[1]{\left\langle#1\right\rangle} %\inangle{A}    is <A>
\newcommand{\abs}[1]{\left|#1\right|}                 %\abs{x}        is |x|
\newcommand{\norm}[1]{\left\Vert#1\right\Vert}        %\norm{x}       is ||x||
\newcommand{\union}{\cup}
\newcommand{\Union}{\bigcup}
\newcommand{\intersection}{\cap}
\newcommand{\Intersection}{\bigcap}
\newcommand{\super}[2]{#1^{\inparen{#2}}}             %\super{G}{i-1} is G^{(i-1)}
\newcommand{\setdef}[2]{\inbrace{{#1}\ : \ {#2}}}
\newcommand{\inv}[1]{#1^{-1}}
\newcommand{\inrpdt}[2]{\left\langle{#1},{#2}\right\rangle}%\inrpdt{x}{y} is <x,y>.
\newcommand{\pderiv}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\iso}{\cong}
\newcommand{\bea}[1]{\begin{eqnarray*} #1 \end{eqnarray*}}
\newcommand{\legendre}[2]{\inparen{\frac{#1}{#2}}}

% Commands specific to this file
% TODO: Find the right way to typeset group index
\DeclareMathOperator{\Sym}{Sym}
\newcommand{\gpidx}[2]{\insquar{#1 : #2}}             %\gpidx{H}{K}   is [H : K]
\newcommand{\gpigs}[2]{\gpidx{\super{G}{#1}}{\super{G}{#2}}} %Group index of g super ...
\newcommand{\llhd}{\!\!\lhd\!\!\lhd}
\newcommand{\roundoff}[1]{\left\lfloor #1 \right\rceil}


% \newcommand{\ceil}[1]{\lceil #1 \rceil}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\F}{\mathbb{F}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\renewcommand{\R}{\mathbb{R}}
\renewcommand{\C}{\mathbb{C}}

%for algorithms
\renewcommand{\algorithmicrequire}{\textbf{Input:}}

% Problems we look at
\newcommand{\GIso}{\lang{Graph\text{-}Iso}} %Without \text, ugly minus instead of hyphen.
\newcommand{\GAut}{\lang{Graph\text{-}Aut}}
\newcommand{\SStab}{\lang{Set\text{-}Stab}}

%for Quantum computing
\newcommand{\q}[1]{\left|#1\right\rangle}


\lecture{17: Primality is in $\NP\intersection \coNP$}{CS681}{Piyush P Kurur}{Ramprasad Saptharishi}

\section*{Overview}

We shall get into primality testing for integers in the next
few classes. We shall build up the details starting with showing that
it is in $\NP\intersection\coNP,$ discuss randomized algorithm, and
then finally get into deterministic polynomial time testing. 

We shall prove Pratt's result that it is in $\NP\intersection \coNP.$

\section{Pratt's Theorem}

The problem is the following: we are given a number $N$ as input and
we want to check if this is prime. 

Remember that the input is given in binary. It would be trivial if $N$
was specified in unary in which case the input size is $N$ and
hence primality testing in $O(N^c)$ is trivially accomplished by
checking every number less than $N$ if it's a factor or not.

The input is provided in binary and therefore we are looking for an
algorithm that runs in time polynomial in the input size, which is
$\log N.$

Recall the definition of the classes $\NP$ and $\coNP.$

\begin{definition}
$\NP$ is the class of languages $L$ such there exists a polynomial
time verification scheme $A(x,y)$ such that $x\in L$ if and only there
exists a witness $y$ such that $|y| < |x|^c$ for some constant $c$ and
$A(x,y) = 1.$

$\coNP$ is the class of languages $L$ such that $\bar{L}\in \NP.$
\end{definition}

To get a more intuitive picture, $\NP$ is the class of problems that
have very short proofs or witnesses. Though it might not be clear if
$x\in L$, given a witness $y$, it is easy to check that $(x,y)$
is a proper solution. For example, sudoku. It might be hard to find a
solution but once someone gives us a solution, it is easy to check if
the solution is correct. 

One could also think of this as guessing a witness $y$ and verifying
it using $A.$

Here is an obvious observation:
\begin{observation}
Primality testing is in $\coNP.$
\end{observation}

This equivalent to saying that checking if a number $N$ is composite is in
$\NP$ which is immediate since the witness is the factor $d$ of the
number. Hence, our verification scheme $A(N,d)$ is just checking if
$d$ divides $N.$

Pratt showed that primality testing is infact in $\NP.$

\begin{theorem}
Primality testing is in $\NP.$
\end{theorem}
\begin{proof}
Note that the group $(\Z/N\Z)^\star$ is of order $N-1$ if and only if
$N$ is prime. And more over, it is a cyclic group of order $N-1$ if
and only if $N$ is a prime. Thus, we shall find a witness or a
certificate that the group is cyclic. 

How do we show that a group is cyclic? We guess a generator $a.$ If we
are able to show that $a^n\neq 1$ for any $n<N-1$, we are done. Note
that $a^{N-1}=1$ anyway. Therefore, we just need to check that
$a^{(N-1)/p_i}\neq 1$ for every prime divisor $p_i$ of $N-1.$

Therefore, we not only guess the generator $a$, we guess the factors
$p_1,p_2, \cdots, p_k$ of $N-1.$ But how do we know that the guessed
$p_i$s are indeed primes? We guess its witnesses too; induction!
Aren't we going in circles? Actually no since the numbers $p_i$s are
quite small and it still won't blow up the size of the final
certificate.

Let us try and see how large the witness/certificate can get. How
large can the prime factors of $N-1$ be? Since $N$ is prime , $N-1$ is
certainly composite (unless $N$ was 2, a worthless case which can be
handled right at the beginning). The largest factor of $N-1$ can be of
size atmost $\sqrt{N}.$ How many factors can there exist? Atmost
$\log(N-1)$ of them. Thus if $N - 1 = p_1p_2\cdots p_k$ then our
witness would be $(a,p_1,p_2, \cdots, p_n)$ and the certificates of
each of the $p_i$s. The input is of size $\log N$
and let $S(l)$ be the size of the witness for input of length $l$. Then:
\bea{
S(\log N) & = &\log^2N + S(\log p_1)+S(\log p_2)+\cdots +S(\log p_k)\\
       & = & \log^2N + (\log p_1)^c + (\log p_2)^c + \cdots + (\log
       p_k)^c\\
       & \leq & \log^2N + (\log p_1 + \log p_2 + \cdots + \log
       p_k)^c\\
       & = & \log^2N + (\log (N-1))^c\\
       & = & O((\log N)^c)
}
And since the witness is just polynomially bounded in the size of the
input, we can guess the entire certificate and verify. Thus
primality testing is in $\NP.$
\end{proof}

And since primality is in $\NP$ and $\coNP$, it is in $\NP\intersection\coNP.$
\end{document}