1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Modular arithmetic problem

  1. Jul 4, 2012 #1
    1. The problem statement, all variables and given/known data

    Hi everyone! I have a homework question given below:

    One scheme of pseudorandom number generator is the linear congruential generator where we pick some modulus m, constant a and b and a seed x0, then generate sequence x1, x2, x3, ... according to the equation:

    x(t+1) = mod (ax(t) + b, m)

    given that we know m to be 2^31 -1 (a prime number) and we also know the values of x0, x1, x2, x3 and x4, describe how efficiently you can predict x5 up to x9

    2. Relevant equations

    x(t+1) = mod (ax(t) + b, m)

    x(t+1) = ax(t) + b (mod m)

    3. The attempt at a solution

    for starter, i plug in the values of x0, x1 and x2 into the equation to form 2 equation:
    x1 = ax0 + b (mod m)
    x2 = ax1 + b (mod m)

    substracting the equations above we get:
    (x1 - x2) = a(x0 - x1) mod m

    therefore a mod m = (x1 - x2)/(x0 - x1)
    after that simply plug in the value of a into equation 1 and we get
    b mod m = x1 - (x1 - x2)x0/(x0 - x1)
    then since we know the value of a and b we can simply calculate x5 to x9.

    My question is whether the method that I'm using is correct, since by using the above method means that given value of m, x3 and x4 are not used at all
    Last edited: Jul 4, 2012
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted