12345678910111213141516171819202122232425262728293031323334353637383940 |
- #!/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
|