(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 6sided 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.

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.

What if its only one person. It is too easy to bias things.
But Brother Edwin proposed the following in modern notation.

Pick a 4digit number x.

Compute y_{1}=x^{2},

y_{1} will be 7 or 8 digits. Remove the two leftmost digits
and one or two rightmost digits to obtain a 4digit number z_{1}.

Repeat this process four times to obtain z=z_{4}.

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 4digit 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 randomlooking sequences of numbers.
His idea was to take a 4digit number x
_{1}, square it, and take the
middle 4 digits, repeat some number of times (say 4) to obtain x
_{2}
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.

Posted By GASARCH to
Computational Complexity at 1/26/2010 10:33:00 AM