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 }