1 // cl_miller_rabin_test().
12 #include "cl_modinteger.h"
14 cl_boolean cl_miller_rabin_test (const cl_I& n, int count, cl_I* factor)
16 // [Cohen], section 8.2, algorithm 8.2.2.
17 var cl_modint_ring R = cl_find_modint_ring(n); // Z/nZ
19 var uintL e = ord2(m);
22 var cl_MI one = R->one();
23 var cl_MI minusone = R->uminus(one);
24 for (int i = 0; i < count; i++) {
25 // Choosing aa small makes the expt_pos faster.
28 : i <= cl_small_prime_table_size
29 ? (cl_I) (unsigned int) cl_small_prime_table[i-1] // small prime
30 : 2+random_I(n-2)); // or random >=2, <n
34 var cl_MI a = R->canonhom(aa);
35 var cl_MI b = R->expt_pos(a,m); // b = a^m
38 for (uintL s = e; s > 0; s--) {
41 var cl_MI new_b = R->square(b);
43 // (b-1)*(b+1) == 0 mod n, hence n not prime.
45 *factor = gcd(R->retract(b)-1,n);
50 // b = a^(2^e*m) = a^(n-1), but b != -1 mod n, hence n not prime.
52 var cl_I g = gcd(aa,n);