next up previous
Next: About this document ... Up: A Message Transfer Method Previous: A Message Transfer Method

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 eB=5. Alice chooses a message x to transmit, and you hear 43 from Alice. By calculating 435 mod 113 you transmit 76 to Alice. Alice fires back with 108. Now

Figure out your decoding exponent dB by solving $ 5 y = 1 \ (mod \ 112)$.
Do the final step in the decoding procedure to figure out what message Alice sent you.
You wouldn't ordinarily ever learn this, but in fact Alice's private prime eA was 17 with dA=33. Check that Alice computed dA 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 1012+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. eA for Alice) and decoding powers (dA). 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 220=1,048,576 and 210=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:= x2 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?

next up previous
Next: About this document ... Up: A Message Transfer Method Previous: A Message Transfer Method