7 #include "cln/numtheory.h"
13 #include "cln/abort.h"
17 cl_boolean isprobprime (const cl_I& n)
21 // With a Miller-Rabin count = 50 the final error probability is
24 // Step 1: Trial division (rules out 87% of all numbers quickly).
25 const uint32 trialdivide_limit = 70;
26 var uintC l = integer_length(n);
28 var uint32 nn = cl_I_to_UL(n);
29 if (nn <= cl_small_prime_table_limit) {
31 var uintL i = cl_small_prime_table_search(nn);
32 if (i < cl_small_prime_table_size
33 && ((unsigned int) cl_small_prime_table[i] == nn
39 if ((nn % 2) == 0 || cl_trialdivision(nn,1,trialdivide_limit))
41 // For small n, only few Miller-Rabin tests are needed.
42 if (nn < 2000U) count = 1; // {2}
43 else if (nn < 1300000U) count = 2; // {2,3}
44 else if (nn < 25000000U) count = 3; // {2,3,5}
45 else if (nn < 3200000000U) count = 4; // {2,3,5,7}
47 var uint32 nhi = cl_I_to_UL(ldb(n,cl_byte(32,32)));
48 var uint32 nlo = cl_I_to_UL(ldb(n,cl_byte(32,0)));
49 if ((nlo % 2) == 0 || cl_trialdivision(nhi,nlo,1,trialdivide_limit))
52 if (evenp(n) || cl_trialdivision(n,1,trialdivide_limit))
55 // Step 2: Miller-Rabin test.
56 return cl_miller_rabin_test(n,count,NULL);