blob: 9bd6ba1fc2cd6c481b1cff8e23f2fc746d9ba3b5 [file] [log] [blame]
 #include #ifdef BN_MP_PRIME_MILLER_RABIN_C /* 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@gmail.com, http://math.libtomcrypt.com */ /* 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 LBL_N1; } /* set 2**s * r = n1 */ if ((err = mp_init_copy (&r, &n1)) != MP_OKAY) { goto LBL_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 LBL_R; } /* compute y = b**r mod a */ if ((err = mp_init (&y)) != MP_OKAY) { goto LBL_R; } if ((err = mp_exptmod (b, &r, a, &y)) != MP_OKAY) { goto LBL_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 LBL_Y; } /* if y == 1 then composite */ if (mp_cmp_d (&y, 1) == MP_EQ) { goto LBL_Y; } ++j; } /* if y != n1 then composite */ if (mp_cmp (&y, &n1) != MP_EQ) { goto LBL_Y; } } /* probably prime now */ *result = MP_YES; LBL_Y:mp_clear (&y); LBL_R:mp_clear (&r); LBL_N1:mp_clear (&n1); return err; } #endif /* \$Source: /cvs/libtom/libtommath/bn_mp_prime_miller_rabin.c,v \$ */ /* \$Revision: 1.3 \$ */ /* \$Date: 2006/03/31 14:18:44 \$ */