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



count number of i such that ( (p_2*i) mod p_2) == l
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


