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

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

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

[tex] x^{n}+a=mod(b) [/tex] n>0 and integer..

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

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

CRGreathouse

Science Advisor
Homework Helper
2,771
0
I really don't know what you're asking. I presume the question you've already solved is [tex]ax\equiv b\pmod c[/tex] but I'm not sure what your first is. Depending on what you mean, you might be able to use reciprocity.
 
Last edited:
108
0
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

Science Advisor
Homework Helper
9,392
3
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.
 
108
0
- I don't know why is the "congruence" [tex] x^{n}=amod(b) [/tex] for n>1 in fact it's nothing but a Monomial..you could calculate all the roots of [tex] x^{n}-a=0 [/tex] easily and from this find a solution... :rolleyes: :rolleyes:
 

matt grime

Science Advisor
Homework Helper
9,392
3
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

Science Advisor
41,626
821
lokofer said:
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?
 
108
0
-For example "Hallfosftivy"..a solution to the (general ) congruence:

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

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

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

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

matt grime

Science Advisor
Homework Helper
9,392
3
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).
 

The Physics Forums Way

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top