\documentclass[12pt]{article}

\usepackage{comment}
\usepackage{amsmath}
\usepackage{amssymb}  % for \nmid

\newcommand{\D}{{\mathbb D}}
\newcommand{\G}{{\mathbb G}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\succc}{{\rm succ}}
\newcommand{\pred}{{\rm pred}}

\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\Ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}

\begin{document}


\centerline{Homework 05, MORALLY Due March 10} 

\newif{\ifshowsoln}
\showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks.

\begin{enumerate}
\item
(0 points)
What is your name.

\vfill 

\centerline{\bf GO TO THE NEXT PAGE}

\newpage


\item
(40 points)
\begin{enumerate}
\item
(0 points) 
Write a program that will, given $p,g,a,b$ computes the following:

$g^a \pmod p$, $g^b \pmod p$, $g^{ab} \pmod p$

(The intended input is that $p$ is a prime and $g$ is a generator;
however, the program still works if this is not the case.)
Do not hand anything in.

\item 
(20 points) 
Alice and Bob are carrying out the Diffie-Helman Protocol with $p=521$ and $g=3$.
Output a table of the following form where you generate the 50 $(a,b)$'s at random. 
We give the first 3 rows of what the table might look like.
Note that the numbers are fictional and you may have different
pairs then we have. 

\begin{tabular}{|c|c|c|c|c|}
\hline
$a$ & $b$ & Alice Sends $3^a$ & Bob Sends $3^b$ & Secret $3^{ab}$ \cr
\hline
2   &   17  &   33              &    191           &    330         \cr
33  &   44  &   55              &    200           &    40          \cr
18  &  344  &   500             &    201           &    47          \cr
\hline
\end{tabular}

How often does each secret occur?


\item
(20 points) 
Alice and Bob are carrying out the Diffie-Helman Protocol with $p=521$ and $g=43$.
Output a table of the following form where you generate  50 $(a,b)$'s at random
(they can and will be different from the $(a,b)$'s you used on the problem 2b). 
We give the first 3 rows of what the table might look like.
Note that the numbers are fictional and you may have different
pairs then we have. 

\begin{tabular}{|c|c|c|c|c|}
\hline
$a$ & $b$ & Alice Sends $43^a$ & Bob Sends $43^b$ & Secret $43^{ab}$ \cr
\hline
7   &   29  &   37              &    391           &    130         \cr
13  &   14  &   15              &    100           &    10          \cr
98  &  349  &   509             &    291           &    97          \cr
\hline
\end{tabular}

How often does each secret occur?

\item 
(0 points, do not hand anything in)
Does one of the $g$ values seem better than the other?
(The answer will be YES)
Why is one better than the other?
\end{enumerate}

\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item 
(30 points)
\begin{enumerate}
\item
(10 points)
Prove that $10^{1/3}$ is irrational WITHOUT USING unique factorization. 
\item
(10 points)
Prove that $10^{1/3}$ is irrational USING unique factorization. 
\item
(10 points)
Prove $101^{1/4}$ is irrational USING unique factorization
\item
(0 points, don't hand anything in) 
Would the proof that $101^{1/4}$ have been longer or shorter if you
did it WITHOUT USING unique factorization.
\end{enumerate}

\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item 
(30 points) Prove that, for every prime $p$, $p^{1/3}$ is irrational.
Use Unique Factorization. 
\end{enumerate}

\end{document}