2
$\begingroup$

I'm currently in a Discrete Mathematics class in college, and my professor is giving a quiz soon and told us what will be on it.

Problem is, I missed a day of class and I have no idea to figure out what he was saying when he gave us this problem:

Describe the sequence $X_{n+1} = (Ax_n + b) \mod p$

Is there a common name for this / what am I supposed to do here? I've done a couple of google searches but found nothing; I was hoping some of you might be able to clarify what this means.

Thank you in advance!

Edit: I think $p$ is meant to be interpreted as a prime number.

2 Answers 2

1

The person may have been discussing the Linear Congruential Generators. With suitable choice of parameters, these are a simple method to generate a pseudo-random sequence. Of course such a sequence is definitely not "random," since it is periodic. But if the period is extremely long, say of length $\approx 10^{100}$, the periodicity is not a practical drawback.

  • 0
    I think this is actually what he was talking about, thank you! I'm confused about how to actually use it, though. Do you think that, the way this question was posed, he may have meant for us to simply write out a period of the generated PRNG sequence? That's my thought, but I just want to make sure that there's no other way to "describe the sequence."2012-11-15
  • 1
    @BenjaminKovach: If the parameters $A$, $b$, and $p$ were *explicitly* given, with $p$ at least quite small, writing down a full period may have been intended. Otherwise, I really can't guess what the instructor was asking for.2012-11-15
  • 0
    Okay, thank you! I'll go ahead and assume that's what he was asking for, then.2012-11-15
4

I really don’t know what he’s looking for. About all that you can say without further information is that the sequence is periodic. If $A$ is a multiple of $p$, the sequence is constant: $x_n=b\bmod p$ for every $n$ except perhaps the initial value. If $A$ is not a multiple of $p$, the sequence is periodic with period $p$ and runs through the values $0,1,\dots,p-1$ in some order. (Here I’m assuming that $p$ is intended to be a prime.)

  • 0
    I'm guessing that `p` is supposed to be a prime number as well, if that matters. This might be sufficient too; I understand what you're saying and that makes sense. Thanks for your response!2012-11-15
  • 1
    @Benjamin: You’re welcome! I should have said that I was assuming in my response that $p$ was prime; I’ll add that now.2012-11-15