# Math question.

• May 5th 2009, 05:21 PM
DarkPrognosis
Math question.
Hello,

I hope someone can help me with this.

X=M^e mod N

from this how do we derive N if we know X, M, and e?

I am sure it is simple to do but my head is in a fog after numerous hours in all of this math. :)
• May 5th 2009, 09:04 PM
Gamma
Whoa, I have no idea what some of these letters are coming from? Are they all integers or what? e is usually reserved for the exponential x is usually for real numbers and m and n are usually for integers, but I am hoping you have just run out of good numbers to use and all of these are just arbitrary integers.

$\displaystyle a \equiv b$ mod n iff $\displaystyle n|(b-a)$
so if you know a,b,m all fixed integers.
you just need to choose n to be a divisor of $\displaystyle b^m-a$
Then you will get the desired congruence mod n
$\displaystyle a\equiv b^m$ (mod n)
• May 6th 2009, 04:34 AM
TheAbstractionist
Quote:

Originally Posted by DarkPrognosis
Hello,

I hope someone can help me with this.

X=M^e mod N

from this how do we derive N if we know X, M, and e?

I am sure it is simple to do but my head is in a fog after numerous hours in all of this math. :)

Hi DarkPrognosis.

Suppose $\displaystyle X\ne M^e.$ If you know $\displaystyle X,$ $\displaystyle M$ and $\displaystyle e,$ then $\displaystyle N$ must be a divisor of $\displaystyle X-M^e.$

For example, if $\displaystyle X=26,\ M=2,\ e=3,$ then $\displaystyle X-M^e=18$ so $\displaystyle N$ can be 1, 2, 3, 6, 9, 18. That is, 26 is congruent to 8 modulo 1, 2, 3, 6, 9 and 18.

Unfortunately if $\displaystyle X=M^e$ then $\displaystyle N$ can be any integer, and there is no way to find out what it is without further information.
• May 6th 2009, 10:02 AM
DarkPrognosis
oh brother.

All are integers but if there is no way to reverse the formula I guess it doesn't matter. :(

Thanks to everyone for helping with this.