Take the 2-minute tour ×
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.

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 at 8:42
    
@fgrieu But from the isomorphism of the crt? –  curious Apr 16 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 at 11:42
    
@poncho. the multiplicative one: $\phi(ab)=\phi (a)\phi (b)$ –  curious Apr 16 at 12:01
1  
@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 at 13:30

1 Answer 1

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 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 at 16:59
1  
Actually, that's the problem: $\mathbb{Z}_{N^2}^*$ is not a cyclic group. –  poncho Apr 16 at 17:06

Your Answer

 
discard

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.