# public libtom /libtommath

### Subversion checkout URL

You can clone with HTTPS or Subversion.

Fetching contributors…

Cannot retrieve contributors at this time

file 98 lines (84 sloc) 2.276 kb
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 `/* LibTomMath, multiple-precision integer library -- Tom St Denis * * LibTomMath is a library that provides multiple-precision * integer arithmetic as well as number theoretic functionality. * * The library was designed directly after the MPI library by * Michael Fromberger but has been written from scratch with * additional optimizations in place. * * The library is free for all purposes without any express * guarantee it works. * * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org */#include /* Miller-Rabin test of "a" to the base of "b" as described in * HAC pp. 139 Algorithm 4.24 * * Sets result to 0 if definitely composite or 1 if probably prime. * Randomly the chance of error is no more than 1/4 and often * very much lower. */int mp_prime_miller_rabin (mp_int * a, mp_int * b, int *result){  mp_int n1, y, r;  int s, j, err;  /* default */  *result = MP_NO;  /* ensure b > 1 */  if (mp_cmp_d(b, 1) != MP_GT) {     return MP_VAL;  }   /* get n1 = a - 1 */  if ((err = mp_init_copy (&n1, a)) != MP_OKAY) {    return err;  }  if ((err = mp_sub_d (&n1, 1, &n1)) != MP_OKAY) {    goto __N1;  }  /* set 2**s * r = n1 */  if ((err = mp_init_copy (&r, &n1)) != MP_OKAY) {    goto __N1;  }  /* count the number of least significant bits * which are zero */  s = mp_cnt_lsb(&r);  /* now divide n - 1 by 2**s */  if ((err = mp_div_2d (&r, s, &r, NULL)) != MP_OKAY) {    goto __R;  }  /* compute y = b**r mod a */  if ((err = mp_init (&y)) != MP_OKAY) {    goto __R;  }  if ((err = mp_exptmod (b, &r, a, &y)) != MP_OKAY) {    goto __Y;  }  /* if y != 1 and y != n1 do */  if (mp_cmp_d (&y, 1) != MP_EQ && mp_cmp (&y, &n1) != MP_EQ) {    j = 1;    /* while j <= s-1 and y != n1 */    while ((j <= (s - 1)) && mp_cmp (&y, &n1) != MP_EQ) {      if ((err = mp_sqrmod (&y, a, &y)) != MP_OKAY) {         goto __Y;      }      /* if y == 1 then composite */      if (mp_cmp_d (&y, 1) == MP_EQ) {         goto __Y;      }      ++j;    }    /* if y != n1 then composite */    if (mp_cmp (&y, &n1) != MP_EQ) {      goto __Y;    }  }  /* probably prime now */  *result = MP_YES;__Y:mp_clear (&y);__R:mp_clear (&r);__N1:mp_clear (&n1);  return err;}`
Something went wrong with that request. Please try again.