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 $k$ is being used.

In[1]:= k = khide;

Now, shuffle the disguised cards (their numbers are raised to the $k\text{th power mod }p$ 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 $k$ 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 $(p-1)/2\text{ power mod }p$, 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 $\text{mod }p$.