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

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

• 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

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
• 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