# count number of i such that ( (a*i+b) mod p) mod k == l

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

This problem is related with the simple hash function $$h(i) = ((ai+b)\mod p) \mod k$$

It seems that no related topics are discussed.

• (1) I hope that you know that cstheory.stackexchange.com is a place for research-level questions. (2) What have you tried? – Tsuyoshi Ito Sep 26 '12 at 15:33
• Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the FAQ for more information. – Kaveh Sep 29 '12 at 20:53