Efficient way to solve $31^6 \mod 189$ without using any external devices.

Question

Assuming basic knowledge of modulus arithmetic, is there a way, a trick or formulas that allow you to solve modulus question with very large numbers without using calculator? For example,

$$76^7 \mod 187=32$$ $$7^{23} \mod 143=2$$

This question ties into RSA Encryption where I'm trying to figure out how to solve these questions. So if I have $31^6 \mod 189$, I can simply use Wolfram Alpha but how can I work out that $31^6 \mod 189$?

Answer 1

$31^2=961$ and $5\times 189=945$ so that $31^6\equiv 16^3$ and if you know your powers of $2$ this is efficiently sorted.

Answer 2

Go in small steps. For instance first compute $$76^2 \mod 187$$ by hand, giving 166. Now, $166= -21\mod 187$. Also, $76^3=(-21)\cdot 76 = 87 \mod 187$. So you have

$$(76^2)\cdot(76^2)\cdot(76^3) = (-21)\cdot(-21)\cdot(87)=67\cdot87=32\mod 187.$$

You can do the other one in a similar fashion.

Answer 3

There is a shortcut for any calculation of two digit number in power of 2. For instance you need to count 442 (forty four in power of 2), you do like this:

1. Split this two digit number(44) -> 4 4

2. Then you rise two digits(separately) in a power of two and in the middle you will put double product of the first digit to the second ->

   ---

   4²_ 2*4*4 _4²

3. Then you've got the following : 16_32_16
4. So now you need to derive the answer from that, the answer is not that number 163216 . Actually what you've got from step 3 is , 3 digits which make up your answer ,and you have to put it appropriate slots . 16 32 16 ->_ _ _ -> we need to put first value in the first slot as our value consist of two digit value , we put only 6 there and 1 we keep in mind _ _ 6 (1->in mind) then put second value in the second slot , again 32 is two digit value , so do the same operation , put there 2 , keep 3 in mind , and main part you have to sum up the previous numbers in mind to the next hop _ (1+2) 6(3-in mind), then put third value in third place and add the number (3) you have in mind (6+3)36 (1 in mind), so as you can see you are left with one more number ,so the last number in mind you put in front of .

Here is the result: 1936
Now you can easily rise two digits number in power of two. This will give you great benefit in speed and calculation as well.
76²*76²*76²*76

Answer 4

Chinese remainder theorem int tandem with Eulers theorem will reduce is as far as possible. As to whether the calculations are easy or not is another issue.

So $31^6 \mod 189$. $189 = 7*3^3$ so by chinese remainder theorem we can solve this by solving $31^6 \mod 7$ and $31^6 \mod 27$.

So $7$ is prime and $31$ is not a multiple of $7$ we know $31^{7-1}\equiv 1 \mod 7$ so ... that's that. And $\phi(27) = 3^2*2 = 18$ so $31^6 \equiv .... \mod 37$. Well, it's a cube root of one but ... $31^6 \equiv 4^6 \equiv (3+1)^6 \equiv {6 \choose 2}3^2 + 6*3 + 1 \equiv \frac {6*5}2*3^2 + 18 + 1\equiv 19\mod 27$ ... or $4^6 \equiv 64^2 \equiv 10^2 \equiv 100 \equiv 19 \mod 27$.

So $31^6 \equiv 1 + 7k \equiv 19 + 27j \mod 189$. By CRT there is one solution.

So solve $1 + 7k = 19 + 27j$

$27 = 4*7 - 1$

$1 = 4*7 - 27$.

$1 + 7k = 19 + 27j$

$7k - 27j = 18 = 21 - 3 = 3*7 - 3(4*7 - 27) = -9*7 +3*27$.

So if $k = -9$ and $j = -3$ we get $1-7*9 = -62$ and $19 - 3*27 =-62$

And so $31^6 \equiv -62 \equiv 127 \mod 189$