int aws_mp_prime_miller_rabin()

in AWSCognitoIdentityProvider/Internal/JKBigInteger/LibTomMath/tommath.c [5829:5905]

• 51 lines of code
• 15 McCabe index (conditional complexity)

int aws_mp_prime_miller_rabin(aws_mp_int *a, aws_mp_int *b, int *result)
{
  aws_mp_int n1, y, r;
  int     s, j, err;

  /* default */
  *result = AWS_MP_NO;

  /* ensure b > 1 */
  if (aws_mp_cmp_d(b, 1) != AWS_MP_GT) {
     return AWS_MP_VAL;
  }     

  /* get n1 = a - 1 */
  if ((err = aws_mp_init_copy(&n1, a)) != AWS_MP_OKAY) {
    return err;
  }
  if ((err = aws_mp_sub_d(&n1, 1, &n1)) != AWS_MP_OKAY) {
    goto LBL_N1;
  }

  /* set 2**s * r = n1 */
  if ((err = aws_mp_init_copy(&r, &n1)) != AWS_MP_OKAY) {
    goto LBL_N1;
  }

  /* count the number of least significant bits
   * which are zero
   */
  s = aws_mp_cnt_lsb(&r);

  /* now divide n - 1 by 2**s */
  if ((err = aws_mp_div_2d(&r, s, &r, NULL)) != AWS_MP_OKAY) {
    goto LBL_R;
  }

  /* compute y = b**r mod a */
  if ((err = aws_mp_init(&y)) != AWS_MP_OKAY) {
    goto LBL_R;
  }
  if ((err = aws_mp_exptmod(b, &r, a, &y)) != AWS_MP_OKAY) {
    goto LBL_Y;
  }

  /* if y != 1 and y != n1 do */
  if (aws_mp_cmp_d(&y, 1) != AWS_MP_EQ && aws_mp_cmp(&y, &n1) != AWS_MP_EQ) {
    j = 1;
    /* while j <= s-1 and y != n1 */
    while ((j <= (s - 1)) && aws_mp_cmp(&y, &n1) != AWS_MP_EQ) {
      if ((err = aws_mp_sqrmod(&y, a, &y)) != AWS_MP_OKAY) {
         goto LBL_Y;
      }

      /* if y == 1 then composite */
      if (aws_mp_cmp_d(&y, 1) == AWS_MP_EQ) {
         goto LBL_Y;
      }

      ++j;
    }

    /* if y != n1 then composite */
    if (aws_mp_cmp(&y, &n1) != AWS_MP_EQ) {
      goto LBL_Y;
    }
  }

  /* probably prime now */
  *result = AWS_MP_YES;
LBL_Y:
aws_mp_clear(&y);
LBL_R:
aws_mp_clear(&r);
LBL_N1:
aws_mp_clear(&n1);
  return err;
}