# Existence of a map $\phi:\mathbb{Z}_{N^2}^* \mapsto \mathbb{F}$

Is there a map between the group of $\mathbb{Z}_{N^2}^*$ where $N$ is a composite number , a product of two equal size secure prime numbers $p$ and $q$ and a finite field $\mathbb{F}$, such that for all $x \in \mathbb{Z}_{N^2}^*$ there is a polynomial representation of $x \in \mathbb{F}$ ?

-
If we assume finite fields defined over congruent classes of prime numbers then $|\mathbb{Z}_F|=F-1$ The order of $\mathbb{Z}_{N^2}^*$ is $N\phi(N)$. Maybe there is sth with the crt and the isomorphism $\phi: \mathbb{Z}_{N^2}^* \mapsto \mathbb{Z}_{p^2}^* \times \mathbb{Z}_{q^2}^*$ but $\mathbb{Z}_{p^2}^*$ and $\mathbb{Z}_{q^2}^*$ are not defined modulo a prime – curious Apr 16 '14 at 8:42
@fgrieu But from the isomorphism of the crt? – curious Apr 16 '14 at 9:22
If you want to define a mapping between one set and the other, it's easy; you can define a mapping to $GF(2^{256})$ using SHA256. However, presumably you also insist that the mapping also preserve the group operation; however any field has two operations defined on it; which field operation should the group operation be mapped to? In other words, should $\phi(ab) = \phi(a)+\phi(b)$ or $\phi(ab) = \phi(a)\phi(b)$? – poncho Apr 16 '14 at 11:42
@poncho. the multiplicative one: $\phi(ab)=\phi (a)\phi (b)$ – curious Apr 16 '14 at 12:01
@tylo: actually, because he wants the multiplicative operation to be preserved, the appropriate order is $x^a-1$. In any case, we can show that an injective map cannot exist; a surjective map (where surjective is defined to mean "we map to all elements of the field other than 0") does exist, however whether a nontrivial map exists in general is less clear. – poncho Apr 16 '14 at 13:30

So if you want a homomorphism from $\mathbb{Z}_{N^2}^*$ into the multiplicative group of a field, you have to adjust the number of elements in the field. With $p=2a+1$ and $q=2b+1$ (with $a,b$ prime), you have $$|\mathbb{Z}_{N^2}^*| = 4pqab$$ The multiplicative subgroup of a field $F_{x^y}$ with prime $x$ and exponent $y$ has $x^y-1$ elements. At this point you could choose a specific $N$, that the according cardinalities match ($4abpq=x^y-1$), but if you have to apply this to arbitrary $N$, it won't work this way. Then all you can do is try to find $x^y$, s.t. $(x^y-1)$ is a factor of $4abpq$. If you use e.g. $\mathbb{F}_p^*$ or $\mathbb{F}_q^*$, this will work. But I can't think of any other fields which have this property from these given values.
As an example for an homomorphism you can use $f(x) = x^{pq(q-1)}$ to get a subgroup of order $p-1$, which you might be able to find an isomorphism into the multiplicative group of $\mathbb{F}_p$.
Are you absolutely sure about that? Small number example: $p=3, q=5 \Rightarrow N^2=225, \phi(N^2)=120$. From the cardinality it would fit to the multiplicative group of $\mathbb{F}_{11^2}$, and both are cyclic groups wrt. their multiplication. And I think all finite cyclic groups are isomorphic to each other. – tylo Apr 16 '14 at 16:59
Actually, that's the problem: $\mathbb{Z}_{N^2}^*$ is not a cyclic group. – poncho Apr 16 '14 at 17:06