% encry.tex
% RSA Encryption Project
\font\bigrm=cmr17
\font\medrm=cmr12
\font\medbf=cmbx12
\def\sc{\it}
\def\sectioncount{\count11}
\sectioncount=0
\def\theoremcount{\count12}
\theoremcount=0
\def\lemmacount{\count13}
\lemmacount=0
\def\corollarycount{\count14}
\corollarycount=0
\def\exerciseno{\count15}
\exerciseno=0
\def\algorithmcount{\count16}
\algorithmcount=0
\def\figurecount{\count17}
\figurecount=0
\def\ex{\advance\exerciseno by 1
        \item{\the\exerciseno.}
       }
\def\section#1{\advance\sectioncount by 1
     \medskip
     {\par \noindent \bf\the\sectioncount.\enskip #1.}
     \medskip
%     \headline={{\sl #1\hfil\the\pageno}}
     \theoremcount=0
     \lemmacount=0
     \corollarycount=0
    }
\long\def\longtheorem#1{\advance\theoremcount by 1
      \medskip
      {\bf\noindent Theorem \the\sectioncount.\the\theoremcount\ :
      \enskip}{\sl #1}
      \medskip
    }
\def\theorem#1{\advance\theoremcount by 1
      \medskip
      {\bf\noindent Theorem \the\sectioncount.\the\theoremcount\ :
      \enskip}{\sl #1}
      \medskip
    }
\long\def\longlemma#1{\advance\lemmacount by 1
      \medskip
      {\bf\noindent Lemma \the\sectioncount.\the\lemmacount\ :
      \enskip}{\sl #1}
      \medskip
    }
\def\lemma#1{\advance\lemmacount by 1
      \medskip
      {\bf\noindent Lemma \the\sectioncount.\the\lemmacount\ :
      \enskip}{\sl #1}
      \medskip
    }
\long\def\longcorollary#1{\advance\corollarycount by 1
      \medskip
      {\bf\noindent Corollary \the\sectioncount.\the\corollarycount\ :
      \enskip}{\sl #1}
      \medskip
    }
\def\corollary#1{\advance\corollarycount by 1
      \medskip
      {\bf\noindent Corollary \the\sectioncount.\the\corollarycount\ :
      \enskip}{\sl #1}
      \medskip
    }
\long\def\longalgorithm#1{\advance\algorithmcount by 1
      \medskip
      {\bf\noindent Algorithm \the\sectioncount.\the\algorithmcount\ :
      \enskip}{\sl #1}
      \medskip
    }
\def\algorithm#1{\advance\algorithmcount by 1
      \medskip
      {\bf\noindent Algorithm \the\sectioncount.\the\algorithmcount\ :
      \enskip}{\sl #1}
      \medskip
    }
\long\def\figure#1#2#3{\advance\figurecount by 1
                \vbox{
                      \vskip #1
                      \special{psfile="#2"}
                      \vskip .3true in
                      \centerline{Figure\ \the\figurecount.}
                     }
                \medskip
                \figurelabel{#3}
            }
\def\proof{{\bf\noindent Proof}:\enskip}
%\def\qed{\hfill \vrule width4pt height8pt depth0pt}
\def\qed{\hfill\vbox to 4pt{\hrule\hbox to 4pt
            {\vrule height 3pt depth 0pt \hfill \vrule}\vfill\hrule}
            \medskip
            }
\def\exerciselabel#1{\edef#1{\the\exerciseno}}
\def\theoremlabel#1{\edef#1{\the\sectioncount.\the\theoremcount}}
\def\lemmalabel#1{\edef#1{\the\sectioncount.\the\lemmacount}}
\def\corollarylabel#1{\edef#1{\the\sectioncount.\the\corollarycount}}
\def\algorithmlabel#1{\edef#1{\the\sectioncount.\the\algorithmcount}}
\def\figurelabel#1{\edef#1{\the\figurecount}}
\def\svs#1{{\sl S}_{#1}}
\def\dsvs#1{\dual{{\sl S}_{#1}}}
\def\dual#1{#1^*}
\def\comp#1{{\overline #1}}
\def\bibitem#1#2{
        \vbox{
          \smallskip\noindent \hangindent2\parindent \textindent{[#1]\ } #2}
        }
\def\Z{{\bf Z}}
\def\T{\top}
\def\true{\top}
\def\false{\bot}
\def\F{\bot}
\def\iff{\leftrightarrow}
\def\underline#1{{\bf #1}}
\def\notequal{\not=}
\def\plusminus{\pm}
\def\circle{\circ}
\def\N{{\rm\bf N}}
\def\Z{{\rm\bf Z}}
\def\R{{\rm\bf R}}
\def\Q{{\rm\bf Q}}
\def\C{{\rm\bf C}}
\def\page{\vfill\eject}
\def\title#1{\centerline{\bigrm #1}\bigskip}

\def\author#1{\centerline{\bf #1}\par}
\def\department#1{\centerline{#1}\par}
\def\university#1{\centerline{#1}\par}
\def\address#1{\centerline{#1}\par}

\def\by#1#2#3#4{\author{#1}\department{#2}\university{#3}\address{#4}
                \bigskip}
\def\({\left (}
\def\){\right )}
\def\[{\left [}
\def\]{\right ]}
\def\lf{\left\lfloor}
\def\rf{\right\rfloor}
\def\lc{\left\lceil}
\def\rc{\right\rceil}

\nopagenumbers
\magnification=\magstep2

\centerline{\bigrm RSA Encryption}
\medskip

To start the project you should read Section~1.5 of the text book 
carefully.  You are
given an encrypted message below and your job is to decode it.

Before trying to decode the message, you are to state a theorem which
generalizes Theorem~1.28 to include instead of just two primes $p$ and
$q$, any finite number of primes, say $p_1,p_2,\cdots ,p_j$.  You are
then to prove the generalized theorem.

Now, after you understand the RSA encryption technique, write a few
paragraphs explaning how it works.  You should be sure to include what
numbers are kept secret and what numbers are not.

Next, suppose that you intercept a message that Joe is
sending to Mary.  You know that to encode a message to Mary you use the
numbers $k=109283753$ and $n=2357879497866699967$. Based
on recent techniques to factor large numbers, you know that Mary's
numbers are small enough that it is feasible to break her code.  It is
your job to do just that with the use of Mathematica or Maple.
You also know that the way 
Mary converts a message into a number is to replace A with 01, B with
02, C with 03, and so on through Z with 26.  Furthermore, a space is
converted to 27, a period is converted to 28, a question mark is
converted to 29, and an exclamation mark is converted to 30.  So for
example the message "HI." becomes 080930. If you write this number as
80930, you need to put a zero in front since the number of digits must be even.
So, to send Mary a secret
message, you first replace the message with a number and then use the
scheme described in the book.  When the message is long, it is just
broken into smaller parts and each part is coded seperately.
Using Mathematica, Maple,
or your calculator, your job is to decode the following message 
consisting of the three numbers below.  After decoding, remember to concatenate the
three messages together to form one message.  Each of the three decoded
messages should have an even number of digits.
\medskip

246919062243423957

1673829235453550548

1794946576363047813

\medskip

If you are using Mathematica, then there are a few functions that help.
Use the help menu to determine how to use the functions {\bf
FactorInteger} and {\bf PowerMod}.  Note that in PowerMod, you can use
negative exponents.

\bye