Log in

View Full Version : (x ^ y) mod z = w


Foreigner
July 9th, 2004, 17:13
(x ^ y) mod z = w

I have x, y and w; is it possible to find z? Is there a tool that can help me?

Thanks in advance.

naides
July 13th, 2004, 11:55
Quote:
[Originally Posted by Foreigner](x ^ y) mod z = w

I have x, y and w; is it possible to find z? Is there a tool that can help me?

Thanks in advance.


I am unsure of your symbol convention, but I assume that ^ means "to the power of".
If that is the case, and you know both x and y, you know the value of (x^y) = n (Some integer number).

The Equation is rewritten

n mod z = w, where you know n and w and want to find z.


By the definition of modulus

n \ z = q (q is quotient) where \ is integer division

and

n mod z = w the modulus operation, your equation


then

n = z * q + w

z * q = n - w (1)

Any couple of integers z and q which satisfy the equation (1)

will provide one valid value for z

If you factorize out (n-w), both of which you know, you will find all possible values of z that satisfy your equation (factorization tools are plenty on the net).

There is a range of possible values of z that correctly solve the equation. If you might have more information on z you could narrow down its possible value.

Hope this makes sense

gabri3l
July 13th, 2004, 16:19
It has been awhile since I used the mod function; but w is the remainder of (x^y) / z
As Naides said; there are many possible answers for z.

hint: if z greater than half of (x^y) then w will equal ((x^y) - z)

However in math it means something a little different. It is usually written as x = (
n ^ p) mod z

Let us replace (n^p) with y
resulting with x = y mod z

Which reads as "x is equivalent to y, modulo z". What this means is that x and y have the same remainder when divided by m.

You may find this page useful as well
hxxp://mathforum.org/library/drmath/view/51619.html#assoc