jonab@sdcrdcf.UUCP (Jonathan Biggar) (01/10/84)
Given: A sequence of random numbers is produced by the following
algorithm:
1) A linear congruential random number generator is used
to produce pseudo-random numbers of the form:
r[i] = (a * r[i-1] + c) % m; /* c-syntax */
of period approx. equal to 2^30.
2) The final random number sequence is produced by
the output of the following function on the generated
random numbers:
y = (r/37) % n; /* c-syntax */
where r is the generated number, and n is fixed and n << m.
Questions:
1) Is it a reasonably difficult problem to determine the
initial seed to the random number generator given the
parameters of the generator (a, c, and m) and your choice
of a large sample of elements of the final random sequence
that are possibly but not necessarily in sequential order?
2) How hard is it to produce any initial seed to the random
number generator that will produce that sequence given a
large sample of elements of the final sequence that are
not of your choice?
Commentary on the questions:
1) The real problem is to attempt to predict other elements
of the final random number sequence.
2) The problem here is to be able to change elements
in the final sequence by changing the inital seed
while holding any given set of the elements in the
sequence as fixed.
Please reply by mail and I will summarize the results to the net.
--
Jon Biggar
{allegra,burdvax,cbosgd,hplabs,ihnp4,sdccsu3,trw-unix}!sdcrdcf!jonab