Public Key Decryption

Alan has sent you a text message, including only letters and blank spaces, encrypted by the following algorithm:

1. Each letter in the message is turned into its numerical order in the alphabet, with a blank space being set at 0, and then multiplied by 27 raised to the position of the letter in the message, counting from the right with the rightmost letter having position 0. For example, “I am” is turned into 9 x 27³ + 0 x 27² +1 x 27 +13 = 177,187.
2. The result from step 1 is raised to the power 3,038,795,305 and then divided by 2,853,926,939,827,803,391. The remainder of the division calculation becomes the encrypted message. For example, 177,187 is converted into 405,673,963,959,368,185 by performing these operations.

The encrypted message Alan sent you was 69,176,418,906,672,230. Can you decode this message? (Hint: It will almost certainly require some computer calculation. If you can do it by hand, then you are very talented. If you can do it in your head, then you are a superhero and deserve your own comic book!)

Design a New Casino Game

In this puzzle, you work at a casino owned by Sheldon. Sheldon presents you with a roulette-like machine that spins around and randomly stops at a number from 1 to n, where n is fixed, each number having equal probability. Sheldon asks you to design a new game where the probability of winning is p. Can you do this? If so, explain how. If not, explain why not.

Here is a simple algorithm that works for all values of p in the interval (0, 1):

1. Expand out p in base n representation. This can be done one digit at a time for any p, even if it is irrational or, worse yet, transcendental.
2. Use the gambling machine, one digit at a time “moving rightward from the decimal point,” to generate the base n expansion of another number in the interval (0, 1) in base n representation. For example, if the machine lands on a value k, then the digit can be taken as k-1.
3. At each step, if the digit randomly generated is:
4. The same as the corresponding digit of p, then continue to generate the next digit of both the original number p and the random number, respectively.
5. Greater than the corresponding digit of p, then stop and declare a loss.
6. Less than the corresponding digit of p, then stop and declare a win.

There is p probability of stopping at some point with a win and 1-p probability of stopping at some point with a loss. It is possible that the game could continue forever by generating the exact base n representation of p, but the probability of this is 0. In fact, the probability that the game will go on for more than a few digits is very low.

Solutions were also submitted by Patrick Allen, Xunchi Chen, Bob Conger, Ian Deters, Clive Keatinge, Robert W. Peterson, Brad Rosin and Edward “Ned” Tyrrell.