Thread: Injective function f: Z_p x Z_p -> Z_{p^2}

I would like to find an injective function f: Z_p x Z_p -> Z_{q}, i.e., a function from the cartesian product of the group of integers modulo a prime p to the integers modulo another prime q such that q > (p-1)^2.

The problem can just be solved by creating a table that maps each value (a,b) \in Z_p x Z_p to a different c \in Z_{q}, and from there deriving the algebraic expression of the function. But I would need a polynomial function with few now-zero coefficients. I.e., the degree of the polynomial can be large, but the amount of non-zero coefficients should be logarithmic in the degree. E.g., an injective function like this one (where n can be large):

f(x,y) = a_n x^n y^n + a_4 x^4 y^4 + a_1 x y + _0 mod q

PS: my orininal problem was to design an injective function f: Z_p x Z_p -> Z_{p}, but this is impossible since the cardinality of Z_p x Z_p is bigger than that of Z_p.

You won't find a homomorphic map like that, since by the first isomorphism theorem, the image of will be isomorphic to , which is not cyclic, but will on the other hand be a subgroup of , which must be cyclic (subgroups of cyclic groups are cyclic). So are you just looking for any old injection? If so, why not ?

Thank you for your reply.

I am not looking for a homomorphic map. I just need an injective polynomial.

Your reply allowed me to correct the formulation of my problem. I cannot use because, although it is an injection $Z_p x Z_p -> Z_{q}$, I need the polynomial to be in injective in $Z_q x Z_q -> Z_q$. The reason is that, although I only need to evaluate the polynomial in Z_p x Z_p, the polynomial is evaluated in Z_q, and thus an attacker can find another number bigger than p and smaller than q such that the result could be the same as the result given by another number smaller than p. (This is for an application in cryptography).

I have found out that the polynomial f(x,y)=(x+y-1)(x+y-2)+y is an injection N x N -> N, where N represents the natural numbers.
ScienceDirect - Journal of Number Theory : Polynomial indexing of integer lattice-points I. General concepts and quadratic polynomials*1
So it is suitable.

I would be interested on more examples of polynomial injections N x N -> N, and also
multivariate injective polynomials N x ... x N -> N.

I think your problem has a problem. If q>(p-1)^2, it can be less than p^2 (Bertrand-Chebychev's theorem), making an injection impossible.