Help with example RSA problem

Question

While learning about RSA, I found this example problem. The answer is supposed to be "a 4-digit number that is a pattern of digits." I have computed it to be 16657 twice.

OK, now to see if you understand the RSA decryption algorithm, suppose you are person A, and you have chosen as your two primes $p = 97$ and $q = 173$, and you have chosen $e = 5$. Thus you told B that $N = 16781$ (which is just $pq$) and you told him that $e = 5$.

He encodes a message (a number) for you and tells you that the encoding is 5347. Can you figure out the original message? Hint--well, not really a hint, but a check of your final answer: it is a four-digit number that is a pattern of digits.

I have failed to decode this to a 4-digit number. What am I doing wrong?

p = 97
q = 173
N = 16781
dp = 16512 = (p-1)(q-1)
e = 5
d = ?
C = 5347
M = ?

I computed d = 6605 since that seems to be the smallest value of d possible for:

ed = 1(mod (p-1)(q-1))
5d = 1(mod 96 * 172)
5d = 1(mod 16512)
# I need a multiplier for 16512 that when added to 1 yields a number that
# ends in a 5 or a 0 so it will evenly divide by e=5
# 1 + 2 times dp will yield a number that ends in a 5
d = 6605

Now I need to compute M = C^d(mod N):

M = C^d(mod 16781)

    5347^6605(mod 16781)

6605 = 4096 + 2048 + 256 + 128 + 64 + 8 + 4 + 1

5347^1   (mod 16781)    = 5347
5347^2   (mod 16781)    = 12366   (not included in final math)
5347^4   (mod 16781)    = 9484
5347^8   (mod 16781)    = 96
5347^64  (mod 16781)    = 389
5347^128 (mod 16781)    = 292
5347^256 (mod 16781)    = 1359
5347^1024(mod 16781)    = 3105
5347^2048(mod 16781)    = 8731
5347^4096(mod 16781)    = 11059

5347^6605(mod 16781)    = 16657

I've also computed the same result in Excel by reproducing the same table above one power at a time for 6605 rows.

Update: It turns out to have been a mistake. The original author corrected the problem, but not before the error was copied across the internet.

Answer 1

You don't appear to have done anything wrong; you can double check your result by computing:

$16657^5 \bmod 16781$

and find that it is indeed 5347; that is, 16657 is the number that, when encoded with the public key, results in the value you were given.

I suspect that moral of this story is that random examples on the internet might be worth just as much as you pay for them.