Home | History | Annotate | Line # | Download | only in libtommath 
      1 /*	$NetBSD: bn_mp_prime_fermat.c,v 1.2 2017/01/28 21:31:47 christos Exp $	*/
      2 
      3 #include <tommath.h>
      4 #ifdef BN_MP_PRIME_FERMAT_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 (at) gmail.com, http://libtom.org
     18  */
     19 
     20 /* performs one Fermat test.
     21  *
     22  * If "a" were prime then b**a == b (mod a) since the order of
     23  * the multiplicative sub-group would be phi(a) = a-1.  That means
     24  * it would be the same as b**(a mod (a-1)) == b**1 == b (mod a).
     25  *
     26  * Sets result to 1 if the congruence holds, or zero otherwise.
     27  */
     28 int mp_prime_fermat (mp_int * a, mp_int * b, int *result)
     29 {
     30   mp_int  t;
     31   int     err;
     32 
     33   /* default to composite  */
     34   *result = MP_NO;
     35 
     36   /* ensure b > 1 */
     37   if (mp_cmp_d(b, 1) != MP_GT) {
     38      return MP_VAL;
     39   }
     40 
     41   /* init t */
     42   if ((err = mp_init (&t)) != MP_OKAY) {
     43     return err;
     44   }
     45 
     46   /* compute t = b**a mod a */
     47   if ((err = mp_exptmod (b, a, a, &t)) != MP_OKAY) {
     48     goto LBL_T;
     49   }
     50 
     51   /* is it equal to b? */
     52   if (mp_cmp (&t, b) == MP_EQ) {
     53     *result = MP_YES;
     54   }
     55 
     56   err = MP_OKAY;
     57 LBL_T:mp_clear (&t);
     58   return err;
     59 }
     60 #endif
     61 
     62 /* Source: /cvs/libtom/libtommath/bn_mp_prime_fermat.c,v  */
     63 /* Revision: 1.4  */
     64 /* Date: 2006/12/28 01:25:13  */
     65