\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{18: Quadratic Reciprocity}{CS681}{Piyush P Kurur}{Ramprasad Saptharishi}

\section*{Overview}

Polynomial factorization and randomized primality testing were one of
the first examples of the power of randomization. Two standard
algorithms for primality testing (randomized) are the Miller-Rabin
test and the Solovay-Strassen test. 

We shall build some theory on quadratic reciprocity laws before we get
into the Solovay Strassen test. 

\section{Quadratic Reciprocity}

The reciprocity laws are closely related to how primes split over {\em
number fields.} Let us first understand what these number fields are. 

\begin{definition}
An algebraic integer over $\Q$ is an element $\zeta$ such that it is a
root of a monic polynomial in $\Z[X].$ For example, the
number $\frac{1}{2} + i\frac{\sqrt{3}}{2}$ is an algebraic integer as
it is a root of $x^2 -x+1.$ 

A number field is a finite extension of $\Q.$ One could think of this
as just adjoining an algebraic number to $\Q.$
\end{definition}

Note that number fields are strange objects. They may not even be
UFDs. We saw the example when we consider $\Q(\sqrt{-5})$, the number
$6$ factors as both $3\times 2$ and $(1+\sqrt{-5})(1 - \sqrt{-5}).$
However, if one were to consider factorization over ideals, they
form unique factorizations. 

\subsection{The Legendre Symbol}

Fix an odd prime $p.$ We want to study equations of the form $X^2 - a$
over $\F_p.$ What does it mean to say that this has a solution in
$\F_p?$ It means that $a$ has a square-root in $\F_p$ or $a$ is a
square in $\F_p.$ The legendre symbol captures that.

\begin{definition}
For $a\in \F_p$, the legendre symbol $\legendre{a}{p}$ is defined as
follows:
$$
\legendre{a}{p} = \begin{cases}0 & \text{if $p\mid a$}\\-1 &\text{if $a$ is
not a square modulo $p$}\\1 & \text{if $a$ is a square modulo $p$}\end{cases}
$$
\end{definition}

\begin{proposition}
$$
\legendre{ab}{p} = \legendre{a}{p}\legendre{b}{p}
$$
\end{proposition}
The proof is fairly straight forward; just consider them case by case
when they are $-1,0,1.$

Thus, the above proposition tells us that the $\legendre{\cdot}{p}$ is
a homomorphism from $\Z/p\Z$ to $\inbrace{-1,0,1}.$\\

Another observation is that since $\F_p^\star$ is cyclic, there is a
generator $b.$ Then we can write $a = b^t.$ We then have,
$$
a = \begin{cases} 0 & \text{if $p\mid a$}\\-1 & \text{if $a$ is not a
square modulo $p$}\\1& \text{if $a$ is a square modulo $p$}\end{cases}
$$
and therefore $\legendre{a}{p} = a^{\frac{p-1}{2}}.$\\

Note that $x^2 = y^2 \implies x=y$ or $x=-y$ and therefore, the number
of squares in $\F_p^\star$ is exactly $\frac{p-1}{2}.$ And if the
generator of the group is a quadratic non-residue (not a square), then
any odd power of the generator is also a non-residue. 

\section{Quadratic Reciprocity Theorem}
\begin{theorem}
Let $p$ and $q$ be odd primes (not equal to each other). Then
\bea{
\legendre{2}{p} & = & (-1)^{\frac{p^2 -1}{8}}\\
\legendre{p}{q}\legendre{q}{p} & = &(-1)^{\frac{p-1}{2}\frac{q-1}{2}}
}
\end{theorem}
\begin{proof}
We shall prove the part of $\legendre{2}{p}$ in this class and do the
other in the next. The idea is to go to a field extension (if
necessary) and evaluate certain elements in two ways to get what we
want. In the case of $\legendre{2}{p}$ we shall go to the extension
$\F_p(i)$ where $i$ is a square root of $-1.$

Firstly note that this needn't be a proper extension at all. For
example, in $\F_5$, we already have a root of $-1$ which is $2.$
Infact, for every prime of the form $1\bmod{4}$, we have a square root
of $-1.$ So we will go to an extension if necessary. 

Now set $\tau = 1+i.$ We know that $\tau^2 = 1 - 1 + 2i = 2i$ and
$\tau^p = 1 + i^p$ in $\F_p.$ We could also evaluate $\tau^p$ as
$\tau\cdot(\tau^2)^{\frac{p-1}{2}}.$ Also $(1+i)^{-1} = \frac{1-i}{2}.$

\bea{
1+i^p & = & \tau^p\\
 & = & \tau (2i)^{\frac{p-1}{2}}\\
 & = & (1+i) 2^{\frac{p-1}{2}}i^{\frac{p-1}{2}}\\
\implies \frac{(1+i^p)(1 - i)}{2} & = &
 2^{\frac{p-1}{2}}i^{\frac{p-1}{2}}\\
\implies \frac{1+i^p - i - i^{p+1}}{2} & = &
\legendre{2}{p}i^{\frac{p-1}{2}}
}

\noindent
{\bf Case 1:} When $p = 1\bmod{4}$

Then $i\in \F_p$ and the above equation reduces to 
\bea{
\frac{1 + i - i +1}{2} & = & \legendre{2}{p}(-1)^{\frac{p-1}{4}}\\
\implies \legendre{2}{p} &= &(-1)^{\frac{p-1}{4}}
}

\noindent
{\bf Case 2:} When $p = 3\bmod{4}$
\bea{
\frac{1 - i - i - 1}{2} & = & \legendre{2}{p}i^{\frac{p-1}{2}}\\
\implies i^3 & = & \legendre{2}{p}i^{\frac{p-1}{2}}\\
\implies \legendre{2}{p} & = & i^{\frac{1 - p}{2}+3} = i^{\frac{8 -
(1+p)}{4}}\\
& = & (-1)^{\frac{p+1}{4}}
}

Therefore, 
$$
\legendre{2}{p} = \begin{cases} (-1)^{\frac{p-1}{4}} & p = 1\bmod{4}\\
(-1)^{\frac{p+1}{4}} & p = 3\bmod{4}\end{cases}
$$
and combining the two, we get
$$
\legendre{2}{p} = (-1)^{\frac{p^2 - 1}{8}}
$$
\end{proof}

The proof of the other part is very similar. We consider a similar
$\tau$ and evaluate $\tau^p$ in two different ways to get to our
answer. We shall do this in the next class. 
\end{document}