1
$\begingroup$

$$e(x) = (ax + b)$$ $$d(y) = a^{-1}(y-b)$$ I need to prove that $$e(x)=d(y)$$ iff $$(a^2)=1$$ and $$b(a+1)=0,$$ so I tried working with $d(ex)$ to show they can be equivalent:

$$ax + b = a^{-1}(ax + b - b).$$ Next step will be $$ax^2 + ba = ax$$ and that's where I'm stuck I saw a solution doing $$ ax+ b = a-1(x - b) $$ but I don't understand why this is valid. Shouldn't I replace the $y$ in $$d(y) = a^{-1}(y-b)$$ with the body of $$e(x)$$ after all $$x = d(e(x))$$ right?

And another question - how can I find all involutory keys in $\mathbb N$?

$\endgroup$
1
  • 1
    $\begingroup$ In $\mathbb{N}$ the cipher is only invertible if $a \in \{-1,1\}$. This limits the number of possible ciphers. $\endgroup$
    – Henno Brandsma
    Mar 17, 2019 at 16:12

1 Answer 1

Reset to default
2
$\begingroup$

If we have that the encryption equals the decryption function, we have that for each $x$ in the ring we're working on ($\mathbb{Z}_{26}$ or some other.) we have

$$e(e(x))=x$$ or equivalently

$$\forall x: a(ax+b)+b = a^2x+ab+b= x$$

which implies (check that two affine functions are equal everywhere iff they're two coefficients are) that

$$a^2 =1 \text{ and } a(1+b)=0$$

Now the argument will depend somewhat on the ring to determine the squares of $1$(there could be just $2$, $1$ and $-1$ or more); modulo $26$ or a prime, there are indeed just these two. And then $b=-1$ is "forced" by the last equation, as $a$ cannot be a zero-divisor. So in the most common cases we'll have two solutions.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .