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
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,
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?