0
$\begingroup$

I'm in high school and writing a paper on the mathematics behind RSA encryption. I now have come to the point where I have to solve: $50^{61} \pmod{77}$ Then, as on https://math.berkeley.edu/~kpmann/encryption.pdf page#5, I found the binary expansion: $61 = 32 + 16 + 8 + 4 + 1$

Using binary expansion of $61$: $50^{61} = 50^{32+16+8+4+1}$ Using basic exponent rule: $50^{61} = 50^{32} \times 50^{16} \times 50^8 \times 50^4 \times 50^1$

.. Now I don't know how to continue. In the link I sent, if you go to page 5, they continue but the explanation is a bit confusing to me (bearing in mind their example uses different numbers to mine:

"Now since we only care about the result ($\mod{943}$), we can calculate all the parts of the product ($\mod{943}$). By repeated squaring of $545$, we can get all the exponents that are powers of $2$."

How do I do my calculations then?

$\endgroup$
0

2 Answers 2

1
$\begingroup$

Repeated squaring: $$50^2=2500=32\cdot77+36,$$ so $$50^2\equiv36.\tag{1}$$ Squaring both sides of (1), $$50^4=(50^2)^2\equiv36^2=1296=16\cdot77+64,$$ so $$50^4\equiv64.\tag{2}$$ Squaring both sides of (2), $$50^8\equiv(50^4)^2\equiv(64)^2=4096=53\cdot77+15.\tag{3}$$ Squaring both sides of (3), $$50^{16}\equiv\cdots$$

$\endgroup$
3
  • $\begingroup$ Hey! I've just completed these. Now that I have all the values, what do I do next? 50^1 ≡ 50 50^2 ≡ 36 50^4 ≡ 64 50^8 ≡ 15 50^16 ≡ 71 50^32 ≡ 36 $\endgroup$
    – Antonia
    Mar 16, 2016 at 11:03
  • $\begingroup$ As you said in your question $$50^{61} = 50^{32} \times 50^{16} \times 50^8 \times 50^4 \times 50^1.$$ First compute $50^{48}=50^{32}\cdot50^{16},$ next $50^{56},$ etc. $\endgroup$
    – bof
    Mar 16, 2016 at 21:23
  • $\begingroup$ Oh! That makes a lot more sense. Thank you!!! $\endgroup$
    – Antonia
    Mar 17, 2016 at 8:20
0
$\begingroup$

As $77=7\cdot11$ where $(7,11)=1$

$50\equiv1\pmod7\implies50^n\equiv1$ for any integer $n$

$(50,11)=1\implies 50^{11-1}\equiv1\pmod{11}$ using Fermat's Little Theorem

and as $60\equiv0\pmod{10},50^{60}\equiv50^0\equiv1\pmod{11}$

So, $50^{60}-1$ is divisible by $7,11$ hence by lcm$(7,11)$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .