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