I'm reading a text book about cryptography. The text on RSA encryption uses modular arithmetic. When exercising myself with the materials, I struggled a bit with this.

As far as I understood, when my text book says that $100^3 \equiv 254 \mod 319$, I'm tempted to calculate $(100 * 100 * 100) \% 319$ which indeed yields 254. In this case, I'm using $%$ as in C and many other programming languages: as a 'remainder' operator.

Does this make any mathematical sense? Is this the correct way of performing modular arithmetic?

  • 1
    $\begingroup$ if % is what is done in the C language then yes, it is correct. There are many mathematical results for shortcuts for modular arithmetics where you don't have to remember or calculate the whole number $\endgroup$ – mathreadler Dec 23 '16 at 19:11
  • 2
    $\begingroup$ Be sure to understand the relationship between "mod" as a binary operator (remainder) vs. ternary congruence relation, e.g. see this answer and this one by Arturo Magidin. $\endgroup$ – Bill Dubuque Dec 23 '16 at 19:14
  • $\begingroup$ Yes! Another way to think about it is to think, is $(100^3 - 254)$ divisible by $319$? $\endgroup$ – Euler_Salter Dec 23 '16 at 19:27
  • $\begingroup$ @mathreadler That would be interesting, since my OS calculator had some troubles calculating $165^{107}$... $\endgroup$ – mthmulders Dec 23 '16 at 19:30
  • 2
    $\begingroup$ For methods of calculating $165^{107}\bmod n$ I recommend that you take a look at what is explained here as well as familiarize yourself with the square-and-multiply algorithm $\endgroup$ – Jyrki Lahtonen Dec 23 '16 at 19:43

Your Answer

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

Browse other questions tagged or ask your own question.