1

I have an RSA example to solve. I got my decryption key and now I need to calculate the modulo $d^e \pmod n$. Here is the example

$$ 1007^{10} \mod 3599. $$

What I am trying is $$ 1007^3 \times 3 = 3063442029 + 1007^1 = 3063443036. $$

Then I am trying to get the mod by $3063443036/3599$ but that does not give me the answer I get $851192.8413$ while the modulo should be $441$.

I don't think I am doing the calculations correctly in this part $$ 1007^3 \times 3 = 3063442029 + 1007^1 = 3063443036. $$

Mee Seong Im
  • 3,190
  • 1
  • 15
  • 22
AutoTester213
  • 113
  • 1
    Can you explain why you were doing this calculation: $1007^3 * 3 = 3063442029 + 1007^1 = 3063443036$? – Toby Mak Aug 26 '17 at 23:51
  • 1007^10 wont render in my calculator so i tried to break it down, whats the altenrative? – AutoTester213 Aug 26 '17 at 23:55
  • You can represent it as a product of squares, as in: $(1007^2)^3 * 1007^2$. Remember that since $1007^2 \equiv 2730 \pmod {3599}$, you can instead calculate $3599^3$ rather than $(1007^2)^3$. – Toby Mak Aug 26 '17 at 23:57
  • @WojtekT maybe try modular exponentiation through Euler's theorem or Fermat's little theorem ? just a thought of possible ways to do it. –  Aug 26 '17 at 23:58

1 Answers1

2

This is one of the simplest ways to do it:

We can represent $1007^{10}$ as a product of $1007^8 * 1007^2$, or $(1007^2)^3 * 1007^2$.

Since $1007^2 \equiv -869 \pmod {3599}$, you can use $-869$ instead of $1007^2$ to calculate $(-869)^3$, which is equivalent to $-447$. Since we have already calculated $1007^2$ ($-869$), multiply $-447*-869$ and compute the result modulo $3599$.

If you really want a faster result than this, go to Wolfram Alpha.

Toby Mak
  • 16,827
  • Thanks for the anwser but im still confused where are you getting the -896 from? – AutoTester213 Aug 27 '17 at 00:03
  • Do you know what modular arithmetic is? Basically speaking, it is the remainder when you divide by some number. $1007^2 \equiv 2730 \pmod {3599}$, but since subtracting by some multiple of $3599$ will still give the same remainder, so what I did was to do $2730 - 3599*1 = -869$. – Toby Mak Aug 27 '17 at 00:05
  • @WojtekT equivalent representatives. –  Aug 27 '17 at 00:06
  • Kind, of. I need to know how to calculate it it would be 1007^2/3599? I havent done this in ages, and cant find any examples – AutoTester213 Aug 27 '17 at 00:06
  • no that would be a quotient. –  Aug 27 '17 at 00:07
  • By calculator you can calculate $1007^2/3599$, then subtract the integer part, and then multiply by $3599$. – Toby Mak Aug 27 '17 at 00:08
  • Oh god, Im such a doneky, Thank you i know what to do know! :) – AutoTester213 Aug 27 '17 at 00:13