Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
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." –  Benjamin Kovach Nov 15 '12 at 16:24
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. –  André Nicolas Nov 15 '12 at 16:33
    
Okay, thank you! I'll go ahead and assume that's what he was asking for, then. –  Benjamin Kovach Nov 15 '12 at 16:34

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.)

share|improve this answer
    
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! –  Benjamin Kovach Nov 15 '12 at 16:08
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. –  Brian M. Scott Nov 15 '12 at 16:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.