Line data    Source code

       1             : #include <tommath.h>
       2             : #ifdef BN_MP_PRIME_FERMAT_C
       3             : /* LibTomMath, multiple-precision integer library -- Tom St Denis
       4             :  *
       5             :  * LibTomMath is a library that provides multiple-precision
       6             :  * integer arithmetic as well as number theoretic functionality.
       7             :  *
       8             :  * The library was designed directly after the MPI library by
       9             :  * Michael Fromberger but has been written from scratch with
      10             :  * additional optimizations in place.
      11             :  *
      12             :  * The library is free for all purposes without any express
      13             :  * guarantee it works.
      14             :  *
      15             :  * Tom St Denis, tomstdenis@gmail.com, http://libtom.org
      16             :  */
      17             : 
      18             : /* performs one Fermat test.
      19             :  *
      20             :  * If "a" were prime then b**a == b (mod a) since the order of
      21             :  * the multiplicative sub-group would be phi(a) = a-1.  That means
      22             :  * it would be the same as b**(a mod (a-1)) == b**1 == b (mod a).
      23             :  *
      24             :  * Sets result to 1 if the congruence holds, or zero otherwise.
      25             :  */
      26           0 : int mp_prime_fermat (mp_int * a, mp_int * b, int *result)
      27             : {
      28             :   mp_int  t;
      29             :   int     err;
      30             : 
      31             :   /* default to composite  */
      32           0 :   *result = MP_NO;
      33             : 
      34             :   /* ensure b > 1 */
      35           0 :   if (mp_cmp_d(b, 1) != MP_GT) {
      36           0 :      return MP_VAL;
      37             :   }
      38             : 
      39             :   /* init t */
      40           0 :   if ((err = mp_init (&t)) != MP_OKAY) {
      41           0 :     return err;
      42             :   }
      43             : 
      44             :   /* compute t = b**a mod a */
      45           0 :   if ((err = mp_exptmod (b, a, a, &t)) != MP_OKAY) {
      46           0 :     goto LBL_T;
      47             :   }
      48             : 
      49             :   /* is it equal to b? */
      50           0 :   if (mp_cmp (&t, b) == MP_EQ) {
      51           0 :     *result = MP_YES;
      52             :   }
      53             : 
      54           0 :   err = MP_OKAY;
      55           0 : LBL_T:mp_clear (&t);
      56           0 :   return err;
      57             : }
      58             : #endif
      59             : 
      60             : /* $Source: /cvs/libtom/libtommath/bn_mp_prime_fermat.c,v $ */
      61             : /* $Revision: 1.4 $ */
      62             : /* $Date: 2006/12/28 01:25:13 $ */