Integer square root and perfect square test

This adds an implementation of the integer square root using a variant
of Newton's method with adaptive precision. The implementation is based
on a pure Python description of cpython's math.isqrt(). This algorithm
is proven to be correct with a tricky but very neat loop invariant:
https://github.com/mdickinson/snippets/blob/master/proofs/isqrt/src/isqrt.lean

Using this algorithm instead of Newton method, implement Algorithm 1.7.3
(square test) from H. Cohen, "A course in computational algebraic number
theory" to detect perfect squares.

ok jsing

0 files changed, 0 insertions, 0 deletions