/src/botan/src/lib/math/numbertheory/primality.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * (C) 2016,2018 Jack Lloyd |
3 | | * |
4 | | * Botan is released under the Simplified BSD License (see license.txt) |
5 | | */ |
6 | | |
7 | | #include <botan/internal/primality.h> |
8 | | #include <botan/internal/monty_exp.h> |
9 | | #include <botan/bigint.h> |
10 | | #include <botan/internal/monty.h> |
11 | | #include <botan/reducer.h> |
12 | | #include <botan/rng.h> |
13 | | #include <algorithm> |
14 | | |
15 | | namespace Botan { |
16 | | |
17 | | bool is_lucas_probable_prime(const BigInt& C, const Modular_Reducer& mod_C) |
18 | 2.32k | { |
19 | 2.32k | if(C == 2 || C == 3 || C == 5 || C == 7 || C == 11 || C == 13) |
20 | 14 | return true; |
21 | | |
22 | 2.31k | if(C <= 1 || C.is_even()) |
23 | 0 | return false; |
24 | | |
25 | 2.31k | BigInt D = BigInt::from_word(5); |
26 | | |
27 | 2.31k | for(;;) |
28 | 8.14k | { |
29 | 8.14k | int32_t j = jacobi(D, C); |
30 | 8.14k | if(j == 0) |
31 | 0 | return false; |
32 | | |
33 | 8.14k | if(j == -1) |
34 | 2.31k | break; |
35 | | |
36 | | // Check 5, -7, 9, -11, 13, -15, 17, ... |
37 | 5.83k | if(D.is_negative()) |
38 | 2.32k | { |
39 | 2.32k | D.flip_sign(); |
40 | 2.32k | D += 2; |
41 | 2.32k | } |
42 | 3.50k | else |
43 | 3.50k | { |
44 | 3.50k | D += 2; |
45 | 3.50k | D.flip_sign(); |
46 | 3.50k | } |
47 | | |
48 | 5.83k | if(D == 17 && is_perfect_square(C).is_nonzero()) |
49 | 0 | return false; |
50 | 5.83k | } |
51 | | |
52 | 2.31k | const BigInt K = C + 1; |
53 | 2.31k | const size_t K_bits = K.bits() - 1; |
54 | | |
55 | 2.31k | BigInt U = BigInt::one(); |
56 | 2.31k | BigInt V = BigInt::one(); |
57 | | |
58 | 2.31k | BigInt Ut, Vt, U2, V2; |
59 | | |
60 | 721k | for(size_t i = 0; i != K_bits; ++i) |
61 | 719k | { |
62 | 719k | const bool k_bit = K.get_bit(K_bits - 1 - i); |
63 | | |
64 | 719k | Ut = mod_C.multiply(U, V); |
65 | | |
66 | 719k | Vt = mod_C.reduce(mod_C.square(V) + mod_C.multiply(D, mod_C.square(U))); |
67 | 719k | Vt.ct_cond_add(Vt.is_odd(), C); |
68 | 719k | Vt >>= 1; |
69 | 719k | Vt = mod_C.reduce(Vt); |
70 | | |
71 | 719k | U = Ut; |
72 | 719k | V = Vt; |
73 | | |
74 | 719k | U2 = mod_C.reduce(Ut + Vt); |
75 | 719k | U2.ct_cond_add(U2.is_odd(), C); |
76 | 719k | U2 >>= 1; |
77 | | |
78 | 719k | V2 = mod_C.reduce(Vt + Ut*D); |
79 | 719k | V2.ct_cond_add(V2.is_odd(), C); |
80 | 719k | V2 >>= 1; |
81 | | |
82 | 719k | U.ct_cond_assign(k_bit, U2); |
83 | 719k | V.ct_cond_assign(k_bit, V2); |
84 | 719k | } |
85 | | |
86 | 2.31k | return (U == 0); |
87 | 2.31k | } |
88 | | |
89 | | bool is_bailie_psw_probable_prime(const BigInt& n, const Modular_Reducer& mod_n) |
90 | 2.54k | { |
91 | 2.54k | if(n == 2) |
92 | 3 | return true; |
93 | 2.53k | else if(n <= 1 || n.is_even()) |
94 | 13 | return false; |
95 | | |
96 | 2.52k | auto monty_n = std::make_shared<Montgomery_Params>(n, mod_n); |
97 | 2.52k | const auto base = BigInt::from_word(2); |
98 | 2.52k | return passes_miller_rabin_test(n, mod_n, monty_n, base) && is_lucas_probable_prime(n, mod_n); |
99 | 2.54k | } |
100 | | |
101 | | bool is_bailie_psw_probable_prime(const BigInt& n) |
102 | 2.54k | { |
103 | 2.54k | Modular_Reducer mod_n(n); |
104 | 2.54k | return is_bailie_psw_probable_prime(n, mod_n); |
105 | 2.54k | } |
106 | | |
107 | | bool passes_miller_rabin_test(const BigInt& n, |
108 | | const Modular_Reducer& mod_n, |
109 | | const std::shared_ptr<Montgomery_Params>& monty_n, |
110 | | const BigInt& a) |
111 | 2.56k | { |
112 | 2.56k | if(n < 3 || n.is_even()) |
113 | 0 | return false; |
114 | | |
115 | 2.56k | BOTAN_ASSERT_NOMSG(n > 1); |
116 | | |
117 | 2.56k | const BigInt n_minus_1 = n - 1; |
118 | 2.56k | const size_t s = low_zero_bits(n_minus_1); |
119 | 2.56k | const BigInt nm1_s = n_minus_1 >> s; |
120 | 2.56k | const size_t n_bits = n.bits(); |
121 | | |
122 | 2.56k | const size_t powm_window = 4; |
123 | | |
124 | 2.56k | auto powm_a_n = monty_precompute(monty_n, a, powm_window); |
125 | | |
126 | 2.56k | BigInt y = monty_execute(*powm_a_n, nm1_s, n_bits); |
127 | | |
128 | 2.56k | if(y == 1 || y == n_minus_1) |
129 | 792 | return true; |
130 | | |
131 | 56.8k | for(size_t i = 1; i != s; ++i) |
132 | 56.6k | { |
133 | 56.6k | y = mod_n.square(y); |
134 | | |
135 | 56.6k | if(y == 1) // found a non-trivial square root |
136 | 2 | return false; |
137 | | |
138 | | /* |
139 | | -1 is the trivial square root of unity, so ``a`` is not a |
140 | | witness for this number - give up |
141 | | */ |
142 | 56.6k | if(y == n_minus_1) |
143 | 1.56k | return true; |
144 | 56.6k | } |
145 | | |
146 | 212 | return false; |
147 | 1.77k | } |
148 | | |
149 | | bool is_miller_rabin_probable_prime(const BigInt& n, |
150 | | const Modular_Reducer& mod_n, |
151 | | RandomNumberGenerator& rng, |
152 | | size_t test_iterations) |
153 | 15 | { |
154 | 15 | if(n < 3 || n.is_even()) |
155 | 0 | return false; |
156 | | |
157 | 15 | auto monty_n = std::make_shared<Montgomery_Params>(n, mod_n); |
158 | | |
159 | 44 | for(size_t i = 0; i != test_iterations; ++i) |
160 | 43 | { |
161 | 43 | const BigInt a = BigInt::random_integer(rng, BigInt::from_word(2), n); |
162 | | |
163 | 43 | if(!passes_miller_rabin_test(n, mod_n, monty_n, a)) |
164 | 14 | return false; |
165 | 43 | } |
166 | | |
167 | | // Failed to find a counterexample |
168 | 1 | return true; |
169 | 15 | } |
170 | | |
171 | | |
172 | | size_t miller_rabin_test_iterations(size_t n_bits, size_t prob, bool random) |
173 | 1 | { |
174 | 1 | const size_t base = (prob + 2) / 2; // worst case 4^-t error rate |
175 | | |
176 | | /* |
177 | | * If the candidate prime was maliciously constructed, we can't rely |
178 | | * on arguments based on p being random. |
179 | | */ |
180 | 1 | if(random == false) |
181 | 0 | return base; |
182 | | |
183 | | /* |
184 | | * For randomly chosen numbers we can use the estimates from |
185 | | * http://www.math.dartmouth.edu/~carlp/PDF/paper88.pdf |
186 | | * |
187 | | * These values are derived from the inequality for p(k,t) given on |
188 | | * the second page. |
189 | | */ |
190 | 1 | if(prob <= 128) |
191 | 1 | { |
192 | 1 | if(n_bits >= 1536) |
193 | 0 | return 4; // < 2^-133 |
194 | 1 | if(n_bits >= 1024) |
195 | 0 | return 6; // < 2^-133 |
196 | 1 | if(n_bits >= 512) |
197 | 0 | return 12; // < 2^-129 |
198 | 1 | if(n_bits >= 256) |
199 | 1 | return 29; // < 2^-128 |
200 | 1 | } |
201 | | |
202 | | /* |
203 | | If the user desires a smaller error probability than we have |
204 | | precomputed error estimates for, just fall back to using the worst |
205 | | case error rate. |
206 | | */ |
207 | 0 | return base; |
208 | 1 | } |
209 | | |
210 | | } |