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 */
mp_prime_fermat(const mp_int * a,const mp_int * b,mp_bool * result)14 mp_err mp_prime_fermat(const mp_int *a, const mp_int *b, mp_bool *result)
15 {
16 mp_int t;
17 mp_err err;
18
19 /* default to composite */
20 *result = MP_NO;
21
22 /* ensure b > 1 */
23 if (mp_cmp_d(b, 1uL) != MP_GT) {
24 return MP_VAL;
25 }
26
27 /* init t */
28 if ((err = mp_init(&t)) != MP_OKAY) {
29 return err;
30 }
31
32 /* compute t = b**a mod a */
33 if ((err = mp_exptmod(b, a, a, &t)) != MP_OKAY) {
34 goto LBL_T;
35 }
36
37 /* is it equal to b? */
38 if (mp_cmp(&t, b) == MP_EQ) {
39 *result = MP_YES;
40 }
41
42 err = MP_OKAY;
43 LBL_T:
44 mp_clear(&t);
45 return err;
46 }
47 #endif
48