int aws_mp_prime_next_prime()

in AWSCognitoIdentityProvider/Internal/JKBigInteger/LibTomMath/tommath.c [1359:1500]

• 95 lines of code
• 32 McCabe index (conditional complexity)

int aws_mp_prime_next_prime(aws_mp_int *a, int t, int bbs_style)
{
   int      err, res = 0, x, y;
   aws_mp_digit res_tab[AWS_JKTM_PRIME_SIZE], step, kstep;
   aws_mp_int b;

   /* ensure t is valid */
   if (t <= 0 || t > AWS_JKTM_PRIME_SIZE) {
      return AWS_MP_VAL;
   }

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

   /* simple algo if a is less than the largest prime in the table */
   if (aws_mp_cmp_d(a, aws_ltm_prime_tab[AWS_JKTM_PRIME_SIZE - 1]) == AWS_MP_LT) {
      /* find which prime it is bigger than */
      for (x = AWS_JKTM_PRIME_SIZE - 2; x >= 0; x--) {
          if (aws_mp_cmp_d(a, aws_ltm_prime_tab[x]) != AWS_MP_LT) {
             if (bbs_style == 1) {
                /* ok we found a prime smaller or
                 * equal [so the next is larger]
                 *
                 * however, the prime must be
                 * congruent to 3 mod 4
                 */
                if ((aws_ltm_prime_tab[x + 1] & 3) != 3) {
                   /* scan upwards for a prime congruent to 3 mod 4 */
                   for (y = x + 1; y < AWS_JKTM_PRIME_SIZE; y++) {
                       if ((aws_ltm_prime_tab[y] & 3) == 3) {
                           aws_mp_set(a, aws_ltm_prime_tab[y]);
                          return AWS_MP_OKAY;
                       }
                   }
                }
             } else {
                 aws_mp_set(a, aws_ltm_prime_tab[x + 1]);
                return AWS_MP_OKAY;
             }
          }
      }
      /* at this point a maybe 1 */
      if (aws_mp_cmp_d(a, 1) == AWS_MP_EQ) {
          aws_mp_set(a, 2);
         return AWS_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] & 3) != 3) {
         if ((err = aws_mp_sub_d(a, (a->dp[0] & 3) + 1, a)) != AWS_MP_OKAY) { return err; };
      }
   } else {
      if (aws_mp_iseven(a) == 1) {
         /* force odd */
         if ((err = aws_mp_sub_d(a, 1, a)) != AWS_MP_OKAY) {
            return err;
         }
      }
   }

   /* generate the restable */
   for (x = 1; x < AWS_JKTM_PRIME_SIZE; x++) {
      if ((err = aws_mp_mod_d(a, aws_ltm_prime_tab[x], res_tab + x)) != AWS_MP_OKAY) {
         return err;
      }
   }

   /* init temp used for Miller-Rabin Testing */
   if ((err = aws_mp_init(&b)) != AWS_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 < AWS_JKTM_PRIME_SIZE; x++) {
             /* add the step to each residue */
             res_tab[x] += kstep;

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

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

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

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

      /* is this prime? */
      for (x = 0; x < t; x++) {
          aws_mp_set(&b, aws_ltm_prime_tab[x]);
          if ((err = aws_mp_prime_miller_rabin(a, &b, &res)) != AWS_MP_OKAY) {
             goto LBL_ERR;
          }
          if (res == AWS_MP_NO) {
             break;
          }
      }

      if (res == AWS_MP_YES) {
         break;
      }
   }

   err = AWS_MP_OKAY;
LBL_ERR:
aws_mp_clear(&b);
   return err;
}