newton_s_method_for_polynomials.sf

#!/usr/bin/ruby

# Newton's method for computing n-th roots of polynomials,
# applied to the computation of "n-th roots" of p-adic numbers.

# Inspired by:
#   https://yewtu.be/watch?v=3gyHKCDq1YA

func newton_inverse_method(f, r, v) {
    var x = Poly(1)
    r.times {
        x = (x - (f(x).eval(v) / derivative(f(x)).eval(v)))
    }
    x.eval(v)
}

for n in (1..8) {
    say newton_inverse_method(func(x) { x**2 + 7 }, n, 1).as_rat
}

# Problem: find a value for x, such that x^2 + 7 is divisible by 2^50.
# One such solution, is x = 206036503412917, which gives 42451040738620958589002448896.

say ''
var t = Mod(newton_inverse_method(func(x) { x**2 + 7 }, 6, 1), 2**50)

say t                               #=> Mod(206036503412917, 1125899906842624)
say (t**2 + 7)                      #=> Mod(0, 1125899906842624)
say factor_exp(t.lift**2 + 7)       #=> [[2, 51], [29, 1], [1789, 1], [363370967, 1]]

__END__
-3
-1/3
31/3
449/93
70529/41757
-3615594751/2945079453
23820962743960351231/10648213811544751203
-113126467792729861089136567110653207551/253650704494531566925735633658389780893