Prime Algorithms
Author:
Nadya
Last Updated:
9 years ago
License:
Creative Commons CC BY 4.0
Abstract:
Primality Tests and Factoring Algorithms
\begin
Discover why 18 million people worldwide trust Overleaf with their work.
Primality Tests and Factoring Algorithms
\begin
Discover why 18 million people worldwide trust Overleaf with their work.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Beamer Presentation
% LaTeX Template
% Version 1.0 (10/11/12)
%
% This template has been downloaded from:
% http://www.LaTeXTemplates.com
%
% License:
% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%----------------------------------------------------------------------------------------
% PACKAGES AND THEMES
%----------------------------------------------------------------------------------------
\documentclass{beamer}
\mode<presentation> {
% The Beamer class comes with a number of default slide themes
% which change the colors and layouts of slides. Below this is a list
% of all the themes, uncomment each in turn to see what they look like.
%\usetheme{default}
%\usetheme{AnnArbor}
%\usetheme{Antibes}
%\usetheme{Bergen}
%\usetheme{Berkeley}
%\usetheme{Berlin}
%\usetheme{Boadilla}
%\usetheme{CambridgeUS}
%\usetheme{Copenhagen}
%\usetheme{Darmstadt}
%\usetheme{Dresden}
%\usetheme{Frankfurt}
%\usetheme{Goettingen}
%\usetheme{Hannover}
%\usetheme{Ilmenau}
%\usetheme{JuanLesPins}
%\usetheme{Luebeck}
\usetheme{Madrid}
%\usetheme{Malmoe}
%\usetheme{Marburg}
%\usetheme{Montpellier}
%\usetheme{PaloAlto}
%\usetheme{Pittsburgh}
%\usetheme{Rochester}
%\usetheme{Singapore}
%\usetheme{Szeged}
%\usetheme{Warsaw}
% As well as themes, the Beamer class has a number of color themes
% for any slide theme. Uncomment each of these in turn to see how it
% changes the colors of your current slide theme.
%\usecolortheme{albatross}
%\usecolortheme{beaver}
%\usecolortheme{beetle}
%\usecolortheme{crane}
%\usecolortheme{dolphin}
%\usecolortheme{dove}
%\usecolortheme{fly}
%\usecolortheme{lily}
%\usecolortheme{orchid}
%\usecolortheme{rose}
%\usecolortheme{seagull}
%\usecolortheme{seahorse}
%\usecolortheme{whale}
%\usecolortheme{wolverine}
%\setbeamertemplate{footline} % To remove the footer line in all slides uncomment this line
%\setbeamertemplate{footline}[page number] % To replace the footer line in all slides with a simple slide count uncomment this line
%\setbeamertemplate{navigation symbols}{} % To remove the navigation symbols from the bottom of all slides uncomment this line
}
\usepackage{graphicx} % Allows including images
\usepackage{booktabs} % Allows the use of \toprule, \midrule and \bottomrule in tables
%----------------------------------------------------------------------------------------
% TITLE PAGE
%----------------------------------------------------------------------------------------
\title[Prime Algorithms]{Primality Tests and Factoring Algorithms} % The short title appears at the bottom of every slide, the full title is only on the title page
\author{Joel Barnett and Nadya DeBeers} % Your name
\institute[SRJC] % Your institution as it will appear on the bottom of every slide, may be shorthand to save space
{
Santa Rosa Junior College \\ % Your institution for the title page
%\medskip
%\textit{john@smith.com} % Your email address
}
\date{\today} % Date, can be changed to a custom date
\begin{document}
\begin{frame}
\titlepage % Print the title page as the first slide
\end{frame}
\begin{frame}
\frametitle{Overview} % Table of contents slide, comment this block out to remove it
\tableofcontents % Throughout your presentation, if you choose to use \section{} and \subsection{} commands, these will automatically be printed on this slide as an overview of your presentation
\end{frame}
%----------------------------------------------------------------------------------------
% PRESENTATION SLIDES
%----------------------------------------------------------------------------------------
%------------------------------------------------
\section{Fermat's Primality Test} % Sections can be created in order to organize your presentation into discrete blocks, all sections and subsections are automatically printed in the table of contents as an overview of the talk
%------------------------------------------------
%\subsection{Subsection Example} % A subsection can be created just before a set of slides with a common theme to further break down your presentation into chunks
%------------------------------------
\section{Application}
\begin{frame}{Application}
\frametitle{Application}
\begin{itemize}
\item It's fun, right?
\end{itemize}
\medskip
\medskip
The "real" mathematics of the "real" mathematicians, the mathematics of Fermat and Euler and Gauss and Abel and Riemann, is almost wholly "useless." ...It is not possible to justify the life of any genuine professional mathematician on the ground of the "utility" of his work. -— G. H. Hardy, \textit{A Mathematician’s Apology}, 1941
\end{frame}
%-------------------------------------
\begin{frame}{Application}
\begin{itemize}
\item Encryption systems rely on these "useless" number theories developed by Fermat and Euler.
\item Primes are the basis of encryption security
\end{itemize}
\end{frame}
%--------------------------------------
\begin{frame}{Primality tests}
\begin{itemize}
\item Simple Primality Tests
\item Fermat's Primality Algorithm
\begin{itemize}
\item Modulo Arithmetic
\item Fermat's Little Theorem
\item The algorithm
\item Flaws
\end{itemize}
\item Rabin-Miller Primality Test
\end{itemize}
\end{frame}
%-------------------------------------
\begin{frame}{Simple Primality Test}
Prime or Composite?
\begin{enumerate}
\medskip
\item 511
\item 73
\end{enumerate}
\end{frame}
%--------------------------------------
\begin{frame}{Simple Primality Test}
Prime or Composite?
\begin{enumerate}
\medskip
\item 511 Composite
\\
$\frac{511}{2}=2$ \hfill $\frac{511}{3}=170.33$\hfill $\frac{511}{5}=102.2$\hfill . . .\hfill $\frac{511}{7}=73$
\item 73
\end{enumerate}
\end{frame}
%--------------------------------------
\begin{frame}{Simple Primality Test}
Prime or Composite?
\begin{enumerate}
\medskip
\item 511 Composite
\item 73
\\
$\frac{73}{2}=36.5$ \hfill $\frac{73}{3}=24.33$\hfill $\frac{73}{5}=18.25$\hfill $\frac{73}{7}=10.43$\hfill $\frac{73}{8}=9.13$\hfill$\frac{73}{9}=8.11$
\\
\medskip Note: We stop at $\lceil{}\sqrt[]{73}\rceil{}=\lceil{} 8.544 \rceil{}=9$
\end{enumerate}
\end{frame}
%--------------------------------------
\begin{frame}{Simple Primality Test}
This is a long process!
\end{frame}
%--------------------------------------
\begin{frame}{Simple Primality Test}
This is a long process!
\medskip
\\Testing a 400 digit number ($10^{400}$) requires checking approximately ($\sqrt[]{10^{400}}10^{200}$) factors!
\end{frame}
%--------------------------------------
\begin{frame}{Simple Primality Test}
This is a long process!
\medskip
\\Testing a 400 digit number ($10^{400}$) requires checking approximately ($\sqrt[]{10^{400}}10^{200}$) factors!
\medskip
\\Scientists estimate the life of the universe to be only $10^{18}$ seconds, rendering this process impractical.
\end{frame}
%--------------------------------------
\begin{frame}{Fermat's Method}
New Strategy!
\end{frame}
%--------------------------------------
\begin{frame}
\frametitle{Modulo}
Background\\
\begin{block}{Modulo}
\underline{Definition}: Let \textit{m} and \textit{n} be integers and let \textit{d} be a positive integer. We say that \textit{m} is congruent to \textit{n} modulo \textit{d} if, and only if, \textit{d} divides \textit{m-n} and write:\\
\medskip
$m\equiv{n}\mod{d}\iff d |(m-n)$\\
\medskip
Sometimes this is written in the form:\\
$m\equiv n \mod d \iff m \mod{d}=n\mod{d}$
\medskip
\end{block}
Example:\\
$15\equiv 8\mod 7$ because $7|(15-8)$\\
Or $15\equiv 8\mod 7$ because $15\mod{7}=1$ and $8\mod{7}=1$
\end{frame}
%------------------------------------------------
\begin{frame}{Fermat's Method}
\begin{block}{Fermat's Little Theorem}
If \textit{p} is a prime number, then, $a^p\equiv a\mod{p}, \forall a\in \mathbb{Z}$.\\
\medskip
This theorem is also often rearranged to the form:\\
\medskip $a^{p-1}\equiv 1\mod{p}$
\medskip
\end{block}
\end{frame}
%------------------------------------------------
\begin{frame}{Fermat's Method}
Shortened Proof:
\begin{block}{Fermat's Little Theorem}
If \textit{p} is a prime number, then, $a^p\equiv a\mod{p}, \forall a\in \mathbb{Z}$.\\
\medskip
\end{block}
\underline{Proof} (by induction): Let \textit{p} be any prime number.\\
\smallskip
Base Case: $1^{p} \equiv 1 \mod{p}\iff p|(1^p-1) $, which is true.\\
\smallskip
Inductive Assumption: Assume $k^p\equiv k\mod{p}$ for some integer \textit{k}.\\
That is, assume $p|(k^p-k)$ is true.
\end{frame}
%--------------------------------------------------
\begin{frame}{Fermat's Method}
That is, assume $p|(k^p-k)$ is true.\\\textit{[We must show the (k+1) case follows]}.\\
That is, show $(k+1)^p\equiv (k+1)\mod{p}$\\
$\iff p|(k+1)^p-(k+1)$ \\
$\iff(k+1)^p-(k+1)=p*q, \exists q \in \mathbb{Z}$\\
Using the binomial theorem, the left hand side of above equation becomes:\\$k^p+\binom{p}{1}k^{p-1}+\binom{p}{2}k^{p-2}+ . . . +\binom{p}{p-1}k+1-(k+1)=k^p-k+[\binom{p}{1}k^{p-1}+\binom{p}{2}k^{p-2}+ . . . +\binom{p}{p-1}k]$\\Now,$ \binom{p}{j}=\frac{p!}{j!(p-j)!}$ where \textit{j} is some integer. Since \textit{p} is prime and $j<p$, there is a factor of \textit{p} in the numerator, and no factors of \textit{p} in the denominator.\\
Thus, $\binom{p}{1}k^{p-1}+\binom{p}{2}k^{p-2}+ . . . +\binom{p}{p-1}k=p*m, \exists m \in \mathbb{Z}$
\end{frame}
%--------------------------------------------------
\begin{frame}{Fermat's Method}
Returning to what we were trying to show: $(k+1)^p-(k+1)=p*q$\\
$\iff k^p-k+[\binom{p}{1}k^{p-1}+\binom{p}{2}k^{p-2}+ . . . +\binom{p}{p-1}k]=p*q$\\
But, $\binom{p}{1}k^{p-1}+\binom{p}{2}k^{p-2}+ . . . +\binom{p}{p-1}k=p*m$, so $k^p-k+[\binom{p}{1}k^{p-1}+\binom{p}{2}k^{p-2}+ . . . +\binom{p}{p-1}k]=k^p-k+p*m$\\
Thus, $k^p-k+[\binom{p}{1}k^{p-1}+\binom{p}{2}k^{p-2}+ . . . +\binom{p}{p-1}k]=p*q$
$\iff k^p-k +p*m=p*q$\\$\iff k^p-k=p(q-m)$\\$p|(k^p-k)$, which is true by our inductive assumption.
Thus $a^p\equiv a\mod{p}, \forall a>1$. To prove this for all integers, the inductive direction
\end{frame}
%--------------------------------------------------
\begin{frame}
\frametitle{Blocks of Highlighted Text}
\begin{block}{Block 1}
Lorem ipsum dolor sit amet, consectetur adipiscing elit. Integer lectus nisl, ultricies in feugiat rutrum, porttitor sit amet augue. Aliquam ut tortor mauris. Sed volutpat ante purus, quis accumsan dolor.
\end{block}
\begin{block}{Block 2}
Pellentesque sed tellus purus. Class aptent taciti sociosqu ad litora torquent per conubia nostra, per inceptos himenaeos. Vestibulum quis magna at risus dictum tempor eu vitae velit.
\end{block}
\begin{block}{Block 3}
Suspendisse tincidunt sagittis gravida. Curabitur condimentum, enim sed venenatis rutrum, ipsum neque consectetur orci, sed blandit justo nisi ac lacus.
\end{block}
\end{frame}
%------------------------------------------------
\begin{frame}
\end{frame}
\begin{frame}
\frametitle{Multiple Columns}
\begin{columns}[c] % The "c" option specifies centered vertical alignment while the "t" option is used for top vertical alignment
\column{.45\textwidth} % Left column and width
\textbf{Heading}
\begin{enumerate}
\item Statement
\item Explanation
\item Example
\end{enumerate}
\column{.5\textwidth} % Right column and width
Lorem ipsum dolor sit amet, consectetur adipiscing elit. Integer lectus nisl, ultricies in feugiat rutrum, porttitor sit amet augue. Aliquam ut tortor mauris. Sed volutpat ante purus, quis accumsan dolor.
\end{columns}
\end{frame}
%------------------------------------------------
\section{Second Section}
%------------------------------------------------
\begin{frame}
\frametitle{Table}
\begin{table}
\begin{tabular}{l l l}
\toprule
\textbf{Treatments} & \textbf{Response 1} & \textbf{Response 2}\\
\midrule
Treatment 1 & 0.0003262 & 0.562 \\
Treatment 2 & 0.0015681 & 0.910 \\
Treatment 3 & 0.0009271 & 0.296 \\
\bottomrule
\end{tabular}
\caption{Table caption}
\end{table}
\end{frame}
%------------------------------------------------
\begin{frame}
\frametitle{Theorem}
\begin{theorem}[Mass--energy equivalence]
$E = mc^2$
\end{theorem}
\end{frame}
%------------------------------------------------
\begin{frame}[fragile] % Need to use the fragile option when verbatim is used in the slide
\frametitle{Verbatim}
\begin{example}[Theorem Slide Code]
\begin{verbatim}
\begin{frame}
\frametitle{Theorem}
\begin{theorem}[Mass--energy equivalence]
$E = mc^2$
\end{theorem}
\end{frame}\end{verbatim}
\end{example}
\end{frame}
%------------------------------------------------
\begin{frame}
\frametitle{Figure}
Uncomment the code on this slide to include your own image from the same directory as the template .TeX file.
%\begin{figure}
%\includegraphics[width=0.8\linewidth]{test}
%\end{figure}
\end{frame}
%------------------------------------------------
\begin{frame}[fragile] % Need to use the fragile option when verbatim is used in the slide
\frametitle{Citation}
An example of the \verb|\cite| command to cite within the presentation:\\~
This statement requires citation \cite{p1}.
\end{frame}
%------------------------------------------------
\begin{frame}
\frametitle{References}
\footnotesize{
\begin{thebibliography}{99} % Beamer does not support BibTeX so references must be inserted manually as below
\bibitem[Smith, 2012]{p1} John Smith (2012)
\newblock Title of the publication
\newblock \emph{Journal Name} 12(3), 45 -- 678.
\end{thebibliography}
}
\end{frame}
%------------------------------------------------
\begin{frame}
\Huge{\centerline{The End}}
\end{frame}
%----------------------------------------------------------------------------------------
\end{document}