Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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}$ ?

share|improve this question
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$.

However, a bijective function (isomorphism) is quite unlikely to exist.

share|improve this answer
Actually, we know that a bijective function cannot exist (even if you omit the element 0 of the field). – poncho Apr 16 '14 at 14:51
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.