Integer square root and perfect square test
authortb <tb@openbsd.org>
Wed, 13 Jul 2022 06:28:22 +0000 (06:28 +0000)
committertb <tb@openbsd.org>
Wed, 13 Jul 2022 06:28:22 +0000 (06:28 +0000)
commite9fb66355c358c2edac8ce861ef8c452ade366c1
treeb51a6676aa923562952c7bb625b397e9f2cd8f1c
parenta8fb1317a5e2edb3840a0883a9d941bba5744a3f
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
lib/libcrypto/bn/bn_isqrt.c [new file with mode: 0644]
lib/libcrypto/bn/bn_lcl.h