0
$\begingroup$

Let $N$ be a positive integer. Consider the affine cipher on the space of plaintext messages $\mathcal M=\mathbb Z/N\mathbb Z$ with encryption function $e(m)=am+b$ where $a,b\;\epsilon\; \mathbb Z/N\mathbb Z$ and $a\neq1\pmod{N}$. Also assume $N$ is prime. $$$$ I've been playing around for this for quite some time at this point and haven't gotten too far. I have found that for $m=-ba^{-1}$ we get $e(-ba^{-1})\equiv a(-ba^{-1})+b\equiv (aa^{-1})-b+b\equiv -b+b\equiv 0\pmod{N}$. I don't think that's very useful, however, I don't really know how else to attack this problem. If someone could just point me in the right direction I'd much appreciate it.

$\endgroup$
1
$\begingroup$

Suppose that $f: \mathbb{Z}_p \to \mathbb{Z}_p$ by $f(x) = ax+b$ is your affine map, where $a \neq 0,1$. (You should exclude $a =0$ or you don't have a bijection. If you for some reason allow $a=0$ the statement is still correct since $x=b$ will be the unique fixed point.) You are asking about fixed points $x$ from the message space $\mathbb{Z}_p$ so that $f(x)=x$. Well, just write it out: $$ f(x) = ax + b=x. $$ Now do the algebra: $$ ax-x=-b \Rightarrow (a-1)x=-b. $$ Since you've assumed $a \neq 1$, we know $a-1 \neq 0$, so we can invert $a-1$ since we are working mod $p$ and all non-zero elements are invertble: $$ x=-(a-1)^{-1}b. $$ Hence you can check that (a) this $x$ is indeed fixed by $f$ and (b) it's the only fixed point (use the same idea above).

$\endgroup$
  • 1
    $\begingroup$ Wow that is a lot simpler than I expected. Thank you so much for the help $\endgroup$ – joseph Feb 23 at 23:53
  • $\begingroup$ To be clear, the bulk of my answer shows the thought process for how you get there: it isn't a valid proof that a fixed point exists, because I started out by assuming so. But, this does show you what the answer ought to be, so now you just have to start over and check it. But that's just plug-and-chug. $\endgroup$ – Randall Feb 23 at 23:55
  • $\begingroup$ To go about showing that this is the only such fixed message.. would you just use some argument that starts by assuming another such exists and then showing at the end that it must actually be equal to the one we found therefore reaching a conclusion? $\endgroup$ – joseph Feb 24 at 22:10
  • $\begingroup$ Yep, you got it. $\endgroup$ – Randall Feb 24 at 22:48
  • $\begingroup$ Thank you so much! $\endgroup$ – joseph Feb 24 at 23:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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