Decoding RSA Problem: How to Crack Public Exponent and Modulo N

[Galileo]

I just read up a bit on RSA and tried to do a problem I have in my algebra book. The goal is to crack/decode the message c=m^e mod N, obtained with public exponent e and modulo N.
I just puzzled away and tried a few things. I`m not a number theorist so my method may not be the most efficient, but it should work. However, my final answer doesn't match. When I compute m^e mod N it's not the same as I started with. Hopefully someone can spot the error.

Given is:

$$N = 15241578753238836751577503665157706318489955952973821$$

$$e = 31$$

$$c = m^e = 861510404336695227251078663863347293625350352438927$$

I just let Maple grind for a few minutes and it found the prime factorisation of N = pq:
$$p=1234567890123456789012345678901231$$

$$q=12345678901234567891$$
From which I find the totient:

$$\phi(N)=(p-1)(q-1)=15241578753238836750342935775034237183798709039504700$$

Then I found 'd' such that $$ed \equiv 1 \bmod \phi(N)$$:

$$d = 11799931937991357484136466406478119110037710224132671$$

So now that I've found the private key d, I should just compute c^d and I should get m. However, Maple finds
$$c^d=861510404336695227251078663863347293625350352438927^{11799931937991357484136466406478119110037710224132671} \bmod N$$ a bit hard to swallow (well, me too). So I thought about breaking d up into smaller pieces that Maple can handle and compute the parts manually. It goes fine as long as the exponent is not much larger than in the order of 50000.

I did: $$d=(11)(17)^2(20116367)(99732718879652629)(1850127955377590503746343)$$
Then raised c to the power 11, than to the power 17^2, all mod N ofcourse.
What I was left with is then:

$$m=10629575215834074693129969195052025048670006092854912^{(1850127955377590503746343)(99732718879652629)(20116367)}=x^{abc}$$
with

$$x=10629575215834074693129969195052025048670006092854912$$

$$a = 20116367 = 1+(2)(1193)(8431)$$

$$b = 99732718879652629 = 13+(8)(3)(59)(73)(21863)(2143)(20593)$$

$$c = 1850127955377590503746343 = 31+(8)(3)(1223)(3313)(19025787016433837)$$

So I've broken up a,b and c into smaller pieces again and repeated the scheme. The answer is below, I've introduced some symbols for clarity. Everything is assumed to be taken modulo N.

$$y = x^a = 1610044581396706062621617218007597816610136362872871$$

$$z = y^b = 8295213403069483304303211306255358878287773906357859$$

$$m = z^c = (z^13)(2882470640844826906680249819845717295058993606788553)^(19025787016433837)$$

For the last step I hacked up 19025787016433837 into 10+(49)(349)(25447)(21937)(1993) and putting it all together gave me:
m = 1632801515822720824329177013717453486198256157145735

But when I calculate m^e (mod N) I do not get the original c. So something is wrong, but I've doublechecked the whole thing a few times and I can't find a mistake. It may be something elementary, but I'd appreciate any help.

Ciao

 

[Galileo]

Doh!

I did z^13 instead of z^31. Silly me. After a few hours of checking I didn't notice that. And if I didn't make that Latex error I probably still missed it.

So with z^31 it does give the right answer:
m = 14210805021005040520182103202305120205071805160514

If you group the digits in pairs and let A=01, B=02, etc, it says
NUHEBJEDETRUCTWELBEGREPEN, which is (apart from spacebars and a spelling error) dutch for 'You've understood the trick by now'.
I hoped it would contain some ancient wisdom, but oh well.