1. Square and Multiply

I was wondering if somebody could help me with a problem I am having. I am trying to compute:

9983^2052765 mod 36581 and 13461^2052765 mod 36581

I am pretty sure it can be accomplished with the square and multiply method but I'm not to sure as to how to accomplish this. Could anyone point me in the right direction or get me started off?

2. $\displaystyle \varphi(36581) = 36192$ and $\displaystyle 2052765 = 56\cdot36192+26013$.

Thus $\displaystyle \displaystyle 9983^{2052765} \equiv 9983^{26013} \bmod{36581}$. Now express $\displaystyle 26013$ in binary..

3. Thanks for your response. To be honest I have no idea what you did. What do you mean by express in binary, as in 2 to a power?

4. Originally Posted by chiph588@
$\displaystyle \varphi(36581) = 36192$ and $\displaystyle 2052765 = 56\cdot36192+26013$.

Thus $\displaystyle \displaystyle 9983^{2052765} \equiv 9983^{26013} \bmod{36581}$. Now express $\displaystyle 26013$ in binary..
$\displaystyle 26013 = 110010110011101_2$ i.e. $\displaystyle 26013 = 2^{14}+2^{13}+2^{10}+2^8+2^7+2^4+2^3+2^2+2^0$

Let $\displaystyle a = 9983$, now $\displaystyle \displaystyle a^{26013} = a^{2^{14}}\cdot a^{2^{13}}\cdot a^{2^{10}}\cdot a^{2^8}\cdot a^{2^7}\cdot a^{2^4}\cdot a^{2^3}\cdot a^{2^2}\cdot a^{2^0}$.

If we compute $\displaystyle \displaystyle a^{2^n}$ starting from $\displaystyle 0$ to $\displaystyle 14$, it will be less messy to compute the solution.

$\displaystyle 9983^1 \equiv 9983 \bmod{36581}$

$\displaystyle 9983^2 \equiv 13645 \bmod{36581}$

$\displaystyle 9983^4 \equiv 13645^2 \equiv 25316 \bmod{36581}$

$\displaystyle 9983^8 \equiv 25316^2 \equiv 736 \bmod{36581}$

$\displaystyle 9983^{16} \equiv 736^2 \equiv 33454 \bmod{36581}$

$\displaystyle \vdots$

This seems rather tedious. If you are familiar with the notion of multiplicative order, this can be a bit easier. Are you?

If so, use the fact that $\displaystyle 9983^{1508} \equiv 1 \bmod{36581}$ and $\displaystyle 2052765 = 1361 \cdot 1508+377$. Then you'll only have to do the above for $\displaystyle 377$ instead of $\displaystyle 26013!$

5. Okay, so this is what I did.

377 = 101111001

377^256 % 36581 = 25398
377^64 % 36581 = 13118
377^32 % 36581 = 20272
377^16 % 36581 = 24932
377^8 % 36581 = 26097
377^1 % 36581 = 377

multiplied those all together and got 1656734045363396234936064.
Now do i mod that number by 36581 for the answer?

6. Originally Posted by tr6699
Okay, so this is what I did.

377 = 101111001

377^256 % 36581 = 25398
377^64 % 36581 = 13118
377^32 % 36581 = 20272
377^16 % 36581 = 24932
377^8 % 36581 = 26097
377^1 % 36581 = 377

multiplied those all together and got 1656734045363396234936064.
Now do i mod that number by 36581 for the answer?
You need to consider $\displaystyle \displaystyle 9983^{2^n}$, not $\displaystyle \displaystyle 377^{2^n}$

Otherwise, yes you've done everything correctly.