1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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

    CRGreathouse

    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

    HallsofIvy

    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)

Loading...