0
$\begingroup$

Let $N$ be an even integer. Consider the affine cipher on the space of plaintext messages $\mathcal M=\mathbb Z/N\mathbb Z$ with encryption function $e(m)=am$ where $a\;\epsilon\; \mathbb Z/N\mathbb Z$ and $a\neq1\pmod{N}$. Assume $a$ is invertible modulo $N$.

I know that $0$ is going to be a fixed message as $e(0)\equiv a(0)\equiv 0 \pmod{N}$. Also I know that the other fixed message is going to be of the form $$ e(m_1)\equiv am_1\equiv m_1\pmod{N}$$ $$ m_1\equiv a^{-1}m_1 \pmod{N}$$ but I am not sure how to find this without assuming it exists first. I tried to solve the same equation by: $$ am_1-m_1\equiv m_1(a-1)\equiv 0 \pmod{N}$$ but this is also using the same assumption, right?

$\endgroup$
  • $\begingroup$ You should use the hypothesis that $N$ is even. In that case, is $a$ even or odd? How about $a-1$? $\endgroup$ – FredH Feb 25 at 18:46
  • $\begingroup$ So then $a$ has to be odd because it is invertible.. so $a-1$ is even $\endgroup$ – joseph Feb 25 at 18:47
  • $\begingroup$ I did think of going this route but I couldn't figure out how that would eventually help me get my same input without assuming it already exists $\endgroup$ – joseph Feb 25 at 18:48
1
$\begingroup$

Write $N=2M$. Since $a$ is invertible mod $N$, you have $\gcd(a,N)=1$. Hence, $a$ cannot be even since $N$ is even. Thus $a$ is odd and so $a=1+2k$ for some $k$. Then $$ e(M)=aM=(1+2k)M=M + 2kM = M + kN = M \bmod N. $$ But clearly $M$ isn't the class of $0$ so this is your other fixed point.

$\endgroup$
  • $\begingroup$ why did you start by writing $N=2M$? I know N must be even but why does it have to be two times $m$? Or I guess how did you know this ahead of time? $\endgroup$ – joseph Feb 25 at 19:00
  • $\begingroup$ That's what an even number looks like. I used this to find out that $M$ was going to work. $\endgroup$ – Randall Feb 25 at 19:02
  • $\begingroup$ IOW, I showed that $N/2$ will always be fixed. So is $0$, so QED $\endgroup$ – Randall Feb 25 at 19:03
  • $\begingroup$ Yeah I know that an even number is given by $N=ex$ for some $x:\ \epsilon \mathbb Z$ I'm just wondering how you knew to write it as $a=M$? Did you just find that by playing with actual numbers ahead of time and then going back and using that from the beginning or was there some deeper intuition used? $\endgroup$ – joseph Feb 25 at 19:05
  • $\begingroup$ How does it matter? Write $N=2\beta$ and then prove that $\beta$ is a fixed message. In short, yes, I just played with it. I didn't call it "$M$" for "message" because I knew that was going to work ahead of time. $\endgroup$ – Randall Feb 25 at 19:05

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.