0
$\begingroup$

Hi guys so I'm investigating Affine ciphers and I need to understand a field of mathematics I'm not familiar with, which is modular arithmetic. The formula for encrypting a letter xx using the affine cipher is:

$y=(ax+b)$ mod $26$

And apparently the decryption formula is

$x=a^{−1}(y−b)$ mod $26$

Where $a^{−1}$ is the multiplicative inverse of $a$ mod $26$. Firstly I have no idea how they derived this formula, but I think I have a general idea. I'm pretty sure they subtracted b from both sides and then divided both sides by a, but what to do about the mod26? Also what the heck does multiplicative inverse even mean? Like I know that it must be an integer, so how can that be possible? Thank you so much.

$\endgroup$
  • $\begingroup$ You really just need to learn modular arithmetic, either via webpages or a book on, say, number theory (like Rosen). While it would probably be easier in an actual course or in-person, it's not the hugest of endeavors. $\endgroup$ – pjs36 Nov 13 '16 at 4:56
  • $\begingroup$ Do you have any sources that directly address this issue of modular inverses? Like I can't really find any sources. It would be extremely helpful. Thanks. $\endgroup$ – ConfusedMathStudent Nov 13 '16 at 5:10
  • $\begingroup$ Any textbook on introductory Number Theory will tell you all about modular inverses. But have you tried just typing "modular arithmetic" or "modular inverse" into the internet, to see what comes back at you? $\endgroup$ – Gerry Myerson Nov 13 '16 at 5:45
  • $\begingroup$ Yes I have, but I still don't quite understand why the euclidean algorithm works. Everything I've came across so far just says to follow it blindly. I need to be able to understand exactly the theories behind it and the underlying concepts. $\endgroup$ – ConfusedMathStudent Nov 13 '16 at 6:04
  • $\begingroup$ If you have a question about how the Euclidean algorithm works, then you should ask a question about how the Euclidean algorithm works. The Euclidean algorithm isn't even mentioned in your question – how is anyone supposed to know that that's what's giving you trouble? $\endgroup$ – Gerry Myerson Nov 13 '16 at 22:53
1
$\begingroup$

As per the comments, the question seems to be about the Euclidean algorithm.

Given integers $a,m$, the Euclidean algorithm finds the number $\gcd(a,m)$, which we'll call $d$ (if you want to understand why the Euclidean algorithm finds $d$, pick up any intro Number Theory textbook).

The extended Euclidean algorithm finds integers $x,y$ such that $ax+my=d$ (again, details in any textbook).

If $\gcd(a,m)=1$, this says the algorithm finds $x,y$ with $ax+my=1$. As a congruence modulo $m$, this is $ax\equiv1\pmod m$. So, $x$ is the multiplicatvie inverse of $a$ when arithmetic is done modulo $m$.

$\endgroup$

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.