\documentclass[12pt]{article}

\title{21-320 Homework Set 7}
\author{James Cummings}

\begin{document}

\maketitle

  Due Mon 17 April. I encourage submission by email (preferably as a 
  PostScript file) to {\tt maplehw@asdb.math.cmu.edu}.

\begin{enumerate}

\item   A celebrated theorem in number theory (the Prime Number
Theorem, proved by  Chebyshev) states that there are roughly 
  $\displaystyle \frac{n}{\ln(n)}$ primes less than $n$.
\begin{enumerate}
\item Use the Prime Number Theorem to predict the number of primes $p$
  such that $10^6 < p < 10^6 + 10^5$.
\item Compute the exact number of such primes and compare your answer 
  with the approximate one.
\end{enumerate}

\item  Recall that $\phi(N)$ is the number of integers $a$ such that
  $0 < a < N$ and $\gcd(a, N) = 1$. Recall also that if $N$ is the
  product of distinct primes $p$ and $q$ then 
  $\phi(N) = (p-1)(q-1)$.

  
I tell you that $N$ is a product of two distinct primes, and also that
$N$ equals
\begin{verbatim}
 71230886527397475528902959842062683921344888484583255939615\
 1192609812793082691907457433512778147335174624061436571100\
 3444923859947701073568621805325046523376370966829465179246\
 3818541786574184942207665344863964955096676339119018031568\
 2002829226033237
\end{verbatim} 
 and $\phi(N)$ equals
\begin{verbatim}
 71230886527397475528902959842062683921344888484583255939615\
 1192609812793082691907457433512778147335174624061436571100\
 3444923101084226930916603169299614335297484083504289690567\
 7337340996860357644514198720353287484747268662052904940993\
 0609316431583360
\end{verbatim}

  Factorise $N$.

\item  My public RSA key is $(N, e)$ where $N$ is the integer from the
previous question and $e$ equals  
\begin{verbatim}
58782632971472609735977247854813679207830011036574028624263\
1973266302366965856861031085647814053119392611194525720896\
5269339899649888947805070270367988884937655567025895568812\
5223344206281537099596120465260142417879939199670320661032\
6378345899605099
\end{verbatim}


  Decode the message 
\begin{verbatim}
 130726090583641062363608445649854078411575063392373340322\
 341934527302113161045214653377609615790627337225903403387\
 278456312292589343673401228690415701744654751681855468730\
 138502814996007032411881020517855674597193797388383640080\
 44350030226450422007
\end{verbatim}
  which was encrypted using the key $(N, e)$. 


  (I coded this using the convention 0=blank, 1=A,2=B etc from class)


\item  A positive integer $n > 1$ is called a {\em Carmichael number}
  if and only if it satisfies all of the following conditions:
\begin{enumerate}
\item $n$ is not prime.
\item For all integers $b$ with $0 < b < n$, if
  $gcd(b, n) = 1$ then $b^{n-1}$ is congruent to $1$ modulo $n$.
\end{enumerate}

  Find as many Carmichael numbers as you can. 
  Encouraging hint: there is at least one Carmichael number
 less than one thousand.


\item  It's a nice fact from number theory that if $a$ and $b$ are 
  non-zero integers and $d= gcd(a, b)$ then there are integers
  $m$ and $n$ such that $d = m a + n b$. For example
  the gcd of $8$ and $14$ is $2$, and $2 = 3 \times 14 - 5 \times 8$.

  Write a program which takes $a$ and $b$ as arguments and returns 
  a suitable pair $m, n$.


\end{enumerate}

\end{document} 






