A peculiar feature of public key codes is that they allow users to "sign" their messages in a way that authenticates them. If I had a public key code given by (n,e) (and secret decoding exponent d), I would sign my messages with (MY NAME)^d (mod n). If I sent it to someone whose public key code was given by (n',e'), I would then encode it in the normal way and send it off. The recipient would decode it with the secret decoding exponent d', and would find my signature ("encoded" with my decoding exponent d). To verify that the message really came from me, the recipient would simply raise it to the power e (mod n) using MY public key code. Note that e decodes d just as d decodes e. If a sensible "signature" results, then it could only have come from me. Only I know the inverse of e mod n, which must have been used to prepare the signature.
Public key codes rely on the practical impossibility of factoring the number n, but history relates examples where the seemingly impossible was done. A famous case is that of the "Fermat primes," numbers of the form 2^(2^n)+1, specifically 2^1+1=3, 2^2+1=5, 2^4+1=17, 2^8+1=257, 2^16+1=65537, 2^32+1=4,294,967,297, ... Fermat remarked that all such numbers seem to be prime. He didn't actually know that they were (i.e., he had no proof). The largest one that he knew to be a prime was 65537, only the fifth one in the list. Nowadays a claim like this would be greeted with great skepticism, because there is no formula known which always produces a prime. But in Fermat's day it didn't look so unreasonable.
Euler showed that the sixth "Fermat prime" is actually not prime -- he found a factorization of this 10-digit number! Needless to say, it wasn't dumb luck. He very systematically narrowed the field of candidates for a prime p which could work. By the time he was ready to search through what was left, there were very few possibilities. Thus it didn't take him long to find a factor. That is what must worry the designers of public key codes -- perhaps there is some super-intelligent way to search for factors, a way which is unknown now, but which will be discovered in the future. Even elementary observations can shorten a search. For example, if a number n is not prime, then among its factors is a prime which is at most the square root of n. So the search for factors need not go up to n, only to its square root, which is generally much less. If you try to factor 10^4+1=10001, for example, you need only search for prime factors less than 100, and there aren't so many of those.
By the way, with computers, it has been possible to test even larger "Fermat primes," and NONE of them seems to be prime after 65537. So it is possible that most "Fermat primes" are not prime.
Here is how Euler did it. He thought generally about numbers of the form a^2+1, a^4+1, a^8+1, a^16+1, ... where a has only 2 as a factor. Then if an odd prime p divides a^4+1, for example, it means that a^4= -1 (mod p). But also a^(p-1)=1 (mod p), by Fermat's Little Theorem, since a is relatively prime to p. Euler used these two facts together to characterize p. First, since p must be odd, it is of the form p=2k+1 for some k. Now if p divides something of the form a^2+1, then a^2= -1 (mod p), but also a^(p-1)=a^(2k)=(-1)^k=1 (mod p) (FLT). Thus k must be even, i.e., k=2m, and p is of the form p=2(2m)+1=4m+1. This is a restriction on the odd primes p which could divide a number of the form a^2+1. Now consider what primes p could divide a number of the form a^4+1. Since such a number is also a number of the form a^2+1 (a^4 is a square), we know by the previous line that p must be of the form 4m+1. Also, since a^4+1=0 mod p, a^4= -1 (mod p), and by FLT, a^(p-1)=a^(4m)=(-1)^m=1 (mod p). Thus m must be even, i.e., m=2n, and p is actually of the form p=4(2n)+1=8n+1. This is a further restriction on p. This argument can be repeated indefinitely. The primes p which divide something of the form a^8+1 must have the form p=16k+1. The primes p which divide something of the form a^16+1 must have the form p=32k+1. The primes p which divide something of the form a^32+1 must have the form p=64k+1. Now this is exactly the case of the sixth "Fermat prime," 2^32+1. The argument says that if it has a prime factor, it can only be of the form 64k+1, and there aren't very many primes of this form. The first one is 193, corresponding to k=3. Euler tried out the few primes that are 64k+1. The fifth one, corresponding to k=10, namely p=641, divided evenly into 4,294,967,297! That proved the number wasn't prime. So, in a sense, he took only a few minutes to factor that number, using only his head.
Public key codes rely on multiplication in Zn*, where n=pq. This might give you second thoughts, because not all numbers less than n -- i.e., not all possible "messages" -- are actually in Zn*. Multiples of p and q are not relatively prime to n, and hence are not in Zn*. The decoding process relies on a decoding exponent d satisfying ed=1 (mod (p-1)(q-1)). By FLT this exponent decodes any message in Zn*, but what about those others?? Someone might argue that in practice p and q are so large (say 50 digits or so) that the chance of a message being a multiple of one of them is too small to worry about, but that seems rather sloppy. In fact, these peculiar messages get decoded without any problem! We haven't exactly said WHY -- i.e., it doesn't exactly follow from what we have said -- but the reason is not hard to discover. This seems like a good challenge problem -- you can try examples, and maybe even give a general argument.
Two possibilities here: take your pick (no need to do both!)
(1) Use the general arguments of Euler, above, either to factor 8^4+1=4097, or to show it is prime. Be sure to show how Euler's arguments guide what you do. It's not enough to do this without Euler.
(2) What numbers are cubes in Z7*, Z11*, Z13*, and Z17*? Is there a general rule for the behavior of cubes in Zp* (p a prime)? (Here "cube" means "third power." For example the cube of 2 is 8. The cube of 2 is 3 (mod 5). Thus 8 is a cube, and 3 is a cube in Z5*.)