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

  • Thread starter tpm
  • Start date
  • #1
tpm
72
0

Main Question or Discussion Point

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:
 

Answers and Replies

  • #2
tpm
72
0
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}
 

Related Threads on Newton method and f(x)=0mod(p)

  • Last Post
Replies
1
Views
3K
Replies
2
Views
2K
Replies
4
Views
6K
  • Last Post
Replies
12
Views
3K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
3
Views
4K
  • Last Post
Replies
7
Views
8K
  • Last Post
Replies
2
Views
4K
Replies
12
Views
7K
Top