37 lines
1.3 KiB
Plaintext
37 lines
1.3 KiB
Plaintext
;Task.
|
|
|
|
Convert rational a/b to its approximate [[wp:Hensel%27s_lemma#Hensel's_lemma_for_p-adic_numbers|p-adic square root]]. To check the result,
|
|
square the root and construct rational m/n to compare with radicand a/b.
|
|
|
|
For rational reconstruction Lagrange's [[wp:Lattice_reduction|lattice basis reduction]] algorithm is used.
|
|
|
|
'''Recipe:''' find root {{math|''x<sub>1</sub>'' modulo p}} and build a sequence of solutions
|
|
{{math|''f''(''x<sub>k</sub>'') ≡ 0 (mod p<sup>k</sup>)}},
|
|
<br/>using the lifting equation
|
|
{{math|''x<sub>k+1</sub>'' = ''x<sub>k</sub>'' + ''d<sub>k</sub>'' * ''p<sup>k</sup>'' }}
|
|
with {{math|''d<sub>k</sub>'' = –(''f''(''x<sub>k</sub>'') / ''p<sup>k</sup>'') /
|
|
''f'' ′(''x<sub>1</sub>'') (mod p)}}.
|
|
<br/>The multipliers {{math|''d<sub>k</sub>''}} are the successive p-adic digits to find.
|
|
|
|
If evaluation of {{math|''f''(''x'') = ''bx<sup>2</sup>'' – ''a''}} overflows,
|
|
the expansion is cut off and might be too short to retrieve the radicand.
|
|
Setting a higher precision won't help, using a programming language with built-in
|
|
large integer support will.
|
|
|
|
|
|
;Related task.
|
|
|
|
[[p-Adic numbers, basic]]
|
|
|
|
|
|
;Reference.
|
|
|
|
[https://www.uvm.edu/~cvincen1/files/teaching/spring2017-math255/quadraticequation.pdf]
|
|
Solving {{math|''x<sup>2</sup>'' ≡ ''a'' (mod n)}}
|
|
|
|
|
|
__TOC__
|
|
|
|
|
|
|