1.\" $OpenBSD: BN_mod_sqrt.3,v 1.2 2022/12/06 22:22:42 tb Exp $ 2.\" 3.\" Copyright (c) 2022 Ingo Schwarze <schwarze@openbsd.org> 4.\" 5.\" Permission to use, copy, modify, and distribute this software for any 6.\" purpose with or without fee is hereby granted, provided that the above 7.\" copyright notice and this permission notice appear in all copies. 8.\" 9.\" THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 10.\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 11.\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 12.\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 13.\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 14.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 15.\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 16.\" 17.Dd $Mdocdate: December 6 2022 $ 18.Dt BN_MOD_SQRT 3 19.Os 20.Sh NAME 21.Nm BN_mod_sqrt 22.Nd square root in a prime field 23.Sh SYNOPSIS 24.In openssl/bn.h 25.Ft BIGNUM * 26.Fo BN_mod_sqrt 27.Fa "BIGNUM *r" 28.Fa "const BIGNUM *a" 29.Fa "const BIGNUM *p" 30.Fa "BN_CTX *ctx" 31.Fc 32.Sh DESCRIPTION 33.Fn BN_mod_sqrt 34solves 35.Bd -unfilled -offset indent 36.EQ 37r sup 2 == a ( roman mod p ) 38.EN 39.Ed 40.Pp 41for 42.Fa r 43in the prime field of characteristic 44.Fa p 45using the Tonelli-Shanks algorithm if needed 46and places one of the two solutions into 47.Fa r . 48The other solution is 49.Fa p 50\- 51.Fa r . 52.Pp 53The argument 54.Fa p 55is expected to be a prime number. 56.Sh RETURN VALUES 57In case of success, 58.Fn BN_mod_sqrt 59returns 60.Fa r , 61or a newly allocated 62.Vt BIGNUM 63object if the 64.Fa r 65argument is 66.Dv NULL . 67.Pp 68In case of failure, 69.Dv NULL 70is returned. 71This for example happens if 72.Fa a 73is not a quadratic residue or if memory allocation fails. 74.Sh SEE ALSO 75.Xr BN_CTX_new 3 , 76.Xr BN_kronecker 3 , 77.Xr BN_mod_sqr 3 , 78.Xr BN_new 3 79.Rs 80.%A Henri Cohen 81.%B A Course in Computational Algebraic Number Theory 82.%I Springer 83.%C Berlin 84.%D 1993 85.%O Algorithm 1.5.1 86.Re 87.Sh HISTORY 88.Fn BN_mod_sqrt 89first appeared in OpenSSL 0.9.7 and has been available since 90.Ox 3.2 . 91.Sh CAVEATS 92If 93.Fa p 94is not prime, 95.Fn BN_mod_sqrt 96may succeed or fail. 97If it succeeds, the square of the returned value is congruent to 98.Fa a 99modulo 100.Fa p . 101If it fails, the reason reported by 102.Xr ERR_get_error 3 103is often misleading. 104In particular, even if 105.Fa a 106is a perfect square, 107.Fn BN_mod_sqrt 108often reports 109.Dq not a square 110instead of 111.Dq p is not prime . 112