Mercurial > dropbear

comparison libtommath/bn_mp_prime_miller_rabin.c @ 1733:d529a52b2f7c coverity coverity

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
merge coverity from main
author Matt Johnston <matt@ucc.asn.au>
date Fri, 26 Jun 2020 21:07:34 +0800
parents 1051e4eea25a
children
comparison
equal deleted inserted replaced
1643:b59623a64678 1733:d529a52b2f7c
1 #include <tommath_private.h> 1 #include "tommath_private.h"
2 #ifdef BN_MP_PRIME_MILLER_RABIN_C 2 #ifdef BN_MP_PRIME_MILLER_RABIN_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 * The library is free for all purposes without any express
13 * guarantee it works.
14 *
15 * Tom St Denis, [email protected], http://libtom.org
16 */
17 5
18 /* Miller-Rabin test of "a" to the base of "b" as described in 6 /* Miller-Rabin test of "a" to the base of "b" as described in
19 * HAC pp. 139 Algorithm 4.24 7 * HAC pp. 139 Algorithm 4.24
20 * 8 *
21 * Sets result to 0 if definitely composite or 1 if probably prime. 9 * Sets result to 0 if definitely composite or 1 if probably prime.
22 * Randomly the chance of error is no more than 1/4 and often 10 * Randomly the chance of error is no more than 1/4 and often
23 * very much lower. 11 * very much lower.
24 */ 12 */
25 int mp_prime_miller_rabin (mp_int * a, mp_int * b, int *result) 13 mp_err mp_prime_miller_rabin(const mp_int *a, const mp_int *b, mp_bool *result)
26 { 14 {
27 mp_int n1, y, r; 15 mp_int n1, y, r;
28 int s, j, err; 16 mp_err err;
17 int s, j;
29 18
30 /* default */ 19 /* default */
31 *result = MP_NO; 20 *result = MP_NO;
32 21
33 /* ensure b > 1 */ 22 /* ensure b > 1 */
34 if (mp_cmp_d(b, 1) != MP_GT) { 23 if (mp_cmp_d(b, 1uL) != MP_GT) {
35 return MP_VAL; 24 return MP_VAL;
36 } 25 }
37 26
38 /* get n1 = a - 1 */ 27 /* get n1 = a - 1 */
39 if ((err = mp_init_copy (&n1, a)) != MP_OKAY) { 28 if ((err = mp_init_copy(&n1, a)) != MP_OKAY) {
40 return err; 29 return err;
41 } 30 }
42 if ((err = mp_sub_d (&n1, 1, &n1)) != MP_OKAY) { 31 if ((err = mp_sub_d(&n1, 1uL, &n1)) != MP_OKAY) {
43 goto LBL_N1; 32 goto LBL_N1;
44 } 33 }
45 34
46 /* set 2**s * r = n1 */ 35 /* set 2**s * r = n1 */
47 if ((err = mp_init_copy (&r, &n1)) != MP_OKAY) { 36 if ((err = mp_init_copy(&r, &n1)) != MP_OKAY) {
48 goto LBL_N1; 37 goto LBL_N1;
49 } 38 }
50 39
51 /* count the number of least significant bits 40 /* count the number of least significant bits
52 * which are zero 41 * which are zero
53 */ 42 */
54 s = mp_cnt_lsb(&r); 43 s = mp_cnt_lsb(&r);
55 44
56 /* now divide n - 1 by 2**s */ 45 /* now divide n - 1 by 2**s */
57 if ((err = mp_div_2d (&r, s, &r, NULL)) != MP_OKAY) { 46 if ((err = mp_div_2d(&r, s, &r, NULL)) != MP_OKAY) {
58 goto LBL_R; 47 goto LBL_R;
59 } 48 }
60 49
61 /* compute y = b**r mod a */ 50 /* compute y = b**r mod a */
62 if ((err = mp_init (&y)) != MP_OKAY) { 51 if ((err = mp_init(&y)) != MP_OKAY) {
63 goto LBL_R; 52 goto LBL_R;
64 } 53 }
65 if ((err = mp_exptmod (b, &r, a, &y)) != MP_OKAY) { 54 if ((err = mp_exptmod(b, &r, a, &y)) != MP_OKAY) {
66 goto LBL_Y; 55 goto LBL_Y;
67 } 56 }
68 57
69 /* if y != 1 and y != n1 do */ 58 /* if y != 1 and y != n1 do */
70 if ((mp_cmp_d (&y, 1) != MP_EQ) && (mp_cmp (&y, &n1) != MP_EQ)) { 59 if ((mp_cmp_d(&y, 1uL) != MP_EQ) && (mp_cmp(&y, &n1) != MP_EQ)) {
71 j = 1; 60 j = 1;
72 /* while j <= s-1 and y != n1 */ 61 /* while j <= s-1 and y != n1 */
73 while ((j <= (s - 1)) && (mp_cmp (&y, &n1) != MP_EQ)) { 62 while ((j <= (s - 1)) && (mp_cmp(&y, &n1) != MP_EQ)) {
74 if ((err = mp_sqrmod (&y, a, &y)) != MP_OKAY) { 63 if ((err = mp_sqrmod(&y, a, &y)) != MP_OKAY) {
64 goto LBL_Y;
65 }
66
67 /* if y == 1 then composite */
68 if (mp_cmp_d(&y, 1uL) == MP_EQ) {
69 goto LBL_Y;
70 }
71
72 ++j;
73 }
74
75 /* if y != n1 then composite */
76 if (mp_cmp(&y, &n1) != MP_EQ) {
75 goto LBL_Y; 77 goto LBL_Y;
76 } 78 }
79 }
77 80
78 /* if y == 1 then composite */ 81 /* probably prime now */
79 if (mp_cmp_d (&y, 1) == MP_EQ) { 82 *result = MP_YES;
80 goto LBL_Y; 83 LBL_Y:
81 } 84 mp_clear(&y);
82 85 LBL_R:
83 ++j; 86 mp_clear(&r);
84 } 87 LBL_N1:
85 88 mp_clear(&n1);
86 /* if y != n1 then composite */ 89 return err;
87 if (mp_cmp (&y, &n1) != MP_EQ) {
88 goto LBL_Y;
89 }
90 }
91
92 /* probably prime now */
93 *result = MP_YES;
94 LBL_Y:mp_clear (&y);
95 LBL_R:mp_clear (&r);
96 LBL_N1:mp_clear (&n1);
97 return err;
98 } 90 }
99 #endif 91 #endif
100
101 /* ref: $Format:%D$ */
102 /* git commit: $Format:%H$ */
103 /* commit time: $Format:%ai$ */