Here is a game you can play. It is essentially the simplified version of poker over the telephone from Section 18.2. There are five cards: ten, jack, queen, king, ace. They are shuffled and disguised by raising their numbers to a random exponent mod the prime 24691313099. You are supposed to guess which one is the ace. To start, pick a random exponent. We use the semicolon after khide so that we cannot cheat and see what value of is being used.
In[1]:= k = khide;
Now, shuffle the disguised cards (their numbers are raised to the and then randomly permuted):
In[2]:= shuffle
Out[2]= {14001090567, 16098641856, 23340023892, 20919427041, 7768690848}
These are the five cards (yours will differ from these because the and the random shuffle will be different). None looks like the ace; that’s because their numbers have been raised to powers mod the prime. Make a guess anyway. Let’s see if you’re correct.
In[3]:= reveal[%]
Out[3]= {ten, ace, queen, jack, king}
Let’s play again:
In[4]:= k = khide;
In[5]:= shuffle
Out[5]= {13015921305, 14788966861, 23855418969, 22566749952, 8361552666}
Make your guess (note that the numbers are different because a different random exponent was used). Were you lucky?
In[6]:= reveal[%]
Out[6]= {ten, queen, ace, king, jack}
Perhaps you need some help. Let’s play one more time:
In[7]:= k = khide;
In[8]:= shuffle
Out[8]= {13471751030, 20108480083, 8636729758, 14735216549, 11884022059}
We now ask for advice:
In[9]:= advise[%]
Out[9]= 3
We are advised that the third card is the ace. Let’s see (note that %% is used to refer to the next to last output):
In[10]:= reveal[%%]
Out[10]= {jack, ten, ace, queen, king}
How does this work? Read the part on “How to Cheat” in Section 18.2. Note that if we raise the numbers for the cards to the , we get
In[11]:= PowerMod[{200514, 10010311, 1721050514, 11091407, 10305}, (24691313099 - 1)/ 2, 24691313099]
Out[11]= {1, 1, 1, 1, 24691313098}
Therefore, only the ace is a quadratic nonresidue .