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

Newton method and f(x)=0mod(p)

  1. Mar 27, 2007 #1

    tpm

    User Avatar

    Let be the congruence equation with f(x) a Polynomial of grade k then:

    [tex] f(x)=0mod(p) [/tex]

    then if we have as a first approximation [tex] f(x_{n+1})=0mod(p) [/tex]

    then using a linear interpolation: [tex] f(x_{n})+f'(x_{n})(x_{n+1}-x_{n})=0mod(p) [/tex] or [tex] x_{n+1}=(x_{n}+\frac{f(x_{n}}{f'(x_{n})})0mod(p/f'(x_{n}) [/tex]

    So we have 'modified' Newton method for solving Polynomial congruences. :Bigrin:
     
  2. jcsd
  3. Mar 28, 2007 #2

    tpm

    User Avatar

    I think in this case the mai question is if the linear interpolation solution

    [tex] f(x_{n})+f'(x_{n})(x_{n+1}-x_{n})=0mod(p) [/tex] (1)

    will work to solve the general congruence [tex] f(x)=0mod(p) [/tex] for f(x) a POlynomial solving it by iterations using Newton method, where from (1) form an initial ansatz x_n we can get the next approximate value x_{n+1}
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Newton method and f(x)=0mod(p)
  1. X² + y² = 1 (mod p) (Replies: 7)

  2. Calculate f(x)modg(x) (Replies: 1)

Loading...