%% This LaTeX-file was created by <jl> Wed Apr 15 14:13:00 1998
%% LyX 0.12 (C) 1995-1998 by Matthias Ettrich and the LyX Team

%% Do not edit this file unless you know what you are doing.
\documentclass{article}
\usepackage[T1]{fontenc}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\newcommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\spacefactor1000}

\makeatother

\begin{document}

Day 25 4/15/98 ``You have to squint a little.''


\section{Primality Testing}

Is n prime or composite? We want an algorithm that runs in \( (\log n)^{k} \).


\subsection{Fermat's little theorem}

If \( p \) is prime with \( 1<a<p \) then \( a^{p-1}=1\textrm{mod}p \) 


\subsection{contrapositive}

If \( 1<a<n \) and \( a^{n-1}\neq 1\textrm{mod}n \) then \( n \) is composite.


\subsection{Primality test heuristic}

\begin{enumerate}
\item guess \( a \)
\item check if \( a^{n-1}\neq 1\textrm{mod}n \) If yes output 'composite' otherwise output 'possibly prime'
\end{enumerate}
This heuristic fails for certain numbers known as Carmicheal numbers. Example:

\( 561=3*11*17 \)

If \( GCD(a,n)=1 \) then \( a^{n-1}=1\textrm{mod}n \)

\( n \) is Carmicheal if 

\begin{enumerate}
\item n is composite
\item \( \lambda (n) \) divides \( n-1 \) with \( n=p_{1}^{\alpha _{1}}...p_{m}^{\alpha _{m}} \) and \( \lambda (n)=LCM(p_{1}^{\alpha _{1}-1}(p_{1}-1),...,p_{m}^{\alpha _{m}-1}(p_{m}-1)) \)
\end{enumerate}
Carmicheal numbers actually always have \( \alpha _{i}=1 \) and \( m\geq 3 \).


\subsection{More number theory (from gauss)}

\( \pm 1 \) are the only roots of \( x^{2}=1\textrm{mod}p \) with \( p \) prime


\subsection{Better algorithm}

A(\( a,n \))

let \( n-1=2^{t}u \) for \( u \) odd

\begin{enumerate}
\item if \( n=2 \) output 'prime'
\item if \( n \) is even, output 'composite'
\item if \( a^{u}=1\textrm{mod}n \) output 'possibly prime'
\item if \( a^{2^{j}u}=-1\textrm{mod}n \) for \( 1\leq j<t \) output 'possibly prime'
\item else, output 'composite'
\end{enumerate}

\subsection{Theorem}

half the \( a\in [1,n] \) for \( n \) composite will have that \( A(a,n) \) return 'composite'. 

This means that if you run \( A(a,n) \) 100 times each time putting out 'possibly prime'
then either \( n \) is prime or you are very unlucky.


\subsection{Some number theory}

\begin{itemize}
\item \( Z_{n} \) = the ring with \( +,*\textrm{mod}n \) = \( \{0,1,...,n-1\} \)
\item \( |Z_{n}|=n \) 
\item \( R,R' \) = rings then \( R\times R'=\{(r,r')|r\in R,r'\in R'\} \) is a ring with \( (r_{1},r^{'}_{1})+(r_{2},r^{'}_{2})=(r_{1}+r_{2},r_{1}^{'}+r_{2}^{'}) \).
\end{itemize}

\subsubsection{Chinese remainder theorem}

For \( n=p_{1}^{\alpha _{1}}*...*p_{m}^{\alpha _{m}} \)

we have: \( Z_{n}\simeq Z_{p_{1}^{\alpha _{1}}}\times Z_{p_{m}^{\alpha _{m}}} \)

For \( a\in Z_{n} \) \( a\rightarrow (a\textrm{mod}p_{1}^{\alpha _{1}},...,a\textrm{mod}p_{m}^{\alpha _{m}}) \)


\subsubsection{multiplicative group}

\( Z_{n}^{*}=\{a\in Z_{n}|\exists a'\textrm{with }a'*a=1\textrm{mod}n\} \)\( =\{a\in Z_{n}|GCD(a,n)=1\} \)

If \( p \) is an odd prime, then \( Z_{p}^{*} \) is a cyclic group, which means every invertible
element can be found by multiplying some base (a 'generator') \( \textrm{mod}p \).


\subsection{Pulling all the facts together}

if \( n=5*7 \) then \( Z_{35}^{*}\simeq Z_{5}^{*}\times Z_{7}^{*}\simeq C_{4}*C_{6} \) then there will be many solutions to \( x^{2}=1\textrm{mod}35 \).

For 35, \( x=1,6,-6,34 \) will work.

Working in the decomposed group, we get:

\begin{enumerate}
\item \( 1\rightarrow (1,1) \)
\item \( 6\rightarrow (1,-1) \)
\item \( -6\rightarrow (-1,1) \)
\item \( 34\rightarrow (-1,-1) \)
\end{enumerate}
\( 6^{2}=1\textrm{mod}35 \) = a 'nontrivial square root of 1' => 35 is composite.

\end{document}