Mercurial > dropbear

comparison libtommath/bn_mp_gcd.c @ 1692:1051e4eea25a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Update LibTomMath to 1.2.0 (#84) * update C files * update other files * update headers * update makefiles * remove mp_set/get_double() * use ltm 1.2.0 API * update ltm_desc * use bundled tommath if system-tommath is too old * XMALLOC etc. were changed to MP_MALLOC etc.
author Steffen Jaeckel <s@jaeckel.eu>
date Tue, 26 May 2020 17:36:47 +0200
parents f52919ffd3b1
children
comparison
equal deleted inserted replaced
1691:2d3745d58843 1692:1051e4eea25a
1 #include "tommath_private.h" 1 #include "tommath_private.h"
2 #ifdef BN_MP_GCD_C 2 #ifdef BN_MP_GCD_C
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis 3 /* LibTomMath, multiple-precision integer library -- Tom St Denis */
4 * 4 /* SPDX-License-Identifier: Unlicense */
5 * LibTomMath is a library that provides multiple-precision
6 * integer arithmetic as well as number theoretic functionality.
7 *
8 * The library was designed directly after the MPI library by
9 * Michael Fromberger but has been written from scratch with
10 * additional optimizations in place.
11 *
12 * SPDX-License-Identifier: Unlicense
13 */
14 5
15 /* Greatest Common Divisor using the binary method */ 6 /* Greatest Common Divisor using the binary method */
16 int mp_gcd(const mp_int *a, const mp_int *b, mp_int *c) 7 mp_err mp_gcd(const mp_int *a, const mp_int *b, mp_int *c)
17 { 8 {
18 mp_int u, v; 9 mp_int u, v;
19 int k, u_lsb, v_lsb, res; 10 int k, u_lsb, v_lsb;
11 mp_err err;
20 12
21 /* either zero than gcd is the largest */ 13 /* either zero than gcd is the largest */
22 if (mp_iszero(a) == MP_YES) { 14 if (MP_IS_ZERO(a)) {
23 return mp_abs(b, c); 15 return mp_abs(b, c);
24 } 16 }
25 if (mp_iszero(b) == MP_YES) { 17 if (MP_IS_ZERO(b)) {
26 return mp_abs(a, c); 18 return mp_abs(a, c);
27 } 19 }
28 20
29 /* get copies of a and b we can modify */ 21 /* get copies of a and b we can modify */
30 if ((res = mp_init_copy(&u, a)) != MP_OKAY) { 22 if ((err = mp_init_copy(&u, a)) != MP_OKAY) {
31 return res; 23 return err;
32 } 24 }
33 25
34 if ((res = mp_init_copy(&v, b)) != MP_OKAY) { 26 if ((err = mp_init_copy(&v, b)) != MP_OKAY) {
35 goto LBL_U; 27 goto LBL_U;
36 } 28 }
37 29
38 /* must be positive for the remainder of the algorithm */ 30 /* must be positive for the remainder of the algorithm */
39 u.sign = v.sign = MP_ZPOS; 31 u.sign = v.sign = MP_ZPOS;
40 32
41 /* B1. Find the common power of two for u and v */ 33 /* B1. Find the common power of two for u and v */
42 u_lsb = mp_cnt_lsb(&u); 34 u_lsb = mp_cnt_lsb(&u);
43 v_lsb = mp_cnt_lsb(&v); 35 v_lsb = mp_cnt_lsb(&v);
44 k = MIN(u_lsb, v_lsb); 36 k = MP_MIN(u_lsb, v_lsb);
45 37
46 if (k > 0) { 38 if (k > 0) {
47 /* divide the power of two out */ 39 /* divide the power of two out */
48 if ((res = mp_div_2d(&u, k, &u, NULL)) != MP_OKAY) { 40 if ((err = mp_div_2d(&u, k, &u, NULL)) != MP_OKAY) {
49 goto LBL_V; 41 goto LBL_V;
50 } 42 }
51 43
52 if ((res = mp_div_2d(&v, k, &v, NULL)) != MP_OKAY) { 44 if ((err = mp_div_2d(&v, k, &v, NULL)) != MP_OKAY) {
53 goto LBL_V; 45 goto LBL_V;
54 } 46 }
55 } 47 }
56 48
57 /* divide any remaining factors of two out */ 49 /* divide any remaining factors of two out */
58 if (u_lsb != k) { 50 if (u_lsb != k) {
59 if ((res = mp_div_2d(&u, u_lsb - k, &u, NULL)) != MP_OKAY) { 51 if ((err = mp_div_2d(&u, u_lsb - k, &u, NULL)) != MP_OKAY) {
60 goto LBL_V; 52 goto LBL_V;
61 } 53 }
62 } 54 }
63 55
64 if (v_lsb != k) { 56 if (v_lsb != k) {
65 if ((res = mp_div_2d(&v, v_lsb - k, &v, NULL)) != MP_OKAY) { 57 if ((err = mp_div_2d(&v, v_lsb - k, &v, NULL)) != MP_OKAY) {
66 goto LBL_V; 58 goto LBL_V;
67 } 59 }
68 } 60 }
69 61
70 while (mp_iszero(&v) == MP_NO) { 62 while (!MP_IS_ZERO(&v)) {
71 /* make sure v is the largest */ 63 /* make sure v is the largest */
72 if (mp_cmp_mag(&u, &v) == MP_GT) { 64 if (mp_cmp_mag(&u, &v) == MP_GT) {
73 /* swap u and v to make sure v is >= u */ 65 /* swap u and v to make sure v is >= u */
74 mp_exch(&u, &v); 66 mp_exch(&u, &v);
75 } 67 }
76 68
77 /* subtract smallest from largest */ 69 /* subtract smallest from largest */
78 if ((res = s_mp_sub(&v, &u, &v)) != MP_OKAY) { 70 if ((err = s_mp_sub(&v, &u, &v)) != MP_OKAY) {
79 goto LBL_V; 71 goto LBL_V;
80 } 72 }
81 73
82 /* Divide out all factors of two */ 74 /* Divide out all factors of two */
83 if ((res = mp_div_2d(&v, mp_cnt_lsb(&v), &v, NULL)) != MP_OKAY) { 75 if ((err = mp_div_2d(&v, mp_cnt_lsb(&v), &v, NULL)) != MP_OKAY) {
84 goto LBL_V; 76 goto LBL_V;
85 } 77 }
86 } 78 }
87 79
88 /* multiply by 2**k which we divided out at the beginning */ 80 /* multiply by 2**k which we divided out at the beginning */
89 if ((res = mp_mul_2d(&u, k, c)) != MP_OKAY) { 81 if ((err = mp_mul_2d(&u, k, c)) != MP_OKAY) {
90 goto LBL_V; 82 goto LBL_V;
91 } 83 }
92 c->sign = MP_ZPOS; 84 c->sign = MP_ZPOS;
93 res = MP_OKAY; 85 err = MP_OKAY;
94 LBL_V: 86 LBL_V:
95 mp_clear(&u); 87 mp_clear(&u);
96 LBL_U: 88 LBL_U:
97 mp_clear(&v); 89 mp_clear(&v);
98 return res; 90 return err;
99 } 91 }
100 #endif 92 #endif
101
102 /* ref: HEAD -> master, tag: v1.1.0 */
103 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
104 /* commit time: 2019-01-28 20:32:32 +0100 */