Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Sep 3, 2006 #1
    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.
  2. jcsd
  3. Sep 3, 2006 #2


    User Avatar
    Science Advisor
    Homework Helper

    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: Sep 3, 2006
  4. Sep 4, 2006 #3
    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?..
  5. Sep 4, 2006 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
  6. Sep 15, 2006 #5
    - 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:
  7. Sep 16, 2006 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
  8. Sep 16, 2006 #7


    User Avatar
    Staff Emeritus
    Science Advisor

    What would be an "approximation" to an integer?
  9. Sep 16, 2006 #8
    -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...
  10. Sep 16, 2006 #9

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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).
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Solving x^{n}+a=mod(b)
  1. A=x^b mod p, solvable? (Replies: 3)

  2. Solving mod n? (Replies: 3)

  3. Inverse of b mod n? (Replies: 1)