CVSROOT: /cvs
Module name: src
Changes by: t...@cvs.openbsd.org 2022/07/13 00:28:22
Modified files:
lib/libcrypto/bn: bn_lcl.h
Added files:
lib/libcrypto/bn: bn_isqrt.c
Log message:
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
