/src/dropbear/libtommath/bn_mp_prime_next_prime.c

Source (jump to first uncovered line)
#include "tommath_private.h"
#ifdef BN_MP_PRIME_NEXT_PRIME_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis */
/* SPDX-License-Identifier: Unlicense */

/* finds the next prime after the number "a" using "t" trials
 * of Miller-Rabin.
 *
 * bbs_style = 1 means the prime must be congruent to 3 mod 4
 */
mp_err mp_prime_next_prime(mp_int *a, int t, int bbs_style)
{
   int      x, y;
   mp_ord   cmp;
   mp_err   err;
   mp_bool  res = MP_NO;
   mp_digit res_tab[PRIVATE_MP_PRIME_TAB_SIZE], step, kstep;
   mp_int   b;

   /* force positive */
   a->sign = MP_ZPOS;

   /* simple algo if a is less than the largest prime in the table */
   if (mp_cmp_d(a, s_mp_prime_tab[PRIVATE_MP_PRIME_TAB_SIZE-1]) == MP_LT) {
      /* find which prime it is bigger than "a" */
      for (x = 0; x < PRIVATE_MP_PRIME_TAB_SIZE; x++) {
         cmp = mp_cmp_d(a, s_mp_prime_tab[x]);
         if (cmp == MP_EQ) {
            continue;
         }
         if (cmp != MP_GT) {
            if ((bbs_style == 1) && ((s_mp_prime_tab[x] & 3u) != 3u)) {
               /* try again until we get a prime congruent to 3 mod 4 */
               continue;
            } else {
               mp_set(a, s_mp_prime_tab[x]);
               return MP_OKAY;
            }
         }
      }
      /* fall through to the sieve */
   }

   /* generate a prime congruent to 3 mod 4 or 1/3 mod 4? */
   if (bbs_style == 1) {
      kstep   = 4;
   } else {
      kstep   = 2;
   }

   /* at this point we will use a combination of a sieve and Miller-Rabin */

   if (bbs_style == 1) {
      /* if a mod 4 != 3 subtract the correct value to make it so */
      if ((a->dp[0] & 3u) != 3u) {
         if ((err = mp_sub_d(a, (a->dp[0] & 3u) + 1u, a)) != MP_OKAY) {
            return err;
         }
      }
   } else {
      if (MP_IS_EVEN(a)) {
         /* force odd */
         if ((err = mp_sub_d(a, 1uL, a)) != MP_OKAY) {
            return err;
         }
      }
   }

   /* generate the restable */
   for (x = 1; x < PRIVATE_MP_PRIME_TAB_SIZE; x++) {
      if ((err = mp_mod_d(a, s_mp_prime_tab[x], res_tab + x)) != MP_OKAY) {
         return err;
      }
   }

   /* init temp used for Miller-Rabin Testing */
   if ((err = mp_init(&b)) != MP_OKAY) {
      return err;
   }

   for (;;) {
      /* skip to the next non-trivially divisible candidate */
      step = 0;
      do {
         /* y == 1 if any residue was zero [e.g. cannot be prime] */
         y     =  0;

         /* increase step to next candidate */
         step += kstep;

         /* compute the new residue without using division */
         for (x = 1; x < PRIVATE_MP_PRIME_TAB_SIZE; x++) {
            /* add the step to each residue */
            res_tab[x] += kstep;

            /* subtract the modulus [instead of using division] */
            if (res_tab[x] >= s_mp_prime_tab[x]) {
               res_tab[x]  -= s_mp_prime_tab[x];
            }

            /* set flag if zero */
            if (res_tab[x] == 0u) {
               y = 1;
            }
         }
      } while ((y == 1) && (step < (((mp_digit)1 << MP_DIGIT_BIT) - kstep)));

      /* add the step */
      if ((err = mp_add_d(a, step, a)) != MP_OKAY) {
         goto LBL_ERR;
      }

      /* if didn't pass sieve and step == MP_MAX then skip test */
      if ((y == 1) && (step >= (((mp_digit)1 << MP_DIGIT_BIT) - kstep))) {
         continue;
      }

      if ((err = mp_prime_is_prime(a, t, &res)) != MP_OKAY) {
         goto LBL_ERR;
      }
      if (res == MP_YES) {
         break;
      }
   }

   err = MP_OKAY;
LBL_ERR:
   mp_clear(&b);
   return err;
}

#endif

Line	Count	Source (jump to first uncovered line)
1		#include "tommath_private.h"
2		#ifdef BN_MP_PRIME_NEXT_PRIME_C
3		/* LibTomMath, multiple-precision integer library -- Tom St Denis */
4		/* SPDX-License-Identifier: Unlicense */
5
6		/* finds the next prime after the number "a" using "t" trials
7		* of Miller-Rabin.
8		*
9		* bbs_style = 1 means the prime must be congruent to 3 mod 4
10		*/
11		mp_err mp_prime_next_prime(mp_int *a, int t, int bbs_style)
12	0	{
13	0	int x, y;
14	0	mp_ord cmp;
15	0	mp_err err;
16	0	mp_bool res = MP_NO;
17	0	mp_digit res_tab[PRIVATE_MP_PRIME_TAB_SIZE], step, kstep;
18	0	mp_int b;
19
20		/* force positive */
21	0	a->sign = MP_ZPOS;
22
23		/* simple algo if a is less than the largest prime in the table */
24	0	if (mp_cmp_d(a, s_mp_prime_tab[PRIVATE_MP_PRIME_TAB_SIZE-1]) == MP_LT) {
25		/* find which prime it is bigger than "a" */
26	0	for (x = 0; x < PRIVATE_MP_PRIME_TAB_SIZE; x++) {
27	0	cmp = mp_cmp_d(a, s_mp_prime_tab[x]);
28	0	if (cmp == MP_EQ) {
29	0	continue;
30	0	}
31	0	if (cmp != MP_GT) {
32	0	if ((bbs_style == 1) && ((s_mp_prime_tab[x] & 3u) != 3u)) {
33		/* try again until we get a prime congruent to 3 mod 4 */
34	0	continue;
35	0	} else {
36	0	mp_set(a, s_mp_prime_tab[x]);
37	0	return MP_OKAY;
38	0	}
39	0	}
40	0	}
41		/* fall through to the sieve */
42	0	}
43
44		/* generate a prime congruent to 3 mod 4 or 1/3 mod 4? */
45	0	if (bbs_style == 1) {
46	0	kstep = 4;
47	0	} else {
48	0	kstep = 2;
49	0	}
50
51		/* at this point we will use a combination of a sieve and Miller-Rabin */
52
53	0	if (bbs_style == 1) {
54		/* if a mod 4 != 3 subtract the correct value to make it so */
55	0	if ((a->dp[0] & 3u) != 3u) {
56	0	if ((err = mp_sub_d(a, (a->dp[0] & 3u) + 1u, a)) != MP_OKAY) {
57	0	return err;
58	0	}
59	0	}
60	0	} else {
61	0	if (MP_IS_EVEN(a)) {
62		/* force odd */
63	0	if ((err = mp_sub_d(a, 1uL, a)) != MP_OKAY) {
64	0	return err;
65	0	}
66	0	}
67	0	}
68
69		/* generate the restable */
70	0	for (x = 1; x < PRIVATE_MP_PRIME_TAB_SIZE; x++) {
71	0	if ((err = mp_mod_d(a, s_mp_prime_tab[x], res_tab + x)) != MP_OKAY) {
72	0	return err;
73	0	}
74	0	}
75
76		/* init temp used for Miller-Rabin Testing */
77	0	if ((err = mp_init(&b)) != MP_OKAY) {
78	0	return err;
79	0	}
80
81	0	for (;;) {
82		/* skip to the next non-trivially divisible candidate */
83	0	step = 0;
84	0	do {
85		/* y == 1 if any residue was zero [e.g. cannot be prime] */
86	0	y = 0;
87
88		/* increase step to next candidate */
89	0	step += kstep;
90
91		/* compute the new residue without using division */
92	0	for (x = 1; x < PRIVATE_MP_PRIME_TAB_SIZE; x++) {
93		/* add the step to each residue */
94	0	res_tab[x] += kstep;
95
96		/* subtract the modulus [instead of using division] */
97	0	if (res_tab[x] >= s_mp_prime_tab[x]) {
98	0	res_tab[x] -= s_mp_prime_tab[x];
99	0	}
100
101		/* set flag if zero */
102	0	if (res_tab[x] == 0u) {
103	0	y = 1;
104	0	}
105	0	}
106	0	} while ((y == 1) && (step < (((mp_digit)1 << MP_DIGIT_BIT) - kstep)));
107
108		/* add the step */
109	0	if ((err = mp_add_d(a, step, a)) != MP_OKAY) {
110	0	goto LBL_ERR;
111	0	}
112
113		/* if didn't pass sieve and step == MP_MAX then skip test */
114	0	if ((y == 1) && (step >= (((mp_digit)1 << MP_DIGIT_BIT) - kstep))) {
115	0	continue;
116	0	}
117
118	0	if ((err = mp_prime_is_prime(a, t, &res)) != MP_OKAY) {
119	0	goto LBL_ERR;
120	0	}
121	0	if (res == MP_YES) {
122	0	break;
123	0	}
124	0	}
125
126	0	err = MP_OKAY;
127	0	LBL_ERR:
128	0	mp_clear(&b);
129	0	return err;
130	0	}
131
132		#endif

Coverage Report

Created: 2025-07-11 06:12