7 #include "cln/numtheory.h"
13 #include "cln/integer_io.h"
14 #include "cln/exception.h"
19 bool isprobprime (const cl_I& n)
22 std::ostringstream buf;
24 fprint(buf, " is not a positive integer.");
25 throw runtime_exception(buf.str());
27 // With a Miller-Rabin count = 50 the final error probability is
30 // Step 1: Trial division (rules out 87% of all numbers quickly).
31 const uint32 trialdivide_limit = 70;
32 var uintC l = integer_length(n);
34 var uint32 nn = cl_I_to_UL(n);
35 if (nn <= cl_small_prime_table_limit) {
37 var uintL i = cl_small_prime_table_search(nn);
38 if (i < cl_small_prime_table_size
39 && ((unsigned int) cl_small_prime_table[i] == nn
45 if ((nn % 2) == 0 || cl_trialdivision(nn,1,trialdivide_limit))
47 // For small n, only few Miller-Rabin tests are needed.
48 if (nn < 2000U) count = 1; // {2}
49 else if (nn < 1300000U) count = 2; // {2,3}
50 else if (nn < 25000000U) count = 3; // {2,3,5}
51 else if (nn < 3200000000U) count = 4; // {2,3,5,7}
53 var uint32 nhi = cl_I_to_UL(ldb(n,cl_byte(32,32)));
54 var uint32 nlo = cl_I_to_UL(ldb(n,cl_byte(32,0)));
55 if ((nlo % 2) == 0 || cl_trialdivision(nhi,nlo,1,trialdivide_limit))
58 if (evenp(n) || cl_trialdivision(n,1,trialdivide_limit))
61 // Step 2: Miller-Rabin test.
62 return cl_miller_rabin_test(n,count,NULL);