Question

How to determine the number of $i$'s, as fast as possible, such that $1\le i \le L$ and $((a*i+b)\mod p) \mod k = l$, where $1\lt a,b\lt p-1, p$ is a prime number, and $l \lt k \lt L \lt p$.

This problem seems to be too complex, let me begin with a simple one:

given two different primes $p_1, p_2$, integer $L$ and another integer $l< p_1$. Is there any way to compute the number of solutions of $1\leq i\leq L$ s.t., $$(p_2i)\mod p_1 = l$$

we can assume $L=c*2^d$ for some integers $c,d$, because we can first use dyadic intervals

Answer 1

Until a better idea strikes me, why not give this one a go?

Reduce the problem to $i + B \pmod p$ by the following. Find $f$ so that $fa\equiv1 \pmod p$. then transform the set $ai+b$ to $i +fb \pmod p$. You will also have to transform the set of numbers in $[0,p)$ of the form $tk+l$ to $tfk+fl \pmod p$, but if this set is nice you might be able to find quickly which parts lie in the transformed interval.

Gerhard "I Saw This On ArXiv" Paseman, 2012.09.26