GopherProxy

	zptest.c - 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 }