BN_MOD_SQRT(3)

📦 version 4.4.0, in alpine 3.24, arch rolling

💖 NAME 💖

Okay so bestie, welcome to BN_MOD_SQRT(3) from the Library Functions Manual — the page for BN_mod_sqrt — and it's literally square root in a prime field. That's the whole vibe: find the modular square root, slay, go home. 💅✨

✨ SYNOPSIS ✨

You're linking against libcrypto and pulling in <openssl/bn.h>, so the setup looks like this:

library “libcrypto” #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 sup 2 == a ( roman mod p )

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. So yeah, two roots, and one of them gets the main-character slot. 👑

The argument p is expected to be a prime number. Expected, bestie — we'll get to the caveat. 🙈

🎀 RETURN VALUES 🎀

  • On success? BN_mod_sqrt() returns r, or a newly allocated BIGNUM object if the r argument is NULL. Slay. 🫶
  • On failure? NULL is returned. This for example happens if a is not a quadratic residue or if memory allocation fails. Not slay. 😭

🦋 SEE ALSO 🦋

Also the reference to end all references: Henri Cohen, A Course in Computational Algebraic Number Theory, Springer, Berlin, 1993, Algorithm 1.5.1. Ngl, that's iconic behavior. 📚

🌸 HISTORY 🌸

BN_mod_sqrt() first appeared in OpenSSL 0.9.7 and has been available since OpenBSD 3.2. History lesson complete, periodt. ⭐

💀 CAVEATS 💀

🚨 Bestie, listen: if p is not prime, BN_mod_sqrt() may succeed or fail. That's the whole warning.

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”. So the error message is lowkey not giving what it needs to give. 🙈

💖 Cute source/version sign-off: this page comes from Debian, dated June 8, 2025, and it's BN_MOD_SQRT(3). Bye bestie! 💖

📦 where this page comes from