NAME

BN_mod_sqrt — square root in a prime field

SYNOPSIS

#include <openssl/bn.h>

BIGNUM *
BN_mod_sqrt(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx);

DESCRIPTION

BN_mod_sqrt() solves

$r^2\equiv a\left(\mathrm{mod}p\right)$

for r in the prime field of characteristic p using the Tonelli-Shanks algorithm if needed and places one of the two solutions into r. The other solution is p - r.

The argument p is expected to be a prime number.

RETURN VALUES

In case of success, BN_mod_sqrt() returns r, or a newly allocated BIGNUM object if the r argument is NULL.

In case of failure, NULL is returned. This for example happens if a is not a quadratic residue or if memory allocation fails.

SEE ALSO

BN_CTX_new(3), BN_kronecker(3), BN_mod_sqr(3), BN_new(3)

Henri Cohen, A Course in Computational Algebraic Number Theory, Springer, Berlin, 1993, Algorithm 1.5.1.

HISTORY

BN_mod_sqrt() first appeared in OpenSSL 0.9.7 and has been available since OpenBSD 3.2.

CAVEATS

If p is not prime, BN_mod_sqrt() may succeed or fail. If it succeeds, the square of the returned value is congruent to a modulo p. If it fails, the reason reported by ERR_get_error(3) is often misleading. In particular, even if a is a perfect square, BN_mod_sqrt() often reports “not a square” instead of “p is not prime”.