1/* $NetBSD: bn_mp_prime_is_prime.c,v 1.2 2017/01/28 21:31:47 christos Exp $ */ 2 3#include <tommath.h> 4#ifdef BN_MP_PRIME_IS_PRIME_C 5/* LibTomMath, multiple-precision integer library -- Tom St Denis 6 * 7 * LibTomMath is a library that provides multiple-precision 8 * integer arithmetic as well as number theoretic functionality. 9 * 10 * The library was designed directly after the MPI library by 11 * Michael Fromberger but has been written from scratch with 12 * additional optimizations in place. 13 * 14 * The library is free for all purposes without any express 15 * guarantee it works. 16 * 17 * Tom St Denis, tomstdenis@gmail.com, http://libtom.org 18 */ 19 20/* performs a variable number of rounds of Miller-Rabin 21 * 22 * Probability of error after t rounds is no more than 23 24 * 25 * Sets result to 1 if probably prime, 0 otherwise 26 */ 27int mp_prime_is_prime (mp_int * a, int t, int *result) 28{ 29 mp_int b; 30 int ix, err, res; 31 32 /* default to no */ 33 *result = MP_NO; 34 35 /* valid value of t? */ 36 if (t <= 0 || t > PRIME_SIZE) { 37 return MP_VAL; 38 } 39 40 /* is the input equal to one of the primes in the table? */ 41 for (ix = 0; ix < PRIME_SIZE; ix++) { 42 if (mp_cmp_d(a, ltm_prime_tab[ix]) == MP_EQ) { 43 *result = 1; 44 return MP_OKAY; 45 } 46 } 47 48 /* first perform trial division */ 49 if ((err = mp_prime_is_divisible (a, &res)) != MP_OKAY) { 50 return err; 51 } 52 53 /* return if it was trivially divisible */ 54 if (res == MP_YES) { 55 return MP_OKAY; 56 } 57 58 /* now perform the miller-rabin rounds */ 59 if ((err = mp_init (&b)) != MP_OKAY) { 60 return err; 61 } 62 63 for (ix = 0; ix < t; ix++) { 64 /* set the prime */ 65 mp_set (&b, ltm_prime_tab[ix]); 66 67 if ((err = mp_prime_miller_rabin (a, &b, &res)) != MP_OKAY) { 68 goto LBL_B; 69 } 70 71 if (res == MP_NO) { 72 goto LBL_B; 73 } 74 } 75 76 /* passed the test */ 77 *result = MP_YES; 78LBL_B:mp_clear (&b); 79 return err; 80} 81#endif 82 83/* Source: /cvs/libtom/libtommath/bn_mp_prime_is_prime.c,v */ 84/* Revision: 1.4 */ 85/* Date: 2006/12/28 01:25:13 */ 86