I need to define a family H of universal functions $\{0,1, ..., p^k−1\} →\{0,1, ..., p^2−1\}$.

Now based on a similar example I was thinking of something like:

Given some $a= (a1, a2, ..., ak)∈\{0, ..., p−1\}k$, define $h_a(x)=(a_1x_1+a_2x_2+...+a_kx_k)\ mod\ p^2$ for $x \in \{0,1, ..., pk−1\}$ as we can write x as a sum of digits that represent it in base p. Meaning $x=(x_1,...,x_k)$ where $x_i∈\{0, ..., p−1\}$ and $p$ is some prime number.

Is it a universal family? Because I use $mod\ p^2$ which isn't a prime number.

  • $\begingroup$ The way to know it is universal is to prove it. Do you have a proof? Have you tried to prove it? Please check your question, it looks like it did not get type-set properly in the definition of $a$. $\endgroup$ – D.W. May 6 at 18:59
  • $\begingroup$ Hint: $p^2$ is not a prime number, so working modulo $p^2$ is not a field; but $GF(p^2)$ is a field. See en.wikipedia.org/wiki/Finite_field#Explicit_construction. $\endgroup$ – D.W. May 6 at 18:59

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.