**Problem 1) ** Let's start with a small example to check things
out. Use the computer to make sure you understand what's going on that
way, even though this one could also be done by hand.
Suppose 113 is the publically known prime *p* and you are
playing Bob's role having privately chosen *e*_{B}=5. Alice chooses
a message *x* to transmit, and you hear 43 from Alice. By
calculating
43^{5} *mod* 113 you transmit 76 to Alice. Alice
fires back with 108. Now

- 1.
- Figure out your decoding exponent
*d*_{B}by solving . - 2.
- Do the final step in the decoding procedure to figure out what message Alice sent you.
- 3.
- You wouldn't ordinarily ever learn this, but in fact
Alice's private prime
*e*_{A}was 17 with*d*_{A}=33. Check that Alice computed*d*_{A}properly, and also check the correctness of the other messages you received from Alice.

**Problem 2) ** Now let's try a real message exchange. We'll all use
as public prime *p* the smallest prime bigger than a trillion, namely
10^{12}+39. Find a partner and agree who will play Alice and who
Bob first. Each of you needs to work out your encoding (e.g. *e*_{A}
for Alice) and decoding powers (*d*_{A}). Follow the sample Maple worksheet
on what commands to use. Then ``Alice'' should encode an
at most 6 letter word as an at most 12 digit number - using say
*a*=01, ..., *z*=26. Now using numbers written on index cards,
follow the algorithm to successfully transmit the message from Alice to Bob.
Then using the same choice of private primes, reverse the roles of
Alice and Bob to transmit a message the other way.

**Problem 3) ** You may have noticed before that
2^{20}=1,048,576
and 2^{10}=1024. Suppose you (or a computer) wanted to calculate, say,

Without reduction mod 2,000,003, this number would be more than 2,000,000 digits long ! Using Maple as a numerical aid, but only for the operations or

**Problem 4) ** There are some very efficient probabilistic tests
for whether or not a number is prime. For most composite numbers n,
looking for discrepancies in
works
well. Should this ever for
fail to be
,
then you know *n* is composite. Use this method
to show that each of the following is composite: 33, 1001, 1000001.
Get a feeling for how often the base *a* produces a *witness* to the
nonprimality of each of these. (The probabilistic version of this test
for primality
would try
for a modest number of bases *a*
and conclude *n* was prime if no proof of it being composite emerged.)

**Problem 5) ** There's only one composite number *n*
smaller than 100 so that
.
What
is it? (Such a number is called a 3-pseudoprime.)

**Problem 6) ** But there are some numbers where the above
probabilistic test works poorly - these are called Carmichael
numbers. Try the above test on the first Carmichael number 561.
Are there any values of 0 < *a* < *n* for which
?
There's another Carmichael number between 1000 and
1200. Can you find it?