1 #include "tommath_private.h"
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis */
4 /* SPDX-License-Identifier: Unlicense */
6 /* this function is less generic than mp_n_root, simpler and faster */
7 mp_err mp_sqrt(const mp_int *arg, mp_int *ret)
12 /* must be positive */
13 if (arg->sign == MP_NEG) {
18 if (MP_IS_ZERO(arg)) {
23 if ((err = mp_init_copy(&t1, arg)) != MP_OKAY) {
27 if ((err = mp_init(&t2)) != MP_OKAY) {
31 /* First approx. (not very bad for large arg) */
32 mp_rshd(&t1, t1.used/2);
35 if ((err = mp_div(arg, &t1, &t2, NULL)) != MP_OKAY) {
38 if ((err = mp_add(&t1, &t2, &t1)) != MP_OKAY) {
41 if ((err = mp_div_2(&t1, &t1)) != MP_OKAY) {
44 /* And now t1 > sqrt(arg) */
46 if ((err = mp_div(arg, &t1, &t2, NULL)) != MP_OKAY) {
49 if ((err = mp_add(&t1, &t2, &t1)) != MP_OKAY) {
52 if ((err = mp_div_2(&t1, &t1)) != MP_OKAY) {
55 /* t1 >= sqrt(arg) >= t2 at this point */
56 } while (mp_cmp_mag(&t1, &t2) == MP_GT);