zptest.c - libzahl - big integer library
 (HTM) git clone git://git.suckless.org/libzahl
 (DIR) Log
 (DIR) Files
 (DIR) Refs
 (DIR) README
 (DIR) 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 }