Some Things to Try and to Think About:

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⁵ mod 113 you transmit 76 to Alice. Alice fires back with 108. Now

1.

Figure out your decoding exponent d_B by solving $5 y = 1 \ (mod \ 112)$.

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¹²+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²⁰=1,048,576 and 2¹⁰=1024. Suppose you (or a computer) wanted to calculate, say,

$$101 ^{2^{20}+2^{10}+1} \ (mod \ 2,000,003)$$

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 $u:= x \cdot y \ mod \ p$ or u:= x² mod p, calculate the value of the above expression. Do you see why this idea would enable you to reasonably calculate 101 to any 7 digit power mod 2,000,003?

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 $a^{n-1} \ (mod \ n)$ works well. Should this ever for $1 \leq a \leq n-1$ fail to be $1 \ (mod \ n)$, 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 $a^{n-1} \ (mod \ n)$ 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 $3^{n-1}=1 \ (mod \ (n-1))$. 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 $a^{n-1} \neq 1 \ (mod \ 561)$? There's another Carmichael number between 1000 and 1200. Can you find it?