# How to work out modular arithmetic quickly for cryptography [duplicate]

This question already has an answer here:

I am not so good at Mathematics so please kindly forgive my stupidity.

Basically, I am learning modular arithmetic for cryptography and so I am struggling in understanding how to do big modular arithmetic calculation without a calculator.

So for example, how would I do this question: 6^56 mod 19?

I get that you need to convert the power 56 into binary - so that would be 0111000. So like 2^32 + 2^16 + 2^8.

I then understand you have to do like:

6^8 mod 19 then 6^16 mod 19 and 6^32 mod 19.

I've been told I can use the chinese remainder theorem - but I want to know how to do this all.

Any help would be absolutely great! I like this stuff but I have been struggling a bit.

## marked as duplicate by Misha Lavrov, Lord Shark the Unknown, Leucippus, José Carlos Santos, NamasteJan 24 at 13:55

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• Please don't use phrases like 'kindly forgive my stupidity', no question is stupid and adding that is simply redundant and doesn't put you in a very good light. That said, Welcome to Mathematics Stack Exchange! – Naman Kumar Jan 23 at 15:15
• CRT can be used when the modulus has more than one prime factor.. But your modulus $19$ is prime, so CRT won't help. – Bill Dubuque Jan 23 at 15:17

## 1 Answer

What you mention you have to perform is the fast exponentiation algorithm. However, usually one performs reductions that rest on Fermat's little theorem (or Euler's theorem if the modulus is composite). Here, it is particularly efficient:

As $$6$$ and the modulus are coprime, we know the $$6^{18}\equiv 1\pmod{19}$$, so that $$6^{56}\equiv 6^{56\bmod 18}=6^2\pmod{19},$$ therefore $$\;6^{56}\equiv 36\equiv-2\:$$ (or $$17)\pmod{19}$$.

• I'm so lost now :S. Why did you or how do you know that 6^18 = 1 (mod 19)?? – Benardoe Jackson Jan 23 at 15:41
• That what lil' Fermat asserts. – Bernard Jan 23 at 15:42
• Where did the 18 come from – Benardoe Jackson Jan 23 at 15:44
• The general formula is that if $p$ is prime and $a$ is not divisible by $p$, then $\;a^{p-1}\equiv 1\mod p$. – Bernard Jan 23 at 15:46
• So which one is a and which one is p? – Benardoe Jackson Jan 23 at 15:51