Can we define universal hash function from $U \rightarrow T$ when $T=\{0,1,2,..,m-1\}$ and $m=p^a$? (where $p$ is a prime and a is an integer)

I know that we can define universal hash funciton when $m=p$ and p is a prime in this way:

$h_{\alpha}(x)=\alpha \cdot x \space mod \space m$ but what about $m=p^a$?

a hash function is universal if $Prob(h(x)=i)=1/m \space$ for $i=0,1,...m-1$.

  • 1
    $\begingroup$ You can define $h_a(x)=ax\pmod m$ for any $m$ and $a$, as long as $a$ is relatively prime with $m$. $\endgroup$ – Thomas Andrews Dec 22 '14 at 3:30
  • $\begingroup$ Why did you change from uniform hash in your previous question to universal hash here? They appear the same. $\endgroup$ – Ross Millikan Dec 22 '14 at 3:35
  • $\begingroup$ yes,they are same. $\endgroup$ – abdolahS Dec 22 '14 at 3:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.