\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}