Solving Upper Congruences: Step-by-Step Guide for x^{n}+a=mod(b)

[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.

 

[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.

 

[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?..

 

[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.

 

[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...

 

[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.

 

[HallsofIvy]

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?..

What would be an "approximation" to an integer?

 

[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...

 

[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).