Line data    Source code

       1             : #include "tommath_private.h"
       2             : #ifdef BN_MP_PRIME_FERMAT_C
       3             : /* LibTomMath, multiple-precision integer library -- Tom St Denis */
       4             : /* SPDX-License-Identifier: Unlicense */
       5             : 
       6             : /* performs one Fermat test.
       7             :  *
       8             :  * If "a" were prime then b**a == b (mod a) since the order of
       9             :  * the multiplicative sub-group would be phi(a) = a-1.  That means
      10             :  * it would be the same as b**(a mod (a-1)) == b**1 == b (mod a).
      11             :  *
      12             :  * Sets result to 1 if the congruence holds, or zero otherwise.
      13             :  */
      14           0 : mp_err mp_prime_fermat(const mp_int *a, const mp_int *b, mp_bool *result)
      15             : {
      16           0 :    mp_int  t;
      17           0 :    mp_err  err;
      18             : 
      19             :    /* default to composite  */
      20           0 :    *result = MP_NO;
      21             : 
      22             :    /* ensure b > 1 */
      23           0 :    if (mp_cmp_d(b, 1uL) != MP_GT) {
      24           0 :       return MP_VAL;
      25             :    }
      26             : 
      27             :    /* init t */
      28           0 :    if ((err = mp_init(&t)) != MP_OKAY) {
      29           0 :       return err;
      30             :    }
      31             : 
      32             :    /* compute t = b**a mod a */
      33           0 :    if ((err = mp_exptmod(b, a, a, &t)) != MP_OKAY) {
      34           0 :       goto LBL_T;
      35             :    }
      36             : 
      37             :    /* is it equal to b? */
      38           0 :    if (mp_cmp(&t, b) == MP_EQ) {
      39           0 :       *result = MP_YES;
      40             :    }
      41             : 
      42           0 :    err = MP_OKAY;
      43           0 : LBL_T:
      44           0 :    mp_clear(&t);
      45           0 :    return err;
      46             : }
      47             : #endif