4
$\begingroup$

Does anyone have the computational power to check whether or not

$F(m)^d \equiv m \pmod n$, where the values of the variables are found below.

According to Wolfram Alpha, I found the result of the computation $F(m) \equiv m^e \pmod n$, however I don't know how reliable Wolfram is with computations of this size and I am unable to compute $F(m)^d ≡ m \pmod n$ in Wolfram, since the numbers are too large.

m=112951412120151619251851615182016118201
n=145906768007583323230186939349070635292401872375357164399581871019873438799005358938369571402670149802121818086292467422828157022922076746906543401224889672472407926969987100581290103199317858753663710862357656510507883714297115637342788911463535102712032765166518411726859837988672111837205085526346618740053
d=89489425009274444368228545921773093919669586065884257445497854456487674839629818390934941973262879616797970608917283679875499331574161113854088813275488110588247193077582527278437906504015680623423550067240042466665654232383502922215493623289472138866445818789127946123407807725702626644091036502372545139713

What Wolfram says $F(m)$ is:
F(m)=22759056015886739716909089234835188351754889051525507970444538546831824365432006473081682583255424846673851966695239042380796121790409431507631093425
e=65537

$\endgroup$
  • 1
    $\begingroup$ Do you just want the answer or are you trying to find out how to perform such calculations. And why do you want to know? $\endgroup$ – David Richerby Nov 26 '14 at 22:31
12
$\begingroup$

Modular exponentiation is a well-known algorithm. It is routinely available in libraries and languages that can manipulate large integers, including Wolfram Alpha.

When making computations modulo a large number, one does not first make the whole computation in $\mathbb{N}$ and then take the remainder of the result, because for something like an exponentiation the intermediate result would be exceedingly large. Rather, the result is calculated with reductions modulo $n$ at each step. The basic idea for exponentiation is to write down the exponent $d$ in binary, and proceed one digit at a time, with the rules $$ \begin{align*} x^{2d} &= (x^d)^2 & \text{adding a binary digit \(0\) to the right of \(d\)} \\ x^{2d+1} &= (x^d)^2 \cdot x & \text{adding a binary digit \(1\) to the right of \(d\)} \\ \end{align*} $$ All computations are multiplications modulo $n$, it is never necessary to make computations involving larger numbers. There are variations on this algorithm, including iterating over the digits of $d$ from right to left instead of left to right. The number of multiplications is at most twice the number of digits of $d$.

There are techniques to perform a multiplication $a \cdot b \pmod n$ without calculating $a \cdot b$ which could be as large as $(n-1)^2$, the most popular being Montgomery reduction. Multiplication modulo $n$ can be done in time $O(\ell^2)$ where $\ell$ is the number of digits of $n$; it follows that exponentiation modulo $n$ can be done in time $O(\ell^3)$.

You can easily verify whether the value of $F(m)$ computed by Wolfram Alpha satisfies the equation $F(m)^d \equiv m \pmod n$ by running the modular exponentiation algorithm. (Easily with a computer, not by hand, for numbers of this size.)

We've seen how to compute $m^d \pmod n$ knowing $m$, $d$ and $n$. Solving the equation $F(m)^d = m \pmod n$ where $F(m)$ is the unknown is a different matter. Computing the $d$th root modulo $n$ is a hard problem in general, for which the only known methods are exponential in $\ell$ in the worst case. The problem is tractable (i.e. has polynomial complexity) when $n$ is prime, or more generally given a factorization of $n$.

It is apparent given the notations and the value of $e$ that these numbers are an example of an RSA key pair. An RSA key pair is generated starting with a number $n$ of the form $n = p \cdot q$ where $p$ and $q$ are (probable) primes and with a number $e$ satisfying certain conditions that I won't go into here; the knowledge of the factorization of $n$ makes it easy to compute a number $d$ such that $\forall m, (m^d)^e \equiv m \pmod n$ and $\forall m, (m^e)^d \equiv m \pmod n$. (If the factorization of $n$ was not known, then finding $d$ given $n$ and $e$ or equivalently finding $e$ given $n$ and $d$ would be a hard problem: it would be literally breaking the RSA cryptosystem.)

Given this supplementary knowledge, the $d$th root of $m$ modulo $n$ can be computed with a tractable operation: exponentiation. The solution $F(m)$ is $m^e \pmod n$.

The Python programming environment provides a convenient way of making calculations on large integers.

% python
Python 2.7.3 (default, Mar 13 2014, 11:03:55) 
[GCC 4.7.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> m=112951412120151619251851615182016118201
>>> n=145906768007583323230186939349070635292401872375357164399581871019873438799005358938369571402670149802121818086292467422828157022922076746906543401224889672472407926969987100581290103199317858753663710862357656510507883714297115637342788911463535102712032765166518411726859837988672111837205085526346618740053
>>> d=89489425009274444368228545921773093919669586065884257445497854456487674839629818390934941973262879616797970608917283679875499331574161113854088813275488110588247193077582527278437906504015680623423550067240042466665654232383502922215493623289472138866445818789127946123407807725702626644091036502372545139713
>>> e=65537
>>> pow(m,e,n)
141781201173392662619041096248902274075236734827860244551641082388116267289894721928886528279400665340976615948053755946789302972467196231829204061441862114262117040263042768989461016645192295451421289297123899909172989906731037919155114663997141846344255396618911673987467404521083471325973763420396488985050L
>>> pow(pow(m,e,n),d,n)
112951412120151619251851615182016118201L
>>> pow(pow(m,e,n),d,n) == m
True
$\endgroup$
0
$\begingroup$

I get a different number for $F(m)$. You can download sage and try for yourself.

sage: power_mod(112951412120151619251851615182016118201,65537,145906768007583323230186939349070635292401872375357164399581871019873438799005358938369571402670149802121818086292467422828157022922076746906543401224889672472407926969987100581290103199317858753663710862357656510507883714297115637342788911463535102712032765166518411726859837988672111837205085526346618740053) 141781201173392662619041096248902274075236734827860244551641082388116267289894721928886528279400665340976615948053755946789302972467196231829204061441862114262117040263042768989461016645192295451421289297123899909172989906731037919155114663997141846344255396618911673987467404521083471325973763420396488985050

With this value of $F(m)$, the other computation checks out:

sage: power_mod(141781201173392662619041096248902274075236734827860244551641082388116267289894721928886528279400665340976615948053755946789302972467196231829204061441862114262117040263042768989461016645192295451421289297123899909172989906731037919155114663997141846344255396618911673987467404521083471325973763420396488985050,89489425009274444368228545921773093919669586065884257445497854456487674839629818390934941973262879616797970608917283679875499331574161113854088813275488110588247193077582527278437906504015680623423550067240042466665654232383502922215493623289472138866445818789127946123407807725702626644091036502372545139713,145906768007583323230186939349070635292401872375357164399581871019873438799005358938369571402670149802121818086292467422828157022922076746906543401224889672472407926969987100581290103199317858753663710862357656510507883714297115637342788911463535102712032765166518411726859837988672111837205085526346618740053) 112951412120151619251851615182016118201

$\endgroup$
0
$\begingroup$

In Mathematica, you can use the PowerMod[] function to compute the modulo n power raise to the large power d. I agree with each of the two prior posts that the value of F = m^e mod n from Wolfram Alpha was incorrect.

In[30]:= F = PowerMod[m, e, n]

Out[30]= 1417812011733926626190410962489022740752367348278602445516410\
8238811626728989472192888652827940066534097661594805375594678930297246\
7196231829204061441862114262117040263042768989461016645192295451421289\
2971238999091729899067310379191551146639971418463442553966189116739874\
67404521083471325973763420396488985050


In[31]:= PowerMod[F, d, n]
Out[31]= 112951412120151619251851615182016118201

In[32]:= PowerMod[F, d, n] - m
Out[32]= 0
$\endgroup$
  • 1
    $\begingroup$ Welcome! Just to let you know, this isn't the sort of answer we're usually looking for on CS Stack Exchange: we much prefer answers that explain the principles, rather than just writing a program to solve the problem in the question. I'm not going to downvote, since IMO the question itself is borderline off-topic and there's already a similar answer from a high-rep user so it's understandable that a new user would post something like this. Thanks for contributing! $\endgroup$ – David Richerby Oct 13 '15 at 7:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.