libzahl

big integer library
git clone git://git.suckless.org/libzahl
Log | Files | Refs | README | LICENSE

zptest.c (1193B)


      1 /* See LICENSE file for copyright and license details. */
      2 #include "internals.h"
      3 
      4 #define x   libzahl_tmp_ptest_x
      5 #define a   libzahl_tmp_ptest_a
      6 #define d   libzahl_tmp_ptest_d
      7 #define n1  libzahl_tmp_ptest_n1
      8 #define n4  libzahl_tmp_ptest_n4
      9 
     10 
     11 enum zprimality
     12 zptest(z_t witness, z_t n, int t)
     13 {
     14 	/*
     15 	 * Miller–Rabin primarlity test.
     16 	 */
     17 
     18 	size_t i, r;
     19 
     20 	if (unlikely(zcmpu(n, 3) <= 0)) {
     21 		if (zcmpu(n, 1) <= 0) {
     22 			if (witness)
     23 				SET(witness, n);
     24 			return NONPRIME;
     25 		} else {
     26 			return PRIME;
     27 		}
     28 	}
     29 	if (unlikely(zeven(n))) {
     30 		if (witness)
     31 			zsetu(witness, 2);
     32 		return NONPRIME;
     33 	}
     34 
     35 	zsub_unsigned(n1, n, libzahl_const_1);
     36 	zsub_unsigned(n4, n, libzahl_const_4);
     37 
     38 	r = zlsb(n1);
     39 	zrsh(d, n1, r);
     40 
     41 	while (t--) {
     42 		zrand(a, DEFAULT_RANDOM, UNIFORM, n4);
     43 		zadd_unsigned(a, a, libzahl_const_2);
     44 		zmodpow(x, a, d, n);
     45 
     46 		if (!zcmp(x, libzahl_const_1) || !zcmp(x, n1))
     47 			continue;
     48 
     49 		for (i = 1; i < r; i++) {
     50 			zmodsqr(x, x, n);
     51 			if (!zcmp(x, libzahl_const_1)) {
     52 				if (witness)
     53 					zswap(witness, a);
     54 				return NONPRIME;
     55 			}
     56 			if (!zcmp(x, n1))
     57 				break;
     58 		}
     59 		if (i == r) {
     60 			if (witness)
     61 				zswap(witness, a);
     62 			return NONPRIME;
     63 		}
     64 	}
     65 
     66 	return PROBABLY_PRIME;
     67 }