This question is related to :
https://crypto.stackexchange.com/questions/37351/encoding-an-element-in-r-rhr-way
that I asked couple of weeks ago. The difference is that I did not take the collision probability into account in that question.
Edit: A simpler version.
Assume $p'$ is a 40-bit value and $B=\{b_1,..,b_d\}$, where $b_i \in \mathbb{F}_{p'}$.
Question1: What is the probability that a random element of the field $\mathbb{F}_{p'}$ equals at least one of $B$'s element.
Application:
Assume we have a finite field $\mathbb{F}_p$, where $p$ is a 100-bit prime number.
assume we have a set of 32-bit elements $S=\{s_1,...,s_n\}$ defined over the field. We encode each element as $s'_1=s_1||h(s_1)$, where $h()$ is a (cryptographic) hash function and $|h(s_1)|=40$-bit.
So, for any arbitrary element, $r$, of the field we can check if it has the above structure as below:
1- $r=r_1||r_2$, if $|r_2|=40$-bit, then we proceed to the next step.
2- $h(r_1)\stackrel{?}=r_2$
We know that with some probability two elements can have the same hash value. So, the above question can be re-written as follows:
Question2: What is the probability that an arbitrary element of the field has the above structure?
===================
Answer to question 1 would suffice.