Assume I work with $f: \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}$. $$f(x, y) = (x \oplus y) \mod p$$ where $x, y$ are n-bits 0-1 strings and $x, y \in Z_p$ and $\oplus$ performs bitwise xor.
I would like to find a y such that $g^{a} \oplus y = 1$.

Is there a way to express $y$ related to $g^a$?

These are my thoughts:
$1$ here stands for $0..01$ (n-1 zeros), so in order to have after xor, $n-1$ zeros, $y$ must have the same $n-1$ bits with $g^a$ and the opposite lsb from $g^a$.
If $g^a$ is odd (lsb = 1) then $y=g^{a-1}$ and if $g^a$ is even $y=g^{a+1}$ Is there something else I can do ?



You must log in to answer this question.

Browse other questions tagged .