1
$\begingroup$

i'm pretty noob with mathematica but i need to solve an equation:

$$c\equiv m^2\pmod n$$

I tried something like

Solve[621455041 == m^2, m, Modulus -> 74596505816855975484638389815392741477]

Is it right?

| improve this question | | | | |
$\endgroup$
  • $\begingroup$ Yes, that looks correct. $\endgroup$ – DumpsterDoofus Jan 10 '15 at 1:38
  • $\begingroup$ Voting to close, as this is a fairly simple operation and thus is unlikely to help future visitors (no offense intended). If there is something more complex that you would like to do, please edit the question accordingly and I'll remove the close-vote. $\endgroup$ – DumpsterDoofus Jan 10 '15 at 1:49
2
$\begingroup$
c = 621455041;

n = 74596505816855975484638389815392741477;

sol1 = Solve[c == m^2, m, Modulus -> n]

{{m -> 24929}, {m -> 52367465358866978466157125093802778}, {m ->
74544138351497108506172232690298938699}, {m ->
74596505816855975484638389815392716548}}

If you want to know if it is right, substitiute the solution back into the equation

And @@ (Mod[m^2, n] == c /. sol1)

True

Or, for a more general solution use Reduce

sol2 = Reduce[c == Mod[m^2, n], m, Integers]

C[1] \[Element] 
  Integers && (m == 24929 + 74596505816855975484638389815392741477 C[1] || 
   m == 52367465358866978466157125093802778 + 
     74596505816855975484638389815392741477 C[1] || 
   m == 74544138351497108506172232690298938699 + 
     74596505816855975484638389815392741477 C[1] || 
   m == 74596505816855975484638389815392716548 + 
     74596505816855975484638389815392741477 C[1])

For C[1] == 0 this reduces to sol1

sol1 == {sol2 /. C[1] -> 0 // ToRules}

True

| improve this answer | | | | |
$\endgroup$

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