Mercurial > dropbear

comparison libtommath/bn_mp_exteuclid.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_EXTEUCLID_C 2 #ifdef BN_MP_EXTEUCLID_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 /* Extended euclidean algorithm of (a, b) produces 6 /* Extended euclidean algorithm of (a, b) produces
16 a*u1 + b*u2 = u3 7 a*u1 + b*u2 = u3
17 */ 8 */
18 int mp_exteuclid(const mp_int *a, const mp_int *b, mp_int *U1, mp_int *U2, mp_int *U3) 9 mp_err mp_exteuclid(const mp_int *a, const mp_int *b, mp_int *U1, mp_int *U2, mp_int *U3)
19 { 10 {
20 mp_int u1, u2, u3, v1, v2, v3, t1, t2, t3, q, tmp; 11 mp_int u1, u2, u3, v1, v2, v3, t1, t2, t3, q, tmp;
21 int err; 12 mp_err err;
22 13
23 if ((err = mp_init_multi(&u1, &u2, &u3, &v1, &v2, &v3, &t1, &t2, &t3, &q, &tmp, NULL)) != MP_OKAY) { 14 if ((err = mp_init_multi(&u1, &u2, &u3, &v1, &v2, &v3, &t1, &t2, &t3, &q, &tmp, NULL)) != MP_OKAY) {
24 return err; 15 return err;
25 } 16 }
26 17
27 /* initialize, (u1,u2,u3) = (1,0,a) */ 18 /* initialize, (u1,u2,u3) = (1,0,a) */
28 mp_set(&u1, 1uL); 19 mp_set(&u1, 1uL);
29 if ((err = mp_copy(a, &u3)) != MP_OKAY) { 20 if ((err = mp_copy(a, &u3)) != MP_OKAY) goto LBL_ERR;
30 goto LBL_ERR;
31 }
32 21
33 /* initialize, (v1,v2,v3) = (0,1,b) */ 22 /* initialize, (v1,v2,v3) = (0,1,b) */
34 mp_set(&v2, 1uL); 23 mp_set(&v2, 1uL);
35 if ((err = mp_copy(b, &v3)) != MP_OKAY) { 24 if ((err = mp_copy(b, &v3)) != MP_OKAY) goto LBL_ERR;
36 goto LBL_ERR;
37 }
38 25
39 /* loop while v3 != 0 */ 26 /* loop while v3 != 0 */
40 while (mp_iszero(&v3) == MP_NO) { 27 while (!MP_IS_ZERO(&v3)) {
41 /* q = u3/v3 */ 28 /* q = u3/v3 */
42 if ((err = mp_div(&u3, &v3, &q, NULL)) != MP_OKAY) { 29 if ((err = mp_div(&u3, &v3, &q, NULL)) != MP_OKAY) goto LBL_ERR;
43 goto LBL_ERR;
44 }
45 30
46 /* (t1,t2,t3) = (u1,u2,u3) - (v1,v2,v3)q */ 31 /* (t1,t2,t3) = (u1,u2,u3) - (v1,v2,v3)q */
47 if ((err = mp_mul(&v1, &q, &tmp)) != MP_OKAY) { 32 if ((err = mp_mul(&v1, &q, &tmp)) != MP_OKAY) goto LBL_ERR;
48 goto LBL_ERR; 33 if ((err = mp_sub(&u1, &tmp, &t1)) != MP_OKAY) goto LBL_ERR;
49 } 34 if ((err = mp_mul(&v2, &q, &tmp)) != MP_OKAY) goto LBL_ERR;
50 if ((err = mp_sub(&u1, &tmp, &t1)) != MP_OKAY) { 35 if ((err = mp_sub(&u2, &tmp, &t2)) != MP_OKAY) goto LBL_ERR;
51 goto LBL_ERR; 36 if ((err = mp_mul(&v3, &q, &tmp)) != MP_OKAY) goto LBL_ERR;
52 } 37 if ((err = mp_sub(&u3, &tmp, &t3)) != MP_OKAY) goto LBL_ERR;
53 if ((err = mp_mul(&v2, &q, &tmp)) != MP_OKAY) {
54 goto LBL_ERR;
55 }
56 if ((err = mp_sub(&u2, &tmp, &t2)) != MP_OKAY) {
57 goto LBL_ERR;
58 }
59 if ((err = mp_mul(&v3, &q, &tmp)) != MP_OKAY) {
60 goto LBL_ERR;
61 }
62 if ((err = mp_sub(&u3, &tmp, &t3)) != MP_OKAY) {
63 goto LBL_ERR;
64 }
65 38
66 /* (u1,u2,u3) = (v1,v2,v3) */ 39 /* (u1,u2,u3) = (v1,v2,v3) */
67 if ((err = mp_copy(&v1, &u1)) != MP_OKAY) { 40 if ((err = mp_copy(&v1, &u1)) != MP_OKAY) goto LBL_ERR;
68 goto LBL_ERR; 41 if ((err = mp_copy(&v2, &u2)) != MP_OKAY) goto LBL_ERR;
69 } 42 if ((err = mp_copy(&v3, &u3)) != MP_OKAY) goto LBL_ERR;
70 if ((err = mp_copy(&v2, &u2)) != MP_OKAY) {
71 goto LBL_ERR;
72 }
73 if ((err = mp_copy(&v3, &u3)) != MP_OKAY) {
74 goto LBL_ERR;
75 }
76 43
77 /* (v1,v2,v3) = (t1,t2,t3) */ 44 /* (v1,v2,v3) = (t1,t2,t3) */
78 if ((err = mp_copy(&t1, &v1)) != MP_OKAY) { 45 if ((err = mp_copy(&t1, &v1)) != MP_OKAY) goto LBL_ERR;
79 goto LBL_ERR; 46 if ((err = mp_copy(&t2, &v2)) != MP_OKAY) goto LBL_ERR;
80 } 47 if ((err = mp_copy(&t3, &v3)) != MP_OKAY) goto LBL_ERR;
81 if ((err = mp_copy(&t2, &v2)) != MP_OKAY) {
82 goto LBL_ERR;
83 }
84 if ((err = mp_copy(&t3, &v3)) != MP_OKAY) {
85 goto LBL_ERR;
86 }
87 } 48 }
88 49
89 /* make sure U3 >= 0 */ 50 /* make sure U3 >= 0 */
90 if (u3.sign == MP_NEG) { 51 if (u3.sign == MP_NEG) {
91 if ((err = mp_neg(&u1, &u1)) != MP_OKAY) { 52 if ((err = mp_neg(&u1, &u1)) != MP_OKAY) goto LBL_ERR;
92 goto LBL_ERR; 53 if ((err = mp_neg(&u2, &u2)) != MP_OKAY) goto LBL_ERR;
93 } 54 if ((err = mp_neg(&u3, &u3)) != MP_OKAY) goto LBL_ERR;
94 if ((err = mp_neg(&u2, &u2)) != MP_OKAY) {
95 goto LBL_ERR;
96 }
97 if ((err = mp_neg(&u3, &u3)) != MP_OKAY) {
98 goto LBL_ERR;
99 }
100 } 55 }
101 56
102 /* copy result out */ 57 /* copy result out */
103 if (U1 != NULL) { 58 if (U1 != NULL) {
104 mp_exch(U1, &u1); 59 mp_exch(U1, &u1);
114 LBL_ERR: 69 LBL_ERR:
115 mp_clear_multi(&u1, &u2, &u3, &v1, &v2, &v3, &t1, &t2, &t3, &q, &tmp, NULL); 70 mp_clear_multi(&u1, &u2, &u3, &v1, &v2, &v3, &t1, &t2, &t3, &q, &tmp, NULL);
116 return err; 71 return err;
117 } 72 }
118 #endif 73 #endif
119
120 /* ref: HEAD -> master, tag: v1.1.0 */
121 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
122 /* commit time: 2019-01-28 20:32:32 +0100 */