<p>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$.</p>

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

<p>It seems that no related topics are discussed.</p>

CC BY-SA 3.0
2012-09-26T15:33:28.973Z
(1) I hope that you know that cstheory.stackexchange.com is a place for research-level questions.  (2) What have you tried?
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-29T20:53:14.630Z
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
<ds.algorithms><nt.number-theory><hash-function><algebra>
count number of i such that ( (a*i+b) mod p) mod k == l
redplum
# count number of i such that ( (a*i+b) mod p) mod k == l

(Asked by: username_0 on 2012-09-26)

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.

**Tags:** ds.algorithms, nt.number-theory, hash-function, algebra

> **Comments:**
> **username_1**: (1) I hope that you know that cstheory.stackexchange.com is a place for research-level questions.  (2) What have you tried?  
> **username_2**: 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.  

---

## 0 answers

