Suppose to have a function for numbers expressed in 8-bit $\in [0,2^8-1]$ defined as: $$f(x)=x||x||x||x$$ where $|f(x)|$ is exactly 32 bits.

e.g., suppose x=2 (00000010) so $f(x)=2+2^9+2^{17}+2^{25}=33686018$ (00000010000000100000001000000010)

Given N and x I'd like to find y,z,w s.t.

$$f(x)*f(y) \space mod \space N= f(z)*f(w) \space mod \space N$$

What is a good way to proceed?

OBVIOUS, if you write $f(x)=(1+2^8+2^{16}+2^{24})\times x=K\times x$. Then $f(x)\times f(y)=K^2\times x \times y$. Then $\forall y$, choosing $z \in (\mathbb{Z}/n.\mathbb{Z})^{*}$ allows to dermine the unique $w \in \mathbb{Z}/n.\mathbb{Z}$ satisfying this relation in the multiplicative group.
• Use the table of the multiplicative group. From $K^2\times x \times y\;=\; K^2\times z \times w$ what could you do in a set endowed with a group structure? – Robert NACIRI Mar 25 '15 at 14:34
• sorry I misclick and delete the original question on the comment that was "how to choose z and w?". So I have just to bring any w and z s.t. $wz=xy$ or is there some other criteria that I am missing? – abc Mar 25 '15 at 14:39
• Thanks, but when you write $\mathbb{Z}/n.\mathbb{Z}$ who is $n$ there? – abc Mar 25 '15 at 15:05