# Solving x^{n}+a=mod(b)

1. Sep 3, 2006

### lokofer

If a,b,n are integers..how could you solve:

$$x^{n}+a=mod(b)$$ n>0 and integer..

If possible please put an "step by step" example..i have managed to solve the linear congruence

$$ax=bmod(c)$$ but i don't know how to solve "upper" congruences..thanks.

2. Sep 3, 2006

### CRGreathouse

I really don't know what you're asking. I presume the question you've already solved is $$ax\equiv b\pmod c$$ but I'm not sure what your first is. Depending on what you mean, you might be able to use reciprocity.

Last edited: Sep 3, 2006
3. Sep 4, 2006

### lokofer

i know how to solve for n=1 then i would like to know how to solve the special case y proposed....

- By the way...are not there "approximate" or numerical method to calculate the set of the solutions?..

4. Sep 4, 2006

### matt grime

If you can solve for any x other than 1 (or 2) easily then you've just proven RSA easy to break. Come on, Jose, think for a second before posting a question: taking roots mod c is hard, and that's the whole point of RSA.

5. Sep 15, 2006

### lokofer

- I don't know why is the "congruence" $$x^{n}=amod(b)$$ for n>1 in fact it's nothing but a Monomial..you could calculate all the roots of $$x^{n}-a=0$$ easily and from this find a solution...

6. Sep 16, 2006

### matt grime

Then why don't you 'just do it'? You really ought to get straight in your mind what a function is, what an algorithm to find a value of said function is, and what you consider to be a reasonable cost for carrying out the algorithm, and then state what that is.

7. Sep 16, 2006

### HallsofIvy

Staff Emeritus
What would be an "approximation" to an integer?

8. Sep 16, 2006

### lokofer

-For example "Hallfosftivy"..a solution to the (general ) congruence:

$$f(x)=amod(x)$$ (for example) is the solution to the "equation" (non-linear) in the form:

$$[\frac{f(x)-a}{x}]-\frac{f(x)-a}{x}=0$$ or if we define the function:

$$<x>=x-[x]$$ where "[x] " is the floor function then:

$$<\frac{f(x)-a}{x}>=0$$ so from this you could calculate all the "roots" (integers) and solution to the initial congruence...

9. Sep 16, 2006

### matt grime

Go on then. Do it. Show that it's better than a simple exhastive search through phi(c) options, (or c-1 if you don't know the factorization of c).