Results 1 to 4 of 4

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

  1. #1
    Newbie
    Joined
    Jul 2011
    Posts
    2

    Injective function f: Z_p x Z_p -> Z_{q}

    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.
    Last edited by alfrodo; July 25th 2011 at 06:19 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Tinyboss's Avatar
    Joined
    Jul 2008
    Posts
    433

    Re: Injective function f: Z_p x Z_p -> Z_{q}

    You won't find a homomorphic map like that, since by the first isomorphism theorem, the image of f will be isomorphic to Z_p\times Z_p, which is not cyclic, but will on the other hand be a subgroup of Z_q, which must be cyclic (subgroups of cyclic groups are cyclic). So are you just looking for any old injection? If so, why not (a,b)\mapsto a+bp?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2011
    Posts
    2

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

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member ModusPonens's Avatar
    Joined
    Aug 2010
    Posts
    125
    Thanks
    14

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

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Injective Function
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: June 3rd 2010, 04:27 AM
  2. Injective function
    Posted in the Algebra Forum
    Replies: 2
    Last Post: November 14th 2009, 03:03 PM
  3. Injective Function
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: December 1st 2008, 12:52 PM
  4. injective function
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 20th 2008, 01:00 AM
  5. Show that a function is injective
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: November 17th 2008, 12:19 PM

Search Tags


/mathhelpforum @mathhelpforum