How hard is it to learn a linear modular function? Let $k$ be a fixed number.
Consider the following task $Q$: 


  We are given a sequence of numbers $(x_0,x_1,\cdots,x_k)$. We know they satisfy $x_{k+1}=f(x_k)$, and $f(x)=(ax+b \mod p) \mod m$ where $a,b,m,p \in [2^n]$ are some unknown values.
  The task is to find $f$.


I have a couple of questions about this problem:


How hard is this problem? 
If we choose $a,b,p,m$ randomly but "wisely" will $f$ be a pseudorandom number generator secure against TC0 or AC0 circuits?
What is the smallest value of $k$ where $Q$ can be solved?
What is the fastest known algorithm for $Q$?
I assume you want an efficient algorithm, e.g., one whose running time is polynomial in $n$.  (If you don't care about running time, then heuristically about $4n/\lg m$ samples should suffice to uniquely determine $a,b,m,p$, and you can use exhaustive search over all possible $2^{4n}$ parameter choices to find the correct one.  Of course, the running time of this method is exponential in $n$, so I assume it is not what you are looking for.)

In the case where $p=m$, this generator is known as a linear congruential generator.  It is known to be weak.  See my answer to Cracking a linear congruential generator (on IT Security.Stack Exchange) for an efficient algorithm that breaks this pseudorandom generator.

To summarize the  security of the generator (when $p=m$): A constant number of samples is enough to break the generator.  The algorithm requires only simple arithmetic and requires only a constant number of additions and multiplications, followed by a gcd operation.  I don't know whether this generator going to be pseudorandom for any particular complexity class, like TC0 or AC0; perhaps others will have insights on that.

Note that if you are picky about requiring a cryptanalysis algorithm to succeed with probability 1, and run in polynomial time without any randomness, then you won't like my algorithm.  My algorithm runs in polynomial time, and succeeds in recovering $f$ on an overwhelming majority of inputs; as a consequence, it succeeds in distinguishing the output of this pseudorandom generator from a true-random stream with advantage close to 1.  In the cryptographic world, this constitutes a "break" of the security of the generator.  However, if you wanted a learning algorithm that succeeds (in recovering $f$) on all problem instances, and has a fixed running time, my algorithm isn't it.  (Then again, from an engineering perspective, if you want something that is guaranteed to succeed on all problem instances, you won't find it, since any real-life implementation always has some small chance of producing an incorrect answer, e.g., due to a cosmic-ray bit flip.  My algorithm infers $f$ correctly for all but an exponentially small fraction of inputs. You can choose parameters so the probability of error due to unlucky choice of inputs is smaller than the probability of error due to a cosmic ray causing a bit flip error. So from an engineering perspective, it's essentially as good as deterministic, for all practical purposes.  But it's possible it might not be what you are looking for, if you care more about complexity classes than about whether the generator is usefully secure in an engineering sense.)

In the general case, I don't know what the most efficient cryptanalysis algorithm will be, but I would be pretty surprised if this is secure.  Linear congruential generators are notorious in the cryptographic community for being insecure.  However, you might enjoy the following paper, which while it does not address the specific question you asked, is somehow related:


Inferring sequences produced by a linear congruential generator missing low-order bits.  J. Boyar.  J. ACM 36(1), pp.129--141, Jan 1989.


Also, since $m$ is not a divisor of $p$, note that there will be a statistical bias of the outputs of this generator.  In particular, values in the range $0 .. b-1$ will be slightly more likely than values in the range $b .. p-1$, where $b= p \bmod m$.  The magnitude of this bias depends (roughly) upon the size of $p/m$; the larger $p/m$ is, the greater the bias.  More precisely, the statistical variation distance between pseudorandom and random, due to this effect, is $\delta = 2b(m-b)/mp$, for a single sample.  Therefore, I would expect that $O(1/\delta^2)$ samples should suffice to distinguish the pseudorandom stream from a truly random stream, simply by exploiting this bias.  This attack does not take into account all of the available structure in the output of the generator, so I would expect that better attacks are probably possible.