The First pseudorandom generator- probably

(The following was told to be by Ilan Newman at Dagstuhl 2009. His source was the book The Broken Dice and other mathematical tales of chance.)

What was the first pseudorandom number generator? Who did it? While these type of questions are hard to really answer, the book The Broken Dice by Ivar Ekeland gives a very good candidate.

Brother Edvin (a monk), sometime between 1240 and 1250 AD, was preparing a case for the sainthood of King Olaf Haraldsson, who had been the King of Norway. There was a well documented story (that could still be false) that King Olaf and the King of Sweden needed to determine which country owned the Island the Hising. They agreed to determine this by chance. They were using normal 6-sided dice. The King of Sweden rolled two dice and got a 12. Then King Olaf rolled and got a 12 AND one of the dice broke (hence the name of the book) and he got an additional 1 for a 13. Some attributed this event to divine intervention, which strengthened his case for sainthood.

Brother Edvin got interested in the general question of how you can generate a random number so that nobody could manipulate it. He may have phrased it as a way to know what was divine intervention as opposed to human intervention.

1. There are two players and they want to pick a random number between 0 and 5. They want the process to be such that neither player can bias the outcome. Each picks a natural number in secret. They are revealed, added, and then the remainder upon division by 6 is taken. Brother Edvin noted that the players really only need pick numbers between 0 and 5; however, he thought it best not to tell the players this since they will think they have more choice then they do.
2. What if its only one person. It is too easy to bias things. But Brother Edwin proposed the following in modern notation.
   1. Pick a 4-digit number x.
   2. Compute y₁=x²,
   3. y₁ will be 7 or 8 digits. Remove the two leftmost digits and one or two rightmost digits to obtain a 4-digit number z₁.
   4. Repeat this process four times to obtain z=z₄.
   5. Divide z by 6 and take the remainder.

The hope is that it is very hard for a human to bias the results by picking a particular original 4-digit number. Brother Edvin did note that some choices for x make the final choice choice obvious and hence not random (e.g., 1001). Brother Edvin proposed some solution: make sure the initial x has no 0's and no repeated digits. He also suggesting taking more initial digits or more times that you iterate the process. But he does realize that this might not work.

The method was rediscovered by von Neumann in a different context. He wanted to generate long random-looking sequences of numbers. His idea was to take a 4-digit number x₁, square it, and take the middle 4 digits, repeat some number of times (say 4) to obtain x₂ then repeat to get more and more numbers. It was abandoned since the periods weren't that large. People used linear congruential generators instead. (Are they still used?)

However, Brother Edvin does deserve LOTS OF credit. Given the math known in his day it is impressive that he asked these questions and got some reasonable answers.