# Math Help - Square and Multiply

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. $\varphi(36581) = 36192$ and $2052765 = 56\cdot36192+26013$.

Thus $\displaystyle 9983^{2052765} \equiv 9983^{26013} \bmod{36581}$. Now express $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@
$\varphi(36581) = 36192$ and $2052765 = 56\cdot36192+26013$.

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

Let $a = 9983$, now $\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 a^{2^n}$ starting from $0$ to $14$, it will be less messy to compute the solution.

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

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

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

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

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

$\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 $9983^{1508} \equiv 1 \bmod{36581}$ and $2052765 = 1361 \cdot 1508+377$. Then you'll only have to do the above for $377$ instead of $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 9983^{2^n}$, not $\displaystyle 377^{2^n}$

Otherwise, yes you've done everything correctly.