Mercurial > dropbear
diff libtommath/bn_mp_n_root_ex.c @ 1655:f52919ffd3b1
update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79)
* make key-generation compliant to FIPS 186.4
* fix includes in tommath_class.h
* update fuzzcorpus instead of error-out
* fixup fuzzing make-targets
* update Makefile.in
* apply necessary patches to ltm sources
* clean-up not required ltm files
* update to vanilla ltm 1.1.0
this already only contains the required files
* remove set/get double
author | Steffen Jaeckel <s_jaeckel@gmx.de> |
---|---|
date | Mon, 16 Sep 2019 15:50:38 +0200 |
parents | 8bba51a55704 |
children |
line wrap: on
line diff
--- a/libtommath/bn_mp_n_root_ex.c Wed May 15 21:59:45 2019 +0800 +++ b/libtommath/bn_mp_n_root_ex.c Mon Sep 16 15:50:38 2019 +0200 @@ -1,4 +1,4 @@ -#include <tommath_private.h> +#include "tommath_private.h" #ifdef BN_MP_N_ROOT_EX_C /* LibTomMath, multiple-precision integer library -- Tom St Denis * @@ -9,10 +9,7 @@ * Michael Fromberger but has been written from scratch with * additional optimizations in place. * - * The library is free for all purposes without any express - * guarantee it works. - * - * Tom St Denis, [email protected], http://libtom.org + * SPDX-License-Identifier: Unlicense */ /* find the n'th root of an integer @@ -25,108 +22,108 @@ * each step involves a fair bit. This is not meant to * find huge roots [square and cube, etc]. */ -int mp_n_root_ex (mp_int * a, mp_digit b, mp_int * c, int fast) +int mp_n_root_ex(const mp_int *a, mp_digit b, mp_int *c, int fast) { - mp_int t1, t2, t3; - int res, neg; + mp_int t1, t2, t3, a_; + int res; - /* input must be positive if b is even */ - if (((b & 1) == 0) && (a->sign == MP_NEG)) { - return MP_VAL; - } - - if ((res = mp_init (&t1)) != MP_OKAY) { - return res; - } - - if ((res = mp_init (&t2)) != MP_OKAY) { - goto LBL_T1; - } + /* input must be positive if b is even */ + if (((b & 1u) == 0u) && (a->sign == MP_NEG)) { + return MP_VAL; + } - if ((res = mp_init (&t3)) != MP_OKAY) { - goto LBL_T2; - } - - /* if a is negative fudge the sign but keep track */ - neg = a->sign; - a->sign = MP_ZPOS; + if ((res = mp_init(&t1)) != MP_OKAY) { + return res; + } - /* t2 = 2 */ - mp_set (&t2, 2); + if ((res = mp_init(&t2)) != MP_OKAY) { + goto LBL_T1; + } - do { - /* t1 = t2 */ - if ((res = mp_copy (&t2, &t1)) != MP_OKAY) { - goto LBL_T3; - } - - /* t2 = t1 - ((t1**b - a) / (b * t1**(b-1))) */ + if ((res = mp_init(&t3)) != MP_OKAY) { + goto LBL_T2; + } - /* t3 = t1**(b-1) */ - if ((res = mp_expt_d_ex (&t1, b - 1, &t3, fast)) != MP_OKAY) { - goto LBL_T3; - } + /* if a is negative fudge the sign but keep track */ + a_ = *a; + a_.sign = MP_ZPOS; - /* numerator */ - /* t2 = t1**b */ - if ((res = mp_mul (&t3, &t1, &t2)) != MP_OKAY) { - goto LBL_T3; - } - - /* t2 = t1**b - a */ - if ((res = mp_sub (&t2, a, &t2)) != MP_OKAY) { - goto LBL_T3; - } + /* t2 = 2 */ + mp_set(&t2, 2uL); - /* denominator */ - /* t3 = t1**(b-1) * b */ - if ((res = mp_mul_d (&t3, b, &t3)) != MP_OKAY) { - goto LBL_T3; - } + do { + /* t1 = t2 */ + if ((res = mp_copy(&t2, &t1)) != MP_OKAY) { + goto LBL_T3; + } - /* t3 = (t1**b - a)/(b * t1**(b-1)) */ - if ((res = mp_div (&t2, &t3, &t3, NULL)) != MP_OKAY) { - goto LBL_T3; - } + /* t2 = t1 - ((t1**b - a) / (b * t1**(b-1))) */ - if ((res = mp_sub (&t1, &t3, &t2)) != MP_OKAY) { - goto LBL_T3; - } - } while (mp_cmp (&t1, &t2) != MP_EQ); + /* t3 = t1**(b-1) */ + if ((res = mp_expt_d_ex(&t1, b - 1u, &t3, fast)) != MP_OKAY) { + goto LBL_T3; + } - /* result can be off by a few so check */ - for (;;) { - if ((res = mp_expt_d_ex (&t1, b, &t2, fast)) != MP_OKAY) { - goto LBL_T3; - } - - if (mp_cmp (&t2, a) == MP_GT) { - if ((res = mp_sub_d (&t1, 1, &t1)) != MP_OKAY) { + /* numerator */ + /* t2 = t1**b */ + if ((res = mp_mul(&t3, &t1, &t2)) != MP_OKAY) { goto LBL_T3; } - } else { - break; - } - } + + /* t2 = t1**b - a */ + if ((res = mp_sub(&t2, &a_, &t2)) != MP_OKAY) { + goto LBL_T3; + } - /* reset the sign of a first */ - a->sign = neg; + /* denominator */ + /* t3 = t1**(b-1) * b */ + if ((res = mp_mul_d(&t3, b, &t3)) != MP_OKAY) { + goto LBL_T3; + } + + /* t3 = (t1**b - a)/(b * t1**(b-1)) */ + if ((res = mp_div(&t2, &t3, &t3, NULL)) != MP_OKAY) { + goto LBL_T3; + } + + if ((res = mp_sub(&t1, &t3, &t2)) != MP_OKAY) { + goto LBL_T3; + } + } while (mp_cmp(&t1, &t2) != MP_EQ); - /* set the result */ - mp_exch (&t1, c); + /* result can be off by a few so check */ + for (;;) { + if ((res = mp_expt_d_ex(&t1, b, &t2, fast)) != MP_OKAY) { + goto LBL_T3; + } - /* set the sign of the result */ - c->sign = neg; + if (mp_cmp(&t2, &a_) == MP_GT) { + if ((res = mp_sub_d(&t1, 1uL, &t1)) != MP_OKAY) { + goto LBL_T3; + } + } else { + break; + } + } - res = MP_OKAY; + /* set the result */ + mp_exch(&t1, c); + + /* set the sign of the result */ + c->sign = a->sign; + + res = MP_OKAY; -LBL_T3:mp_clear (&t3); -LBL_T2:mp_clear (&t2); -LBL_T1:mp_clear (&t1); - return res; +LBL_T3: + mp_clear(&t3); +LBL_T2: + mp_clear(&t2); +LBL_T1: + mp_clear(&t1); + return res; } #endif -/* ref: $Format:%D$ */ -/* git commit: $Format:%H$ */ -/* commit time: $Format:%ai$ */ +/* ref: HEAD -> master, tag: v1.1.0 */ +/* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */ +/* commit time: 2019-01-28 20:32:32 +0100 */